Performance of value-type vs reference-type enumerators
In a previous article I focused on
Enumerable.Empty() as it’s the simplest possible implementation of
IEnumerable. I used my own version of the code that is easier to understand, compared to the one currently found in LINQ.
A recent merge request in the dotnet/corefx repository changes it to something very close to my version. The difference is that they use a singleton of a reference-type that implements both
IEnumerator. This is only possible because
Empty<T> is immutable but very interesting.
Given that, previously all the enumerators in the BCL were value-types for performance reasons, I was curious about this change.
Looking into this, I realised there are many possible implementations of
Enumerable.Empty<T> and decided to benchmark the several versions I could come up with.
EmptyEnumerableStruct<T> is the minimal implementation that can be used in a
foreach as it uses ‘duck typing’.
It doesn’t have a
Dispose() method so a
finally block will not be used by the
It’s a value-type so, when used directly in a
foreach, no boxing will happen and all method calls will be direct (no virtual calls). It cannot be cast to
IEnumerable<T> as it doesn’t implement it.
EmptyEnumerableDisposableStruct<T> is a value-type and implements both
IEnumerator<T>. This forces also the implementation of
foreach use a
finally block just to call an empty
foreach will use the public methods which returns the types explicitly (not interfaces) so that no boxing or virtual calls will happen. If casted to
IEnumerable<T>, the explicit implementations will be used instead, where it will be boxed and method calls will be virtual. In either cases, the methods will return copies of the instances.
This is a version very close to the one found in the ‘master’ branch of ‘dotnet/corefx’ repository. It’s implemented here as it’s not yet released.
EmptyEnumerableClass<T> is a reference-type that implements
It implements a singleton pattern so that only one instance of the class is created per each type
T used. All method calls return a reference to this instance.
This is a reference-type that implements both
IEnumerator<T>. It differs from the previous implementation in that, it’s not fully optimised to this scenario and
MoveNext() doesn’t simply return
Uses the enumerator returned by an empty
List<T>(), currently available in .NET Core, which is a value-type. Also benchmarked is when casted to
IEnumerable<T>, boxing the enumerator.
Uses the enumerator returned by an empty
Array<T>(), currently available in .NET Core, which is a reference-type. Also benchmarked is when casted to
IEnumerable<T> (Althought it doesn’t cause a ‘boxing’, the performance is difference for reasons that I don’t know at this moment).
I created a benchmark using BenchmarkDotNet containing all these implementations and here we have the results:
- Having the
finallyblock makes no difference.
EmptyDisposableStruct<T>, that is a value-type, is 33x times faster than the
EmptyClass(the new LINQ version) but 2x slower when casted to
- Two instances of
EmptyDisposableStruct<T>are boxed into the heap (2 x 24B) when casted to
EmptyClass(the new LINQ version) uses references to instances previously allocated on the heap so there are no heap allocations during the benchmark method.
LinqEmpty(the current LINQ implementation) is based on
EmptyBoxedArrayso they have the same performance.
EmptyClass(the new LINQ version) is 30% faster than
LinqEmpty(the current LINQ implementation).
- The slowest is
EmptyDisposableStruct is much faster than
EmptyClass (the new LINQ version), the result of
Enumerable.Empty<T>() is usually returned by methods that output
IEnumerable<T>. This results in all value-typed implementation to end up ‘boxed’. There’s no much use for explicitly
Enumerable.Empty<T>(). The use of a reference-typed singleton seems to be a great call by the .NET team.
I hope you enjoyed this journey as much as I did. It’s not just for
Enumerable.Empty<T>(). These little tricks can be used in many other places but, always measure…