Foreach Performance Considerations in DotNet (C#)

The .Net System.Collections.Generic offers the IEnumerable<T> interface for collections. IEnumerable is the base interface for all non-generic collections that can be enumerated. This interface has the method GetEnumerator() that returns an enumerator, allowing the code to traverse the collection - and is agnostic of the underlying structure (e.g., trees, linked lists or arrays).

There are several ways to access items in collections. For Lists and Arrays (the most common collections), there is for, foreach, and the direct use of the enumerator. Each choice will have several performance implications.
Let's try a few approaches to implementation that will demonstrate the differences:

/// <summary>
/// Runs a test of each Loop given a number of items
/// </summary>
/// <param name="numberOfItems">The number of items</param>
/// <returns>Returns an array of results</returns>
public static long[] Run(int numberOfItems)
{
    var ret = new long[6];
    var sw = new System.Diagnostics.Stopwatch();
    var testList = MakeTestList(numberOfItems);

    // for loop on List
    var current = 0;
    sw.Start();
    for (int i = 0; i < numberOfItems; i++)
    {
        current += testList[i];
    }
    sw.Stop();
    ret[0] = sw.Elapsed.Ticks;

    // foreach loop on List
    current = 0;
    sw.Restart();
    foreach (var val in testList)
    {
        current += val;
    }
    sw.Stop();
    ret[1] = sw.Elapsed.Ticks;

    // enumerator MoveNext on List
    current = 0;
    sw.Restart();
    var enumerator = testList.GetEnumerator();
    while (enumerator.MoveNext())
    {
        current += enumerator.Current;
    }
    sw.Stop();
    ret[2] = sw.Elapsed.Ticks;

    var testArray = MakeTestArray(numberOfItems);
    current = 0;
    // for loop on Array
    sw.Restart();
    for (int i = 0; i < numberOfItems; i++)
    {
        current += testArray[i];
    }
    sw.Stop();
    ret[3] = sw.Elapsed.Ticks;

    current = 0;
    // foreach loop on Array
    sw.Restart();
    foreach (var val in testArray)
    {
        current += val;
    }
    sw.Stop();
    ret[4] = sw.Elapsed.Ticks;

    // enumerator MoveNext on Array
    current = 0;
    sw.Restart();
    var aenumerator = testArray.GetEnumerator();
    while (aenumerator.MoveNext())
    {
        current += (int)aenumerator.Current;
    }
    sw.Stop();
    ret[5] = sw.Elapsed.Ticks;

    return ret;
}

Here is the average of 30 runs (all times in Ticks):

Average Time (in ticks) to access N number of items

Let's normalize the times to ticks per item, shall we?

Normalized Average Time (with respect to ticks / item)

Visually, this might make more sense on a log2 - log2 plot...

These results are really interesting. First we see that for and foreach loops on Arrays are fastest. This should stand to reason as arrays use sequential memory layout - but here is the strange part: calling the MoveNext() on the array is by far the slowest (like 36x slower). Using the enumerator's MoveNext() on the List is slower than calling foreach, but not by much. The moral of the story is not to use the enumerator with MoveNext() as it is always slower.

The difference between the Array's enumerator vs the List's enumerator is surprising. How is that possible? Let's look at the source code...

// List implementation
public bool MoveNext()
{
	List<T> list = _list;
	if (_version == list._version && (uint)_index < (uint)list._size)
	{
		_current = list._items[_index];
		_index++;
		return true;
	}
	if (_version != _list._version)
	{
		ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
	}
	_index = _list._size + 1;
	_current = default(T);
	return false;
}

// Array implementation
public bool MoveNext()
{
	if (_complete)
	{
		index = endIndex;
		return false;
	}
	index++;
	int rank = array.Rank;
	_indices[rank - 1]++;
	for (int num = rank - 1; num >= 0; num--)
	{
		if (_indices[num] > array.GetUpperBound(num))
		{
			if (num == 0)
			{
				_complete = true;
				break;
			}
			for (int i = num; i < rank; i++)
			{
				_indices[i] = array.GetLowerBound(i);
			}
			_indices[num - 1]++;
		}
	}
	return !_complete;
}

Does this difference explain the 16x difference in speed? Sure. .Net's Array allows for partitioning of the Array across several allocations of memory - which makes sense for large data sets where there might not be a continuous allocation available in that size. A list doesn't have this consideration as each element does not need to be adjacent in memory - so there is only one case to handle. This additional complexity causes overhead in the enumerator.