NetFabric.Hyperlinq — Generation Operations

Improving performance of LINQ generation operations.

Beach Sand 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.

Generation Operations

LINQ is a library of operations on IEnumerable<T>. These operations can be grouped into categories. One of these categories is the generation operations that includes all the operations that create a new sequence of values.

Enumerables and enumerators

As mentioned above, all original implementations of the generation operations return IEnumerable<T> . LINQ uses classes derived from an internal Iterator<T> class, while Ix uses the yield keyword. Both result in a reference type that implements both IEnumerable<T> and IEnumerator<T> interfaces. GetEnumerator() returns a “clone” of itself, with the state reset.

Readonly struct

All enumerables are immutable so, the readonly keyword is used on their declaration. This is a feature introduced in C# 7.2, that allows the compiler not to generate defensive copies, improving performance.

The use of the keyword in all these cases resulted in major improvements in some of the benchmarking scenarios.

IReadOnlyCollection and IReadOnlyList

Another objective of this project is to introduce LINQ to “new” interfaces like IReadOnlyCollection<T> and IReadOnlyList<T>.

This means that the Count property can be used on the result of these operations, which has O(1) complexity, instead of the Count() operation, which has O(n) complexity.

Note: Although Count() can be O(1) for some cases, it’s not the case for generation operations. It doesn’t change even for this new implementation as Count() still hasn’t been updated to be aware of IReadOnlyCollection<T>. Like I mentioned in a previous article, it’s better to expose these as public API than as internal runtime optimizations.

Benchmarks

The benchmark calculates the sum of the items, using foreach and for loops, with a number of items of 0, 100 and 10000. (The original implementations only support foreach).

The new implementation results in major performance improvements.

The new implementation is only slower for Range and Repeat, when using foreach and when empty. This is because the original implementation, by returning an interface, can return different implementations given the parameter values. When count is 0, it returns Empty() which is more efficient. This should not be a big issue as empty enumerables are less frequent and its MoveNext() method is called only once.

Conclusions

There’s still a lot of work required to fully take advantage of these performance improvements. foreach can use the value types without boxing but all the methods that take IEnumerable<T> parameters need to use interface constraints.

Still, it shows that these small changes in the code can make a huge difference in the performance.

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