SYSK 132: Loop Performance Comparison — foreach vs. for


Do you think there is a performance difference between the following two loops?


foreach (int x in _data)


{


            . . .


}


 


vs.


for (int i = 0; i < _data.Count; i++)


{


            . . .


}


 


My tests show that foreach is slower than the for loop.  The larger the collection you’re looping through, the greater is the performance difference…


 


With 1 mln records, it’s about 2 times slower; at 10 mln records it’s about 3.5-4 times slower.  Having said that, we’re still talking about milliseconds; so in comparison with the other work your code is executing in the loop, the difference in the actual loop performance is negligible.


 

Comments (15)

  1. theCoach says:

    Below is a silly mock of of possible IL code. It looks to me that you would probably want to compare a collection of Objects rather than boxed ints.

    private static void Loop1()

    {

         foreach (int num1 in Program._data)

         {

         }

    }

    .method private hidebysig static void Loop1() cil managed

    {

         .maxstack 2

         .locals init (

               [0] int32 num1,

               [1] [mscorlib]System.Collections.IEnumerator enumerator1,

               [2] bool flag1,

               [3] [mscorlib]System.IDisposable disposable1)

         L_0000: nop

         L_0001: nop

         L_0002: ldsfld [mscorlib]System.Collections.IList TestLoops.Program::_data

         L_0007: callvirt instance [mscorlib]System.Collections.IEnumerator [mscorlib]System.Collections.IEnumerable::GetEnumerator()

         L_000c: stloc.1

         L_000d: br.s L_001d

         L_000f: ldloc.1

         L_0010: callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()

         L_0015: unbox.any int32

         L_001a: stloc.0

         L_001b: nop

         L_001c: nop

         L_001d: ldloc.1

         L_001e: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()

         L_0023: stloc.2

         L_0024: ldloc.2

         L_0025: brtrue.s L_000f

         L_0027: leave.s L_0040

         L_0029: ldloc.1

         L_002a: isinst [mscorlib]System.IDisposable

         L_002f: stloc.3

         L_0030: ldloc.3

         L_0031: ldnull

         L_0032: ceq

         L_0034: stloc.2

         L_0035: ldloc.2

         L_0036: brtrue.s L_003f

         L_0038: ldloc.3

         L_0039: callvirt instance void [mscorlib]System.IDisposable::Dispose()

         L_003e: nop

         L_003f: endfinally

         L_0040: nop

         L_0041: ret

         .try L_000d to L_0029 finally handler L_0029 to L_0040

    }

    private static void Loop2()

    {

         for (int num1 = 0; num1 < Program._data.Count; num1++)

         {

         }

    }

    .method private hidebysig static void Loop2() cil managed

    {

         .maxstack 2

         .locals init (

               [0] int32 num1,

               [1] bool flag1)

         L_0000: nop

         L_0001: ldc.i4.0

         L_0002: stloc.0

         L_0003: br.s L_000b

         L_0005: nop

         L_0006: nop

         L_0007: ldloc.0

         L_0008: ldc.i4.1

         L_0009: add

         L_000a: stloc.0

         L_000b: ldloc.0

         L_000c: ldsfld [mscorlib]System.Collections.IList TestLoops.Program::_data

         L_0011: callvirt instance int32 [mscorlib]System.Collections.ICollection::get_Count()

         L_0016: clt

         L_0018: stloc.1

         L_0019: ldloc.1

         L_001a: brtrue.s L_0005

         L_001c: ret

    }

  2. Adam says:

    What if you manually code the foreach loop as:

    for (x = _data.GetEnumerator(); x.MoveNext();)

    {

       …

    }

    Also, what type of collection were you iterating over? An array? The for() loop presumably calls Item() to get each member of the collection, which should be O(1) per iteration on arrays, but O(n) per iteration on lists. However, foreach() should be O(1) per iteration (albeit a slower O(1) than for for()) on both types of collection.

    For that reason, foreach() *should* be faster than for() for large lists. Possibly a lot faster.

  3. Adam says:

    Coach:

    You should probably change the for loop to:

    for (int i = 0; i < Program._data.Count; ++i)

    {

       int num1 = Program._data.Item(i);

    }

    so that you access each item in the collection in both loops. That will probably make a fairer comparison.

  4. hasanib says:

    I would have assumed the foreach would have been slower do to overheard.. boxing of int32, plus the another class that implemenets IEnumerator is being used to perform the numeration. I wasn’t expecting it to 2x and 4x slower though :/

  5. theCoach says:

    Adam is obviously correct. Also to compare objects to objects rather than boxed ints in one case.

    Here is a silly little program with IL in comments. Would you really use statics? No.

    Probably the way to do this would to run it in Performce testing tools (I did in VS2005), but the exporting is more than I can do right now.

    using System;

    using System.Collections.Generic;

    using System.Text;

    using System.Collections;

    namespace TestLoops

    {

       class Program

       {

           static object obj;

           static IList _dataObjs = new System.Collections.ArrayList();

           static int ListSize;

           static string loopType = "ForEach";

           static void Main(string[] args)

           {

               ListSize = Convert.ToInt32(args[0]);

               LoadList();

               loopType = args[1];

               if (loopType == "ForEach")

               {

                   ForEachLoop(_dataObjs);

               }

               else

               {

                   ForLoop(_dataObjs);

               }

           }

           // For Each Loop

           static void ForEachLoop(IList data)

           {

               foreach (object x in data)

               {

                   obj = x;

               }

           }

    //.method private hidebysig static void ForEachLoop([mscorlib]System.Collections.IList data) cil managed

    //{

    //      .maxstack 1

    //      .locals init (

    //            [0] object obj1,

    //            [1] [mscorlib]System.Collections.IEnumerator enumerator1,

    //            [2] [mscorlib]System.IDisposable disposable1)

    //      L_0000: ldarg.0

    //      L_0001: callvirt instance [mscorlib]System.Collections.IEnumerator [mscorlib]System.Collections.IEnumerable::GetEnumerator()

    //      L_0006: stloc.1

    //      L_0007: br.s L_0016

    //      L_0009: ldloc.1

    //      L_000a: callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()

    //      L_000f: stloc.0

    //      L_0010: ldloc.0

    //      L_0011: stsfld object TestLoops.Program::obj

    //      L_0016: ldloc.1

    //      L_0017: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()

    //      L_001c: brtrue.s L_0009

    //      L_001e: leave.s L_0031

    //      L_0020: ldloc.1

    //      L_0021: isinst [mscorlib]System.IDisposable

    //      L_0026: stloc.2

    //      L_0027: ldloc.2

    //      L_0028: brfalse.s L_0030

    //      L_002a: ldloc.2

    //      L_002b: callvirt instance void [mscorlib]System.IDisposable::Dispose()

    //      L_0030: endfinally

    //      L_0031: ret

    //      .try L_0007 to L_0020 finally handler L_0020 to L_0031

    //}

           // For Loop

           static void ForLoop(IList data)

           {

               for (int i = 0; i < data.Count; i++)

               {

                   obj = data[i];

               }

           }

    //.method private hidebysig static void ForLoop([mscorlib]System.Collections.IList data) cil managed

    //{

    //      .maxstack 2

    //      .locals init (

    //            [0] int32 num1)

    //      L_0000: ldc.i4.0

    //      L_0001: stloc.0

    //      L_0002: br.s L_0014

    //      L_0004: ldarg.0

    //      L_0005: ldloc.0

    //      L_0006: callvirt instance object [mscorlib]System.Collections.IList::get_Item(int32)

    //      L_000b: stsfld object TestLoops.Program::obj

    //      L_0010: ldloc.0

    //      L_0011: ldc.i4.1

    //      L_0012: add

    //      L_0013: stloc.0

    //      L_0014: ldloc.0

    //      L_0015: ldarg.0

    //      L_0016: callvirt instance int32 [mscorlib]System.Collections.ICollection::get_Count()

    //      L_001b: blt.s L_0004

    //      L_001d: ret

    //}

           static void LoadList()

           {

               

               for (int i = 0; i < ListSize; i++)

               {

                   _dataObjs.Add(new Object());

               }

           }

       }

    }

    For what it is worth, here is some performce data that I got – Showing Elapsed Inclusive Numbers

    Loop 1000        10000       100000

    Foreach 0.710204    5.010083    45.182694

    For     0.396586    6.634075    50.831526

    Very Quickly Done. I suggest running it yourself if interested – and making modifications to the use non-static scenarios.

  6. Peter Ritchie says:

    My tests show that a foreach loop of a value collection (int array in my test) is virually the same speed, an average difference of less than a second (foreach being slower) for 1 billion iterations.

    Object arrays, on the other hand are quicker with a foreach loop rather than a for loop by a difference of over 5 seconds for 1 billion iterations, foreach being ~45% faster.

  7. irenak says:

    Below is the actual test case I was using:

    public partial class Form1 : Form

    {

       long[] _data = new long[10000000];

       public Form1()

       {

           InitializeComponent();

           for (long i = 0; i < _data.Length; i++)

           {

               _data[i] = i;

           }

       }

       private void button1_Click(object sender, EventArgs e)

       {

           long t1, t2;

           long value;

           

           t1 = DateTime.Now.Ticks;            

           foreach (long item in _data)

           {

               value = item;

           }

           t2 = DateTime.Now.Ticks;

           System.Diagnostics.Debug.WriteLine(string.Format("foreach took {0} ticks", (t2-t1)));

           t1 = DateTime.Now.Ticks;            

           for (long i = 0; i < _data.Length; i++)

           {

               value = _data[i];

           }

           t2 = DateTime.Now.Ticks;

           System.Diagnostics.Debug.WriteLine(string.Format("for took {0} ticks", (t2-t1)));

       }

    }

    The result:

       foreach took 2804032 ticks

       for took 1101584 ticks

    As you can see, in both cases I get to the actual object in the array, so, I do believe, that the comparison is "fair".

  8. Peter Ritchie says:

    I went so far as to yank the call to _data.Length (or my equivalent) out of the loop into a local variable, and the for loop is still about the same or slower over 1 billion iterations on my computer

  9. theCoach says:

    Tone is hard to guage in posts. So I just want to be clear that none of my posts were meant as criticism of the original post. My posts are here because I found the topic interesting, something rather fundamental, and something I did not know about.

    I just want to add that I recently had to rebuild my Feed Subscriptions. In the past I had always liked the posts titled "SYSK:" that I got as part of blogs.msdn feed. So, when rebuilding, I now have this feed separated out, and have subscribed to the comment feed for this post – great feature! and great posts. Thanks for the great posts!

  10. Peter Ritchie says:

    Clearly boxing of value types is affecting the results

    Using Object instead of long (Int64), I get the following results with your test case, where foreach is the same speed as for (5 runs):

           mean    median  mode

    foreach 468,756 468,756 468,756

    for     406,255 468,756 468,756

    I modified your test case as follows (changing TEST_TYPE where appropriate):

    using TEST_TYPE = System.Object;

    //…

    TEST_TYPE[] arr = new TEST_TYPE[10000000];

    for (int i = 0; i < arr.Length; i++)

    {

    arr[i] = new TEST_TYPE();

    }

    long t1, t2;

    TEST_TYPE value;

    int c = 0;

    t1 = DateTime.Now.Ticks;

    foreach (TEST_TYPE item in arr)

    {

    value = item;

    }

    t2 = DateTime.Now.Ticks;

    System.Diagnostics.Debug.WriteLine(string.Format("foreach took {0} ticks", (t2 – t1)));

    c = 0;

    t1 = DateTime.Now.Ticks;

    for (int i = 0; i < arr.Length; i++)

    {

    value = arr[i];

    }

    t2 = DateTime.Now.Ticks;

    System.Diagnostics.Debug.WriteLine(string.Format("for took {0} ticks", (t2 – t1)));

  11. irenak says:

    No worries.  I value all feedback — positive and negative!

  12. irenak says:

    Makes sense.  Thanks for the post.

  13. Peter Ritchie says:

    No Problem.  I just noticed the formatting of the code got lost, sorry about that.

  14. Ir0nClad says:

    C# vs VB.NET -> interesting

    VB code:

    Imports OBJ_T = System.Object

    Module Module1

    Sub Main()

    Dim arr(10000000) As OBJ_T

    For i As Integer = 0 To UBound(arr)

    arr(i) = New OBJ_T

    Next

    Dim t1, t2 As Long

    Dim value As OBJ_T

    t1 = DateTime.Now.Ticks

    For Each item As OBJ_T In arr

    value = item

    Next

    t2 = DateTime.Now.Ticks

    System.Diagnostics.Debug.WriteLine(String.Format("foreach: {0}", t2 – t1))

    t1 = DateTime.Now.Ticks

    For i As Integer = 0 To UBound(arr)

    value = arr(i)

    Next

    t2 = DateTime.Now.Ticks

    System.Diagnostics.Debug.WriteLine(String.Format("for: {0}", t2 – t1))

    Dim ii As Integer = 0

    t1 = DateTime.Now.Ticks

    For ii = 0 To UBound(arr)

    value = arr(ii)

    Next

    t2 = DateTime.Now.Ticks

    System.Diagnostics.Debug.WriteLine(String.Format("for same mem: {0}", t2 – t1))

    End Sub

    End Module

    C# code:

    using System;

    using TEST_TYPE = System.Object;

    namespace ConsoleApplication1

    {

       class Program

       {

           static void Main(string[] args)

           {

               //…

               TEST_TYPE[] arr = new TEST_TYPE[10000000];

               for (int i = 0; i < arr.Length; i++)

                   arr[i] = new TEST_TYPE();

               long t1, t2;

               TEST_TYPE value;

               t1 = DateTime.Now.Ticks;

               foreach (TEST_TYPE item in arr)

                   value = item;

               t2 = DateTime.Now.Ticks;

               System.Diagnostics.Debug.WriteLine(string.Format("foreach: {0}", t2-t1));

               t1 = DateTime.Now.Ticks;

               for (int i = 0; i < arr.Length; i++)

                   value = arr[i];

               t2 = DateTime.Now.Ticks;

               System.Diagnostics.Debug.WriteLine(string.Format("for: {0}", t2-t1));

               int ii = 0;

               t1 = DateTime.Now.Ticks;

               for (ii = 0; ii < arr.Length; ii++)

                   value = arr[ii];

               t2 = DateTime.Now.Ticks;

               System.Diagnostics.Debug.WriteLine(string.Format("for same mem: {0}", t2 – t1));

           }

       }

    }

    Results:

    VB:

    foreach: 7812500

    for: 3750000

    for same mem: 3906250

    C#:

    foreach: 781250

    for: 468750

    for same mem: 468750