NetFabric.Hyperlinq — Optimizing LINQ

5 min readJan 11, 2019

Improving performance of LINQ operations.

LINQ is a great tool for writing easy to read and easy to maintain data processing code. I’ve been writing articles on how using it incorrectly will seriously affect the performance of the application but, even when used correctly, it usually does not result in the best performant solution.

For this reason, many avoid using it. Some use libraries that try to solve this issue. Some of these libraries try to stay true to the LINQ API, some have very different solutions.

Recently, I’ve started wondering what if LINQ used some of the techniques described below? I’m sure I’m not the first one but I want to explore this. I may get stuck in a dead end, still I’m sure I’ll learn a lot along the way.

Duck typing

I already mentioned in my previous articles on .NET enumeration that foreach uses duck typing. What does that mean and why?

The foreach in C# is actually syntactic sugar:

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

Is converted by the compiler into a while loop inside a try/finally block:

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

Lets make a small change. Lets convert the result of Range() into a List<int> by adding a ToList():

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

It’s converted by the compiler to the following:

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

Notice that the enumerator variable type changes from IEnumerator<int> to List<int>.Enumerator.

Note: This is one great reason why you should always use var. When writing similar code, if left as IEnumerator<int>, it would inadvertently affect performance. var use results in the best case. This is why I use var… 😉

Let's dive into the .NET Core source code to better understand what’s going on.

List<T> implements IList<T>, making it also implement IEnumerable and IEnumerable<T>. The implementations of the two GetEnumerator() methods, that are required by the interfaces, are explicitly implemented. This means that these methods are only called when the List<T> is cast to one of these interfaces. Otherwise, the public GetEnumerator() implementation is called. This version of GetEnumerator() returns Enumerator, which is a public inner struct of List<T>.

public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
    public Enumerator GetEnumerator()
        => new Enumerator(this);

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
        => new Enumerator(this);

    IEnumerator IEnumerable.GetEnumerator()
        => new Enumerator(this);
        
    public struct Enumerator : IEnumerator<T>, IEnumerator
    {
        public bool MoveNext()
        {
            ...
        }
            
        public T Current => _current;

        object IEnumerator.Current
        {
            get
            {
                ...
            }
        }       
    }
}

When the compiler finds a foreach, it doesn’t simply look for the IEnumerable<T> and IEnumerator<T> implementations. It looks for a public method GetEnumerator() that returns a type that implements a public property Current and a public method MoveNext(). It uses the types returned and not the interfaces they implement. This is duck typing! But, why?

List<int>.Enumerator is a struct, a value type. If List<T> is stored in an IEnumerator<T> variable, the IEnumerator<T>.GetEnumerator() explicit implementation will be used and the List<int>.Enumerator will be boxed. This means that it will be copied into the heap and that all method calls will be virtual. Not a major issue when these methods are called a few times but these are usually called millions of times in the lifetime of most applications. It’s a huge issue when dealing with large sets of data.

The foreach keyword, together with value-type enumerables which are returned by all the .NET framework collections, guarantees the best possible results.

LINQ is a library of extension methods to IEnumerable<T>. Everything is cast to IEnumerable<T> and IEnumerator<T>. This means that, although it includes many internal optimizations, ends up as the worst scenario described above.

Constrained interfaces

It’s possible to use interfaces in .NET without causing boxing of value types.

The following code demonstrates it using a simple IInterface with one method. MyStruct is a value type that implements IInterface. MyStaticClass implements three methods that show different ways of invoking the method defined by IInterface.

using SharpLab.Runtime;

public interface IInterface
{
    int Method();
}

public struct MyStruct : IInterface
{
    public int Method() => 1;
}

public static class MyStaticClass 
{
    public static int AnotherMethod(MyStruct i) 
        => i.Method();
    
    public static int AnotherMethod(IInterface i) 
        => i.Method();
        
    [JitGeneric(typeof(MyStruct))]
    public static int AnotherMethod<TInterface>(TInterface i) 
        where TInterface : IInterface
        => i.Method();
}

The equivalent code IL:

.method public hidebysig static int32 AnotherMethod (valuetype MyStruct i) cil managed 
{
    IL_0000: ldarga.s i
    IL_0002: call instance int32 MyStruct::Method()
    IL_0007: ret
} 

.method public hidebysig static int32 AnotherMethod (class IInterface i) cil managed 
{
    IL_0000: ldarg.0
    IL_0001: callvirt instance int32 IInterface::Method()
    IL_0006: ret
} 

.method public hidebysig static int32 AnotherMethod<(IInterface) TInterface> (!!TInterface i) cil managed 
{
    IL_0000: ldarga.s i
    IL_0002: constrained. !!TInterface
    IL_0008: callvirt instance int32 IInterface::Method()
    IL_000d: ret
}

And the equivalent code in Jit Asm:

MyStaticClass.AnotherMethod(MyStruct)
    L0000: lea ecx, [esp+0x4]
    L0004: call MyStruct.Method()
    L0009: ret 0x4

MyStaticClass.AnotherMethod(IInterface)
    L0000: push ebp
    L0001: mov ebp, esp
    L0003: call dword [0x21d3008c]
    L0009: pop ebp
    L000a: ret

MyStaticClass.AnotherMethod[[MyStruct, _]](MyStruct)
    L0000: lea ecx, [esp+0x4]
    L0004: call MyStruct.Method()
    L0009: ret 0x4

NOTE: The code was converted using SharpLab. The attribute on the third method is used so that SharpLab generates the JIT for when TInterface is MyStruct.

Things to notice in the IL:

When the parameter is a value type, the method is called using the call instruction.
When the parameter is an interface (reference type), the method is called using the callvirt instruction.
When the parameter is a constrained interface, the method is called using the callvirt instruction but preceded by constrained. !!TInterface.

Things to notice in the JIT Asm:

callvirt results in more expensive code than call.
Although the constrained interface uses a callvirt instruction, it results in the same code as call.

This means the compiler will generate a new method for each TInterface found, avoiding boxing and virtual calls for value types. It’s one more duck typing done by the compiler.

LINQ still does not take advantage of this feature when passing in the IEnumerable<T> arguments.

IReadOnlyXXX interfaces

Since LINQ was created, the following interfaces were added to the System.Collections.Generic namespace:

public interface IReadOnlyCollection<out T> 
    : IEnumerable<T>
{
    int Count { get; }
}

public interface IReadOnlyList<out T> 
    : IReadOnlyCollection<T>
{
    T this[int index] { get; }
}

public interface IReadOnlyDictionary<TKey, TValue> 
    : IReadOnlyCollection<KeyValuePair<TKey, TValue>>
{
    bool ContainsKey(TKey key);
    bool TryGetValue(TKey key, out TValue value);

    TValue this[TKey key] { get; }
    IEnumerable<TKey> Keys { get; }
    IEnumerable<TValue> Values { get; }
}

Just like IEnumerable<T>, these give a read-only view of the collections but exposing functionality that can be used to avoid some of the IEnumerable<T> bottlenecks.

All .NET framework collections implement these but LINQ is still not aware of them…

Read-only structs and read-only refs

C# 7 introduces features that allows passing value types by reference while keeping immutability and performance.

NetFabric.Hyperlinq

This is the repository where I keep the code for this brainstorm. Feel free to explore and contribute.

I’ll be writing followup articles on the successes and failures along the way…

Follow-ups: