Performance of value-type vs reference-type enumerators

Enumerable.Empty<T>()

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 IEnumerable and 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.

EmptyStruct

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 try/finally block will not be used by the foreach.

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.

EmptyDisposableStruct and EmptyBoxedDisposableStruct

EmptyEnumerableDisposableStruct<T> is a value-type and implements both IEnumerable<T> and IEnumerator<T>. This forces also the implementation of IDisposable, making foreach use a try/finally block just to call an empty Dispose() method.

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.

EmptyClass

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 IEnumerable<T>, IEnumerator<T> and IDisposable.

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.

EmptyYieldBreak

This method uses the implementation that is created by the compiler when the yield keyword is used. In this case, it results in an empty enumeration.

This is a reference-type that implements both IEnumerable<T> and IEnumerator<T>. It differs from the previous implementation in that, it’s not fully optimised to this scenario and MoveNext() doesn’t simply return false.

LinqEmpty

This uses the version of Enumerable.Empty<T>() currently available in .NET Core.

EmptyList and EmptyBoxedList

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.

EmptyArray and EmptyBoxedArray

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).

Benchmarks

I created a benchmark using BenchmarkDotNet containing all these implementations and here we have the results:

  1. Having the try/finally block makes no difference.
  2. The EmptyDisposableStruct<T>, that is a value-type, is 33x times faster than the EmptyClass (the new LINQ version) but 2x slower when casted to IEnumerable<T>.
  3. Two instances of EmptyDisposableStruct<T> are boxed into the heap (2 x 24B) when casted to IEnumerable<T>.
  4. EmptyClass (the new LINQ version) uses references to instances previously allocated on the heap so there are no heap allocations during the benchmark method.
  5. LinqEmpty (the current LINQ implementation) is based on EmptyBoxedArray so they have the same performance.
  6. EmptyClass (the new LINQ version) is 30% faster than LinqEmpty (the current LINQ implementation).
  7. The slowest is EmptyBoxedList

Conclusion

Although 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 foreach an 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…

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store