CODEWITHSUNDEEP
c#performanceloopsfor-loopforeach
Lolop
Lolop

Reputation: 67

Iterating LinkedListed Performance C#

I am currently working on something that requires a hierarchy like design (Much like that in unity... In fact i'm basically just making a copy of unity on top of unity as a learning experience), which requires a lot of inserting/moving around of objects inside a list. For this reason i decided to go with a LinkedList to store all the hierarchy objects (First time i've ever had a use for a ListList).

I decided to look at which method of looping over a linked list was the most efficient. I know i'm probably micro optimizing, but i generally learn new things by testing stuff out, and the results of my test surprised me quite a bit, so i was hoping someone could shed some light on it.

(I'm no expert at setting up performance tests, but this sort of set up generally gives me a good idea of performance differences)

The Test: With 10 integers in the list, and another with 100,000

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ConsoleApplication1
{
  class Program
  {

    private static Stopwatch timer = new Stopwatch();

    static void Main(string[] args)
    {
        /// Initialization

        var _linkedList = new LinkedList<int>();

        for (int i = 0; i < 10; i++)
            _linkedList.AddLast(i);


        /// Test 1

        timer.Start();

        for (var _node = _linkedList.First; _node != _linkedList.Last; _node = _node.Next)
            FuncFoo(_node.Value);

        timer.Stop();

        Console.WriteLine("For Loop: " + timer.Elapsed);

        timer.Reset();


        /// Test 2

        timer.Start();

        foreach (var _int in _linkedList)
            FuncFoo(_int);

        timer.Stop();

        Console.WriteLine("Foreach Loop: " + timer.Elapsed);

        timer.Reset();


        /// Test 3

        timer.Start();

        var _listNode = _linkedList.First;

        while (_listNode != _linkedList.Last)
        {
            FuncFoo(_listNode.Value);
            _listNode = _listNode.Next;
        }

        timer.Stop();

        Console.WriteLine("While Loop: " + timer.Elapsed);

        timer.Reset();


        ///End

        Console.Write("Press any key to continue...");

        Console.ReadKey();
    }

    private static void FuncFoo(int _num)
    {
        _num = (int)Math.Sqrt(1 + 2 + 3 + 4 + 5) * _num;
    }
  }
}

Results: 10 integers in the list

For Loop: 0.0002371
Foreach Loop: 0.0002880
While Loop: 0.0000002

Results: 100,000 integers in the list

For Loop: 0.0013548
Foreach Loop: 0.0015256
While Loop: 0.0013436

So 2 things i'm unsure about.

  1. Why is the for loop so much slower than the while loop? I thought that a for loop functioned as a while loop behind the scenes? (I understand why the foreach loop is slightly slower in all cases)

  2. Why is it that the while loop becomes less efficient as more elements are added to the linked list? I figured they would all more or less stay the same ratio apart (Like the for & foreach loops did). But to see the while loop seemingly lose performance (Or for/foreach gain performance?) confuses me.

I'm assuming my code is probably non functional as a test (In which case i would like to know what i did wrong/why, so i know how to make more reliable tests in the future). But in the case that it is a valid test, i would like to know what causes these seemingly strange results (Even if the performance difference wont make a difference in my code).

Upvotes: 0

Views: 121

Answers (1)

Vadim Martynov
Vadim Martynov

Reputation: 8892

First of all let make your test more representative by increase iterations count from one to 1 million. Also add not recorded iterations for each test to make a chance for JIT compiler to optimize our code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {

        private static Stopwatch timer = new Stopwatch();

        static void Main(string[] args)
        {
            /// Initialization

            var _linkedList = new LinkedList<int>();

            for (int i = 0; i < 10; i++)
                _linkedList.AddLast(i);

            for (int x = 0; x < 1000000; x++)
                for (var _node = _linkedList.First; _node != _linkedList.Last; _node = _node.Next)
                    FuncFoo(_node.Value);
            for (int x = 0; x < 1000000; x++)
                foreach (var _int in _linkedList)
                    FuncFoo(_int);
            for (int x = 0; x < 1000000; x++)
            {
                var _listNode = _linkedList.First;
                while (_listNode != _linkedList.Last)
                {
                    FuncFoo(_listNode.Value);
                    _listNode = _listNode.Next;
                }
            }

            /// Test 1

            timer.Start();

            for (int x = 0; x < 1000000; x++)
                for (var _node = _linkedList.First; _node != _linkedList.Last; _node = _node.Next)
                    FuncFoo(_node.Value);

            timer.Stop();

            Console.WriteLine("For Loop: " + timer.Elapsed);

            timer.Reset();


            /// Test 2

            timer.Start();

            for (int x = 0; x < 1000000; x++)
                foreach (var _int in _linkedList)
                    FuncFoo(_int);

            timer.Stop();

            Console.WriteLine("Foreach Loop: " + timer.Elapsed);

            timer.Reset();


            /// Test 3

            timer.Start();



            for (int x = 0; x < 1000000; x++)
            {
                var _listNode = _linkedList.First;
                while (_listNode != _linkedList.Last)
                {
                    FuncFoo(_listNode.Value);
                    _listNode = _listNode.Next;
                }
            }

            timer.Stop();

            Console.WriteLine("While Loop: " + timer.Elapsed);

            timer.Reset();


            ///End

            Console.Write("Press any key to continue...");

            Console.ReadKey();
        }

        private static void FuncFoo(int _num)
        {
            _num = (int)Math.Sqrt(1 + 2 + 3 + 4 + 5) * _num;
        }
    }
}

