NetFabric.Hyperlinq — Select Operation

Improving performance of LINQ’s Select operation.

Tiles by aalmada

Introduction

This is a follow up on my exploration into improving LINQ performance. This is a work in progress. Go to my previous article to find what triggered this.

Select Operation

Select() is a projection operation, it creates a new sequence by applying a transformation function to each element of the original sequence.

Value type enumerator

As I explained in a previous article, using a value type enumerator instead, can substantially improve performance. Replacing the yield return by a hand-made enumerator, looks like this:

  • Now, there is no need to use a local function for immediate/lazy execution separation, but methods that throw exceptions cannot be inlined by the JIT compiler. Using local functions to throw the exceptions is a good alternative, making Select() a candidate for inlining.
  • The public SelectEnumerable.GetEnumerator() method returns the type Enumerator, to avoid boxing of the enumerator. The other methods that cause boxing are implemented explicitly so that they are only used when the enumerable is cast to any of the interfaces derived from IEnumerable<T> that it implements.
  • The enumerable is passed by reference to the enumerator constructor using the in keyword. This is the equivalent to a read-only ref. Both the enumerable and the enumerator are declared as readonly struct, avoiding defensive copies made by the compiler.
  • Every time a new Enumerator instance is created, it creates a “twin” enumerator from the source enumerable.
  • The Enumerator methods simply call the methods from the source enumerator, with the exception of Current, that transforms the value by calling theselector function.

IReadOnlyCollection and IReadOnlyList interfaces

Select() applies the transformation to every element of the original sequence. This means that the size of the sequence does not change. It also means that it’s possible to implement random access.

Generics interface constraints

Generics constraints allow the use of interfaces without boxing the value types. To avoid boxing the source enumerator, the code has to be changed to use interface constraints:

  • Use of different static partial classes to avoid ambiguous method calls.
  • source parameter can now be a value type so is null cannot be used. The == operator has to be used instead.
  • TEnumerator can be a value type not defined as readonly so the enumerator field cannot now be defined as readonly. Otherwise, the compiler will make defensive copies when its methods are called, breaking the enumeration behavior. This implies that the Enumerator struct also cannot be defined as readonly but that’s not a big issue.

Generic types inference

When using the above code, I got this error: error CS0411: The type arguments for method ‘Enumerable.Select<TEnumerable, TEnumerator, TSource, TResult>(TEnumerable, Func<TSource, TResult>)’ cannot be inferred from the usage. Try specifying the type arguments explicitly.

  • If it’s not any of the known collections, but implements IReadOnlyList<T>, then the second overload is used.
  • Otherwise, the first overload is used…

Low-level enumeration interfaces

Up until now, I’ve been assuming that the highest-level enumeration interface is used and we can take advantage of its features. If everybody followed the rules I stated in my previous article on .NET enumeration, this wouldn’t be an issue but unfortunately, it’s not always the case.

Benchmarks

So, how does this implementation of the Select() operation compares to the one in LINQ?

Conclusions

Due to the limitations on inference with constrained interfaces, I struggled some time to find a solution that is usable. I think this one is quite acceptable, fully compliant with the current LINQ API and with better performance.

Principal Engineer @ Farfetch - Future Retail Lab https://about.me/antao.almada

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