foreach and traditional for-loop with List in C#

Question

In C#, I just found out there's no such thing like an iterator of C++ or Java. In C++, I was advised not to iterate Linked Lists with indices because there would be a performance impact accessing from the first node on every loop. But it seems that I got only two choices in C#. Traditional for-loop VS foreach.

Is it different in C#? No performance issues with for-loop unlike in C++?

I also heard foreach creates every new variable in every loop iteration like in Java so I don't know which one would fit for low-end mobile phones.

Answer 1

This doesn't answer your question completely, but still wanted to point out that this assumption is false:

In C#, I just found out there's no such thing like an iterator of C++ or Java

It's called an enumerator in C#, see IEnumerator<T>.

Also consider this code sample using a traditional for-loop:

static void Main(string[] args)
{
    var data = new List<int> { 7, 10, 0 };
    for (var it = data.GetEnumerator(); it.MoveNext(); )
    {
        Console.WriteLine(it.Current);
    }
}

Anyway, I don't think anyone is iterating a list or IEnumerable like in this sample :)

Answer 2

There is a concept of iterator in C#, it's IEnumerable<T>, and it can provide sequential access to a collection.

List<T> and LinkedList<T> both implement this interface, and there is no performance penalty associated with algorithmic complexity of the indexing operation in both cases.

As a side note, the LinkedList<T> has no benefit of fast append operation in .NET, since List<T> has O(1) amortized time when adding an item to the end of the list, and List<T> makes less pressure on GC, because it's backed by array storage growing exponentially when needed, so you end up using List<T> most of the time.

As for the performance of indexed access of List<T> and 'same variable' issue, i think following code demonstrates the usage scenarios.

In the 'same variable' check, you can see that in case of 'for' the variable is in outer scope, and for the foreach it's in the inner scope for the iterator block in recent compiler versions (need to check which version changed this). It's very important in case you make a closure, and the code demonstrates it.

void Main()
{
    var n = 10000000;
    var list = Enumerable.Range(0, n).ToList();

    var array = list.ToArray();

    Test(TestForeach, list, "foreach - List");
    Test(TestFor, list, "for - List");

    Test(TestForeach, array, "foreach - Array");
    Test(TestFor, array, "for - Array");

    TestSameVariableFor();
    TestSameVariableForeach();
}

void TestSameVariableFor()
{
    var sum = 0;
    List<Action> actions = new List<Action>();
    for (var i = 0; i < 2; i++)
    {
        actions.Add(() => sum += i);
    }

    foreach (var a in actions)
    {
        a();
    }

    Console.WriteLine("For - Sum is {0}", sum);
}

void TestSameVariableForeach()
{
    var sum = 0;
    List<Action> actions = new List<Action>();
    foreach (var i in Enumerable.Range(0, 2))
    {
        actions.Add(() => sum += i);
    }

    foreach (var a in actions)
    {
        a();
    }

    Console.WriteLine("Foreach - Sum is {0}", sum);
}

void Test(Action<List<int>> action, List<int> list, string what)
{
    var sw = Stopwatch.StartNew();
    action(list);
    sw.Stop();
    Console.WriteLine("Elapsed {0}, {1}", sw.ElapsedMilliseconds, what);
    Console.WriteLine();
}

void Test(Action<int[]> action, int[] list, string what)
{
    var sw = Stopwatch.StartNew();
    action(list);
    sw.Stop();
    Console.WriteLine("Elapsed {0}, {1}", sw.ElapsedMilliseconds, what);
    Console.WriteLine();
}

void TestFor(List<int> list)
{
    long sum = 0;

    var count = list.Count;
    for (var i = 0; i < count; i++)
    {
        sum += i;
    }

    Console.WriteLine(sum);
}

void TestForeach(List<int> list)
{
    long sum = 0;

    foreach (var i in list)
    {
        sum += i;
    }

    Console.WriteLine(sum);
}

void TestFor(int[] list)
{
    long sum = 0;

    var count = list.Length;
    for (var i = 0; i < count; i++)
    {
        sum += i;
    }

    Console.WriteLine(sum);
}

void TestForeach(int[] list)
{
    long sum = 0;

    foreach (var i in list)
    {
        sum += i;
    }

    Console.WriteLine(sum);
}

Output:

49999995000000
Elapsed 37, foreach - List

49999995000000
Elapsed 6, for - List

49999995000000
Elapsed 7, foreach - Array

49999995000000
Elapsed 6, for - Array

For - Sum is 4
Foreach - Sum is 1

Update: Here is the post describing the foreach semantics change: Is there a reason for C#'s reuse of the variable in a foreach?