mono interpreter System.Collections.Generic container run slower than jit

[srxqds]

Description

testcase code show below:

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    List<int> insert_table = new List<int>();
    for(int i=0; i<10000; i++)
        insert_table.Add(i);
}
sw.Stop();
Console.WriteLine(String.Format("test_insert_array, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

Dictionary<string, int> map = new Dictionary<string, int>();
List<int> list = new List<int>();
List<int> shuffle = new List<int>();
int[] array = new int[10000];
for(int i=0; i<10000;i++)
{
    map["" + i] = i;
    list.Add(i);
    array[i] = i;
    shuffle.Add(i);
}

for(int i=1;i<5000;i++)
{
    Random rnd = new Random();
    int j = rnd.Next(0, i);
    int rep = 10000 - 1 - j;
    int tmp = shuffle[rep];
    shuffle[rep] = shuffle[j];
    shuffle[j] = tmp;
}

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    for(int i=0; i<10000; i++)
    {
        int a = list[shuffle[i]];
        //int a = list[i];
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_random_index_list, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    for(int i=0; i<10000; i++)
    {
        //int a = list[shuffle[i]];
        int a = list[i];
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_range_index_list, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100000; j++)
{
    int a1 = list[0];
    int a2 = list[9999];
    int a3 = list[1500];
    int a4 = list[3500];
    int a5 = list[7000];
}
sw.Stop();
Console.WriteLine(String.Format("test_some_index_list, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));
        sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    for(int i=0; i<10000; i++)
    {
        // int a = array[shuffle[i]];
        int a = array[i];
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_random_index_array, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));


sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    foreach(int a in list)
    {
        int va = a;
        //int b = entry.Value;
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_iterate_list, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    for(int i=0; i<list.Count;i++)
    {
        int va = list[i];
        //int b = entry.Value;
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_for_list, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    foreach(int a in array)
    {
        int va = a;
        //int b = entry.Value;
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_iterate_array, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));


sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    foreach(KeyValuePair<string, int> entry in map)
    {
        int b = entry.Value;
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_iterate_map, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

var keys = map.Keys;
sw = Stopwatch.StartNew();
sw.Start();

for(int j=0; j<100; j++)
{
    foreach(string key in keys)
    {
        int b = map[key];
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_key_iterate_map, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    foreach(string key in keys)
    {
        string value3 = key;
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_iterate_keys, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

var values = map.Values;
sw = Stopwatch.StartNew();
sw.Start();
for(int j=0; j<100; j++)
{
    foreach(int key in values)
    {
        int value2 = key;
    }
}
sw.Stop();
Console.WriteLine(String.Format("test_iterate_values, Time taken: {0}ms", sw.Elapsed.TotalMilliseconds));

Configuration

all built with release configuration and run on windows x64 pc using mono6.10.0.

Data

runer with mono ./test.exe output:

test_insert_array, Time taken: 8.4756ms
test_random_index_list, Time taken: 3.6109ms
test_range_index_list, Time taken: 1.915ms
test_some_index_list, Time taken: 0.8582ms
test_random_index_array, Time taken: 1.7885ms
test_iterate_list, Time taken: 2.8108ms
test_for_list, Time taken: 2.0223ms
test_iterate_array, Time taken: 1.9559ms
test_iterate_map, Time taken: 9.6818ms
test_key_iterate_map, Time taken: 38.7477ms
test_iterate_keys, Time taken: 4.2465ms
test_iterate_values, Time taken: 5.1388ms

runer with mono --interp ./test.exe output:

test_insert_array, Time taken: 69.5591ms
test_random_index_list, Time taken: 96.2123ms
test_range_index_list, Time taken: 42.0968ms
test_some_index_list, Time taken: 19.1583ms
test_random_index_array, Time taken: 13.6853ms
test_iterate_list, Time taken: 58.5759ms
test_for_list, Time taken: 61.506ms
test_iterate_array, Time taken: 16.1444ms
test_iterate_map, Time taken: 181.1164ms
test_key_iterate_map, Time taken: 1455.6495ms
test_iterate_keys, Time taken: 78.4558ms
test_iterate_values, Time taken: 72.7544ms

Analysis

[ghost]

Tagging subscribers to this area: @eiriktsarpalis, @jeffhandley
See info in area-owners.md if you want to be subscribed.

[srxqds]

I think the List and Dictionary<Key, Value> are mostly used, it should be optimizated？

[ghost]

Tagging subscribers to this area: @BrzVlad
See info in area-owners.md if you want to be subscribed.

[BrzVlad]

Tested with latest version of interp and the numbers are much better than this. The iterate benchmarks are still somewhat slower (up to 10x slower than jit), because interp doesn't currently support loop invariant hoisting. This optimization is currently not on the roadmap. Keeping track of it in #47520