And how wow! There is more actual result:

For Loop: 00:00:00.2793502 
Foreach Loop: 00:00:00.3588778 
While Loop: 00:00:00.2660378

As we can see for loop and while loop has the same result. It's because their MSIL code is almost the same too:

IL_0115: callvirt instance class [System]System.Collections.Generic.LinkedListNode`1<!0> class [System]System.Collections.Generic.LinkedList`1<int32>::get_First()
IL_011a: stloc.s _listNode
IL_011c: br.s IL_0136
// loop start (head: IL_0136)
    IL_011e: nop
    IL_011f: ldloc.s _listNode
    IL_0121: callvirt instance !0 class [System]System.Collections.Generic.LinkedListNode`1<int32>::get_Value()
    IL_0126: call void ConsoleApplication1.Program::FuncFoo(int32)
    IL_012b: nop
    IL_012c: ldloc.s _listNode
    IL_012e: callvirt instance class [System]System.Collections.Generic.LinkedListNode`1<!0> class [System]System.Collections.Generic.LinkedListNode`1<int32>::get_Next()
    IL_0133: stloc.s _listNode
    IL_0135: nop

    IL_0136: ldloc.s _listNode
    IL_0138: ldloc.0
    IL_0139: callvirt instance class [System]System.Collections.Generic.LinkedListNode`1<!0> class [System]System.Collections.Generic.LinkedList`1<int32>::get_Last()
    IL_013e: ceq
    IL_0140: ldc.i4.0
    IL_0141: ceq
    IL_0143: stloc.s CS$4$0000
    IL_0145: ldloc.s CS$4$0000
    IL_0147: brtrue.s IL_011e
// end loop

ForEach loop runs longer because its mechanism creates new instance of Enumerator which implements IDisposable and should be disposed on the end of the loop. Actual MSIL code looks like that: 

IL_009c: ldloc.0
IL_009d: callvirt instance valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<!0> class [System]System.Collections.Generic.LinkedList`1<int32>::GetEnumerator()
IL_00a2: stloc.s CS$5$0001
.try
{
    IL_00a4: br.s IL_00b5
    // loop start (head: IL_00b5)
        IL_00a6: ldloca.s CS$5$0001
        IL_00a8: call instance !0 valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<int32>::get_Current()
        IL_00ad: stloc.3
        IL_00ae: ldloc.3
        IL_00af: call void ConsoleApplication1.Program::FuncFoo(int32)
        IL_00b4: nop

        IL_00b5: ldloca.s CS$5$0001
        IL_00b7: call instance bool valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<int32>::MoveNext()
        IL_00bc: stloc.s CS$4$0000
        IL_00be: ldloc.s CS$4$0000
        IL_00c0: brtrue.s IL_00a6
    // end loop

    IL_00c2: leave.s IL_00d3
} // end .try
finally
{
    IL_00c4: ldloca.s CS$5$0001
    IL_00c6: constrained. valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<int32>
    IL_00cc: callvirt instance void [mscorlib]System.IDisposable::Dispose()
    IL_00d1: nop
    IL_00d2: endfinally
} // end handler

As you can see this MSIL is totally different because it uses Enumerator.MoveNext method instead of LinkedListNode.get_Next() and creates try block that affects the performance because there is a cost associated with exception handling on some platforms.

Also, JIT doesn't perform optimization on 'try' blocks and this will affect your performance too.

Upvotes: 2

Related Questions