why in this simple test the speed of method relates to the order of triggering?

Question

I was doing other experiments until this strange behaviour caught my eye.

code is compiled in x64 release.

if key in 1, the 3rd run of List method cost 40% more time than the first 2. output is

List costs 9312
List costs 9289
Array costs 12730
List costs 11950

if key in 2, the 3rd run of Array method cost 30% more time than the first 2. output is

Array costs 8082
Array costs 8086
List costs 11937
Array costs 12698

You can see the pattern, the complete code is attached following (just compile and run): {the code presented is minimal to run the test. The actually code used to get reliable result is more complicated, I wrapped the method and tested it 100+ times after proper warmed up}

class ListArrayLoop
{
    readonly int[] myArray;
    readonly List<int> myList;
    readonly int totalSessions;

    public ListArrayLoop(int loopRange, int totalSessions)
    {
        myArray = new int[loopRange];
        for (int i = 0; i < myArray.Length; i++)
        {
            myArray[i] = i;
        }
        myList = myArray.ToList();
        this.totalSessions = totalSessions;
    }
    public  void ArraySum()
    {
        var pool = myArray;
        long sum = 0;
        for (int j = 0; j < totalSessions; j++)
        {
            sum += pool.Sum();
        }
    }
    public void ListSum()
    {
        var pool = myList;
        long sum = 0;
        for (int j = 0; j < totalSessions; j++)
        {
            sum += pool.Sum();
        }
    }

}
class Program
{
    static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();
        ListArrayLoop test = new ListArrayLoop(10000, 100000);

        string input = Console.ReadLine();


