Performance of value-type vs reference-type enumerators

Warp Speed by aalmada

EDIT: Updated to .NET 8 and improved content.

Introduction

The C# compiler generates different code for the foreach keyword, based on the collection type. One of the things that it looks for is if the type of enumerator used is a reference-type or a value-type. This can have major implications in the performance of the collection iteration.

NOTE: It also generates different code in the case of arrays or spans. Check my other article “Array iteration performance in C#” to learn about those cases.

A collection to be enumerable using a foreach loop has to implement a parameter-less method GetEnumerator(). The method must return a type that implements a property Current, that return the type of the item, and a parameter-less method MoveNext(), that return bool.

The type of the enumerator can be a value-type (struct) or a reference-type (class or interface).

Reference-type enumerators

Returning a reference type is the most common. Most collections implement IEnumerable<T> and its GetEnumerator() method returns IEnumerator<T>, which is an interface.

Enumerable.Range() is one example of these enumerables. Let's use a foreach to iterate all the values of the collection:

var source = Enumerable.Range(0, 10);
foreach(var item in source)
    Console.WriteLine(item);

You can see in SharpLab that the compiler converts this code to something equivalent to the following:

IEnumerator<int> enumerator = Enumerable.Range(0, 10).GetEnumerator();
try
{
    while (enumerator.MoveNext())
    {
        Console.WriteLine(enumerator.Current);
    }
}
finally
{
    enumerator?.Dispose();
}

It calls GetEnumerator() to get an instance of the enumerator. Notice that the enumerator is of type IEnumerator<int>, an interface.

It then uses a while loop with enumerator.MoveNext() as condition. Insidoe of the loop, it calls enumerator.Current to get the item.

NOTE: Because the IEnumerable<T> derives from IDisposable, it calls enumerator.Dispose() inside a finally to guarantee that it’s called even if an exception is thrown inside the loop.

You can also see in SharpLab the IL generated:

IL_0000: ldc.i4.0
IL_0001: ldc.i4.s 10
IL_0003: call class [System.Runtime]System.Collections.Generic.IEnumerable`1<int32> [System.Linq]System.Linq.Enumerable::Range(int32, int32)
IL_0008: callvirt instance class [System.Runtime]System.Collections.Generic.IEnumerator`1<!0> class [System.Runtime]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator()
IL_000d: stloc.0
.try
{
    // sequence point: hidden
    IL_000e: br.s IL_001b
    // loop start (head: IL_001b)
        IL_0010: ldloc.0
        IL_0011: callvirt instance !0 class [System.Runtime]System.Collections.Generic.IEnumerator`1<int32>::get_Current()
        IL_0016: call void [System.Console]System.Console::WriteLine(int32)

        IL_001b: ldloc.0
        IL_001c: callvirt instance bool [System.Runtime]System.Collections.IEnumerator::MoveNext()
        IL_0021: brtrue.s IL_0010
    // end loop

    IL_0023: leave.s IL_002f
} // end .try
finally
{
    // sequence point: hidden
    IL_0025: ldloc.0
    IL_0026: brfalse.s IL_002e

    IL_0028: ldloc.0
    IL_0029: callvirt instance void [System.Runtime]System.IDisposable::Dispose()

    // sequence point: hidden
    IL_002e: endfinally
} // end handler

Notice that the instruction callvirt is used to call the MoveNext() and Current.

Value-type enumerators

Collections can implement a GetEnumerator() method that returns a value-type enumerator.

NOTE: Even if the collection implements IEnumerable<T>, it’s possible to make it an explicit implementation, and add a public implementation that returns the value-type enumerator.

List<T> is one example of these enumerables. Let's use a foreach to iterate all the values of the collection:

var source = new List<int>();
foreach(var item in source)
    Console.WriteLine(item);

You can see in SharpLab that the compiler converts this code to something equivalent to the following:

List<int>.Enumerator enumerator = new List<int>().GetEnumerator();
try
{
    while (enumerator.MoveNext())
    {
        Console.WriteLine(enumerator.Current);
    }
}
finally
{
    ((IDisposable)enumerator).Dispose();
}

The code is very similar to the case of reference-type enumerator but notice that now the enumerator type is of type List<int>.Enumerator. You can see in GitHub that this is a value-type.

You can also see in SharpLab the IL generated:

IL_0000: newobj instance void class [System.Collections]System.Collections.Generic.List`1<int32>::.ctor()
IL_0005: callvirt instance valuetype [System.Collections]System.Collections.Generic.List`1/Enumerator<!0> class [System.Collections]System.Collections.Generic.List`1<int32>::GetEnumerator()
IL_000a: stloc.0
.try
{
    // sequence point: hidden
    IL_000b: br.s IL_0019
    // loop start (head: IL_0019)
        IL_000d: ldloca.s 0
        IL_000f: call instance !0 valuetype [System.Collections]System.Collections.Generic.List`1/Enumerator<int32>::get_Current()
        IL_0014: call void [System.Console]System.Console::WriteLine(int32)

        IL_0019: ldloca.s 0
        IL_001b: call instance bool valuetype [System.Collections]System.Collections.Generic.List`1/Enumerator<int32>::MoveNext()
        IL_0020: brtrue.s IL_000d
    // end loop

    IL_0022: leave.s IL_0032
} // end .try
finally
{
    // sequence point: hidden
    IL_0024: ldloca.s 0
    IL_0026: constrained. valuetype [System.Collections]System.Collections.Generic.List`1/Enumerator<int32>
    IL_002c: callvirt instance void [System.Runtime]System.IDisposable::Dispose()
    IL_0031: endfinally
} // end handler

Notice that the instruction call is used to call the enumerator methods.

NOTE: The instruction callvirt is used to call Dispose() but, because of the contrained in the line before, the assembly generated will be similar to the call instruction.

Benchmarking

Let’s use BenchmarkDotNet to run the following benchmarks:

public class AssignmentBoxing
{
    List<int>? list;
    IEnumerable<int>? enumerable;

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

    [GlobalSetup]
    public void GlobalSetup()
    {
        list = System.Linq.Enumerable.Range(0, Count).ToList();
        enumerable = list;
    }

    [Benchmark(Baseline = true)]
    public int Enumerable()
    {
        var sum = 0;
        foreach (var item in enumerable!)
            sum += item;
        return sum;
    }

    [Benchmark]
    public int List()
    {
        var sum = 0;
        foreach (var item in list!)
            sum += item;
        return sum;
    }
}

It compares the performance of iterating a List<int> with 100 and 10.000 items when cast to IEnumerable<int> (reference-type enumerator) and when directly using List<int> (value-type enumerator).

I used a configuration to test on .NET 6, .NET 7, and .NET 8 (all “modern” NET versions).

Notice that the difference ranges from 300% and 700%. It also doesn’t allocate an enumerator in the heap.

One other thing to note is that the performance improves significantly between .NET 7 and .NET 8. That’s one good reason to upgrade to .NET 8 as soon as possible.

Conclusions

Virtual calls are required in types that support inheritance. Value types in .NET do not support inheritance so all methods are called directly. When a value-type is cast to an interface, it’s copied into the heap and converted to a reference type (boxing).

Iterating a collection means calling MoveNext() and Current for each item. Using a value-type enumerator may make a huge difference in performance for large collections.

Avoid casting to interfaces your internal collections. The use of var for local variables guarantees the correct type and makes it easier when refactoring.

On public APIs, consider using immutable collections. You can find these in the System.Collections.Immutable namespace. You can also use an immutable wrapper for arrays provided in the NetFabric package.

If you implement a new collection type, don’t forget to provide a value-type enumerator.