Fastest way to enumerate a List<T>

System.Collections.Generic.List<T> may be the most used collection in .NET. It is a generic collection that can be used to store any type of data. In this post, we'll see the different ways to enumerate a List<T>.

There are multiple ways to enumerate a List<T> in .NET. Not all of them are equal to each other in term of behavior and performance. You can enumerate the list faster if you accept tradeoffs!

#Using the foreach statement

List<T> list = new List<T>();
foreach (var item in list)
{
    // Do something
}

This is the most common way to iterate on a collection. The compiler will replace this loop with a call to GetEnumerator and MoveNext() methods:

List<T> list = new List<T>();
List<T>.Enumerator enumerator = list.GetEnumerator();
try
{
    while (enumerator.MoveNext())
    {
        T current = enumerator.Current;
    }
}
finally
{
    ((IDisposable)enumerator).Dispose();
}

The MoveNext method implementation ensure the list is not modified during the enumeration (source). If the list is modified, an InvalidOperationException with the message "Collection was modified after the enumerator was instantiated" is thrown by the MoveNext method. This mainly helps detecting multi-threading issues. However, this feature comes with a cost. Indeed, there is a check when accessing each item of the collection.

#Using the List<T>.ForEach method

List<T> list = new List<T>();
list.ForEach(item =>
{
    // Do something
});

The ForEach method knows internals of the List<T> and is able to optimize the enumeration. Indeed, it can iterate over the private array and the JIT may be able to remove bound checks. This method gives the same guarantee as when using the foreach keyword. So, it will throw an exception if the list is modified during the enumeration.

This method needs to call the delegate for each item. Calling a method has a low overhead, but it may be significant in a micro-benchmark compared to a foreach loop which would have its code inlined.

#Using the for statement

List<T> list = new List<T>();
for (int i = 0; i < list.Count; i++)
{
    var item = list[i];
    // Do something
}

Using a for loop, you don't ensure the collection is not modified during the enumeration. However, the indexer still need to check you don't access an invalid index (source). So, the performance should be a little bit better than the foreach loop as there is less checks.

#Using the CollectionsMarshal.AsSpan method

List<T> list = new List<T>();
foreach (var item in CollectionsMarshal.AsSpan(list))
{
    // Do something
}

The CollectionsMarshal.AsSpan method is unsafe and should be used only if you know what you're doing. CollectionsMarshal.AsSpan returns a Span<T> on the private array of List<T>. Iterating over a Span<T> is fast as the JIT uses the same tricks as for optimizing arrays. Using this method, it won't check the list is not modified during the enumeration.

As said, this method is unsafe and you may get weird behaviors if you don't know what you are doing. For instance, you may iterate over items that are not part of the list anymore in some cases. Let's see an example:

var list = new List<int>(capacity: 1);
list.Add(0); // list: [0]

var span = CollectionsMarshal.AsSpan(list);
span[0] = 1; // list: [1], span: [1]

// To add a new item, the list needs to increase its capacity
// => A new array is created and replace the existing List._items
// But the span still references the old array
// => ⚠️ Accessing the span won't access the actual list items!
list.Add(3); // list: [1, 3], span: [1]
list[0] = 2; // ⚠️ list: [2, 3], span: [1]
span[0] = 0; // ⚠️ list: [2, 3], span: [0]

As long as you don't modify the list while enumerating it, you should be fine.

#Benchmark

Let's benchmark the 4 methods using BenchmarkDotnet:

BenchmarkRunner.Run<ListBenchmark>();

public class ListBenchmark
{
    private List<int> _list = default!;

    [Params(10, 1_000, 10_000, 100_000, 1_000_000)]
    public int Size { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        _list = new List<int>(Size);
        for (var i = 0; i < Size; i++)
        {
            _list.Add(i);
        }
    }

    [Benchmark(Baseline = true)]
    public void Foreach()
    {
        foreach (var item in _list)
        {
        }
    }

    [Benchmark]
    public void List_Foreach()
    {
        _list.ForEach(_ => { });
    }

    [Benchmark]
    public void For()
    {
        for (var i = 0; i < _list.Count; i++)
        {
            _ = _list[i];
        }
    }

    [Benchmark]
    public void Foreach_Span()
    {
        foreach (var item in CollectionsMarshal.AsSpan(_list))
        {
        }
    }
}

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000
AMD Ryzen 7 5800X, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.100
  [Host]     : .NET 6.0.0 (6.0.21.52210), X64 RyuJIT
  DefaultJob : .NET 6.0.0 (6.0.21.52210), X64 RyuJIT

Unsurprisingly CollectionsMarshal.AsSpan is the fatest way to enumerate a List<T> when it's applicable. I was a bit surprised with the performance of List<T>.Foreach which is about 2.5 times slower than a foreach, but it makes sense as it has to call the delegate. In this benchmark there is no operation applied on list items, but in real scenario, this overhead should be negligible.

Do you have a question or a suggestion about this post? Contact me!