        if (input == "1")
        {
            sw.Start();
            test.ListSum();
            sw.Stop();
            Console.WriteLine("List costs {0}",sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            test.ListSum();
            sw.Stop();
            Console.WriteLine("List costs {0}", sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            test.ArraySum();
            sw.Stop();
            Console.WriteLine("Array costs {0}", sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            test.ListSum();
            sw.Stop();
            Console.WriteLine("List costs {0}", sw.ElapsedMilliseconds);
        }
        else
        {
            sw.Start();
            test.ArraySum();
            sw.Stop();
            Console.WriteLine("Array costs {0}", sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            test.ArraySum();
            sw.Stop();
            Console.WriteLine("Array costs {0}", sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            test.ListSum();
            sw.Stop();
            Console.WriteLine("List costs {0}", sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            test.ArraySum();
            sw.Stop();
            Console.WriteLine("Array costs {0}", sw.ElapsedMilliseconds);
        }

        Console.ReadKey();
    }
}

Answer 1

Contrived problems give you contrived answers.

Optimization should be done after code is written and not before. Write your solution the way that is easiest to understand and maintain. Then if the program is not fast enough for your use case, then you use a profiling tool and go back and see where the actual bottleneck is, not where you "think" it is.

Most optimizations people try to do in your situation is spending 6 hours to do something that will decrease the run time by 1 second. Most small programs will not be run enough times to offset the cost you spent trying to "optimize" it.

---

That being said this is a strange edge case. I modified it a bit and am running it though a profiler but I need to downgrade my VS2010 install so I can get .NET framework source stepping back.

---

I ran though the profiler using the larger example, I can find no good reason why it would take longer.

Answer 2

Your issue is your test. When you are benchmarking code there are a couple of guiding principals you should always follow:

1. Processor Affinity: Use only a single processor, usually not #1.
2. Warmup: Always perform the test a small number of times up front.
3. Duration: Make sure your test duration is at least 500ms.
4. Average: Average together multiple runs to remove anomalies.
5. Cleanup: Force the GC to collect allocated objects between tests.
6. Cooldown: Allow the process to sleep for a short-period of time.

So using these guidelines and rewriting your tests I get the following results:

Run 1

Enter test number (1|2): 1
ListSum averages 776
ListSum averages 753
ArraySum averages 1102
ListSum averages 753
Press any key to continue . . .

Run 2

Enter test number (1|2): 2
ArraySum averages 1155
ArraySum averages 1102
ListSum averages 753
ArraySum averages 1067
Press any key to continue . . .

So here is the final test code used:

static void Main(string[] args)
{
    //We just need a single-thread for this test.
    Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
    System.Threading.Thread.BeginThreadAffinity();

    Console.Write("Enter test number (1|2): ");
    string input = Console.ReadLine();

    //perform the action just a few times to jit the code.
    ListArrayLoop warmup = new ListArrayLoop(10, 10);
    Console.WriteLine("Performing warmup...");
    Test(warmup.ListSum);
    Test(warmup.ArraySum);
    Console.WriteLine("Warmup complete...");
    Console.WriteLine();

    ListArrayLoop test = new ListArrayLoop(10000, 10000);

    if (input == "1")
    {
        Test(test.ListSum);
        Test(test.ListSum);
        Test(test.ArraySum);
        Test(test.ListSum);
    }
    else
    {
        Test(test.ArraySum);
        Test(test.ArraySum);
        Test(test.ListSum);
        Test(test.ArraySum);
    }
}

private static void Test(Action test)
{
    long totalElapsed = 0;
    for (int counter = 10; counter > 0; counter--)
    {
        try
        {
            var sw = Stopwatch.StartNew();
            test();
            totalElapsed += sw.ElapsedMilliseconds;
        }
        finally { }

        GC.Collect(0, GCCollectionMode.Forced);
        GC.WaitForPendingFinalizers();
        //cooldown
        for (int i = 0; i < 100; i++)
            System.Threading.Thread.Sleep(0);
    }
    Console.WriteLine("{0} averages {1}", test.Method.Name, totalElapsed / 10);
}

Note: Some people may debate about the usefulness of the cool-down; However, everyone agrees that even if it's not helpful, it is not harmful. I find that on some tests it can yield a more reliable result; however, in the example above I doubt it makes any difference.

Answer 3

Way too much for a comment so it's CW -- feel free to incorporate and I'll delete this. The given code is a little off to me but the problem is still interesting. If you mix calls, you get poorer performance. This code highlights it:

static void Main(string[] args)
{
    var input = Console.ReadLine();

        var test = new ListArrayLoop(10000, 1000);

        switch (input)
        {
            case "1":
                Test(test.ListSum);
                break;
            case "2":
                Test(test.ArraySum);
                break;
            case "3":
                // adds about 40 ms
                test.ArraySum();
                Test(test.ListSum);
                break;
            default:
                // adds about 35 ms
                test.ListSum();
                Test(test.ArraySum);
                break;
        }

}

private static void Test(Action toTest)
{
    for (int i = 0; i < 100; i++)
    {
        var sw = Stopwatch.StartNew();
        toTest();
        sw.Stop();
        Console.WriteLine("costs {0}", sw.ElapsedMilliseconds);
        sw.Reset();
    }
}

Answer 4

Lists are implemented in .NET with arrays so the average performance should be the same (since you do not change the length of either).

It looks like you have averaged the sum()s' times sufficiently, this could be a GC issue with an iterator used in the sum() method.

Answer 5

Short answer: It is because CRL has optimization for dispatching methods called on interface-type. As long as particular interface's method call is made on the same type (that implements this interface), CLR uses fast dispatching routine (only 3 instructions) that only checks actual type of instance and in case of match it jumps directly on precomputed address of particular method. But when the same interface's method call is made on instance of another type, CLR switches dispatching to slower routine (which can dispatch methods for any actual instance type).

Long answer: Firstly, take a look at how the method System.Linq.Enumerable.Sum() is declared (I omitted validity checking of source parameter because it's not important it this case):

public static int Sum(this IEnumerable<int> source)
{
    int num = 0;
    foreach (int num2 in source)
        num += num2;
    return num;
}

So all types that implement IEnumerable< int > can call this extension method, including int[] and List< int >. Keyword foreach is just abbreviation for getting enumerator via IEnumerable< T >.GetEnumerator() and iterating through all values. So this method actually does this:

    public static int Sum(this IEnumerable<int> source)
    {
        int num = 0;
        IEnumerator<int> Enumerator = source.GetEnumerator();
        while(Enumerator.MoveNext())
            num += Enumerator.Current;
        return num;
    }

Now you can clearly see, that method body contains three method calls on interface-type variables: GetEnumerator(), MoveNext(), and Current (although Current is actually property, not method, reading value from property just calls corresponding getter method).

GetEnumerator() typically creates new instance of some auxiliary class, which implements IEnumerator< T > and thus is able to return all values one by one. It is important to note, that in case of int[] and List< int >, types of enumerators returned by GetEnumerator() ot these two classes are different. If argument source is of type int[], then GetEnumerator() returns instance of type SZGenericArrayEnumerator< int > and if source is of type List< int >, then it returns instance of type List< int >+Enumerator< int >.

Two other methods (MoveNext() and Current) are repeatedly called in tight loop and therefore their speed is crucial for overall performance. Unfortunatelly calling method on interface-type variable (such as IEnumerator< int >) is not as straightforward as ordinary instance method call. CLR must dynamically find out actual type of object in variable and then find out, which object's method implements corresponding interface method.

CLR tries to avoid doing this time consuming lookup on every call with a little trick. When particular method (such as MoveNext()) is called for the first time, CLR finds actual type of instance on which this call is made (for example SZGenericArrayEnumerator< int > in case you called Sum on int[]) and finds address of method, that implements corresponding method for this type (that is address of method SZGenericArrayEnumerator< int >.MoveNext()). Then it uses this information to generate auxiliary dispatching method, which simply checks, whether actual instance type is the same as when first call was made (that is SZGenericArrayEnumerator< int >) and if it is, it directly jumps to the method's address found earlier. So on subsequent calls, no complicated method lookup is made as long as type of instance remains the same. But when call is made on enumerator of different type (such as List< int >+Enumerator< int > in case of calculating sum of List< int >), CLR no longer uses this fast dispatching method. Instead another (general-purpose) and much slower dispatching method is used.

So as long as Sum() is called on array only, CLR dispatches calls to GetEnumerator(), MoveNext(), and Current using fast method. When Sum() is called on list too, CLR switches to slower dispatching method and therefore performance decreases.

If performance is your concern, implement your own separate Sum() extension method for every type, on which you want to call Sum(). This ensures that CLR will use fast dispatching method. For example:

public static class FasterSumExtensions
{
    public static int Sum(this int[] source)
    {
        int num = 0;
        foreach (int num2 in source)
            num += num2;
        return num;
    }

    public static int Sum(this List<int> source)
    {
        int num = 0;
        foreach(int num2 in source)
            num += num2;
        return num;
    }
}

Or even better, avoid using IEnumerable< T > interface at all (because it's still brings noticeable overhead). For example:

public static class EvenFasterSumExtensions
{
    public static int Sum(this int[] source)
    {
        int num = 0;
        for(int i = 0; i < source.Length; i++)
            num += source[i];
        return num;
    }

    public static int Sum(this List<int> source)
    {
        int num = 0;
        for(int i = 0; i < source.Count; i++)
            num += source[i];
        return num;
    }
}

Here are results from my computer:

• Your original program: 9844, 9841, 12545, 14384
• FasterSumExtensions: 6149, 6445, 754, 6145
• EvenFasterSumExtensions: 1557, 1561, 553, 1574

Answer 6

Hm, it really looks strange... My guess: You are calling .sum() on the variable pool with var type. As long as you are working on only one type (either list or array), the call to sum() is unambigous and can be optimized. By using a new class var is ambigous and must be resolved, so further calls will cause a performance hit. I do not have a compiler, so try to load another class which supports sum() and compare the times. If I am right, I would expect again a performance hit, but this time not so much.

Answer 7

In my opinion that's caching (because of read ahead). First time you access an array, many elements from it get into the cache at once (read ahead). This prefetching mechanism expects the program will be likely accessing memory near theaddress requested.

Further calls already benefit from this (provided the array fit into the cache). When you change the method, the cache is invalidated and you need to get everything again from memory.

so calling: list, array, list, array, list, array should be slower than: list,list,list,array,array,array

But this is not deterministic from the programmer point of view, as you don't know the state of the cache or other units affecting caching decisions.