Removing Linq Usage

[TonyValenti]

I’ve noticed a number of commits that are refactoring code to remove Linq usage.

Why is Linq usage being removed? Is there something inherently bad about linq?

I feel like the Linq code is easier to understand and reason about as opposed to nested loops.

[TonyValenti]

@stephentoub

[stephentoub]

LINQ to Objects is great for productivity and succinctly expressing intent. It's not great for high performance, incurring overheads like allocations for delegates and closures, delegate invocations per element, multiple interface dispatch per element, type checks, decreased opportunity for JIT optimization, etc. For code where performance is paramount, such as in dotnet/runtime, it's better to avoid most of LINQ.

[TonyValenti]

Are there any articles that talk about the performance aspect? I'm curious because I would expect a couple of loops to result in essentially the same code as a .Select or .SelectMany. Why does performance degrade?

[stephentoub]

Let's take a simple example.

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Diagnosers;
using BenchmarkDotNet.Running;
using System;
using System.Collections.Generic;
using System.Linq;

[MemoryDiagnoser]
public class Program
{
    static void Main(string[] args) => BenchmarkSwitcher.FromAssemblies(new[] { typeof(Program).Assembly }).Run(args);

    private Dictionary<TimeSpan, int> _timeSpans = Enumerable.Range(0, 100).ToDictionary(i => TimeSpan.FromMinutes(i), i => i % 3);

    [Benchmark]
    public double Linq()
    {
        return Impl(_timeSpans, 2);

        static double Impl(Dictionary<TimeSpan, int> timeSpans, int value) =>
            timeSpans
            .Where(entry => entry.Value == value)
            .Sum(entry => entry.Key.TotalMilliseconds);
    }

    [Benchmark]
    public double Loop()
    {
        return Impl(_timeSpans, 2);

        static double Impl(Dictionary<TimeSpan, int> timeSpans, int value)
        {
            double sum = 0;
            foreach (var entry in timeSpans)
            {
                if (entry.Value == value)
                {
                    sum += entry.Key.TotalMilliseconds;
                }
            }
            return sum;
        }
    }
}

We've got a dictionary mapping TimeSpans to ints for whatever reason, and we have an implementation that finds all entries in the dictionary with a particular value and sums the millisecond values of the key TimeSpan. Two implementations, one with LINQ that does a Where followed by a Sum, and one with an open-coded foreach loop.

This is what benchmark.net reveals:

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
Linq	1,341.0 ns	7.51 ns	6.65 ns	0.0324	-	-	208 B
Loop	341.8 ns	1.17 ns	1.04 ns	-	-	-	-

So, the LINQ variant is 4 times slower and allocates 208 bytes whereas the loop version is allocation-free. You can see the allocations in a profiler... here I've invoked the Linq method 1000 times:

The second line is the IEnumerable object returned from the Where invocation. The third line is the boxed Dictionary<>.Enumerator that results from Where calling IEnumerable<>.GetEnumerator. The fourth line is the closure that results from the Where method capturing value in order to compare it against each entry.Value. And the first line is then the delegate allocation to the method on that closure that represents the lambda passed to Where. On top of those allocations, every entry results in the Where delegate being invoked as well as two interface calls being made (the IEnumerator<>'s MoveNext and Current), and then for anything that passes the Where predicate, the Sum delegate being invoked and two more interface calls on the Where's enumerator.

Compare that with the loop. Dictionary<> exposes a struct-based Enumerator which the compiler-generated code for foreach binds to strongly avoiding any enumerator allocation, plus being able to inline some accesses to the methods on that enumerator, no interface dispatch. There are no delegates to invoke, because the code is right there as part of the method. The JIT is able to keep relevant state in registers rather than constantly spilling back to memory. Etc.

[ShreyasJejurkar]

This is quite great @stephentoub, I had the same question.
So besides all of this, are there any chances that we make some changes in Linq implementation directly (without breaking of course), so that it will use less allocations and use less memory. If did so then overall linq performance will get improved everywhere!
So is there any room for linq internal performance improvements?

[stephentoub]

The costs I cited above are largely unrelated to the implementation of the LINQ methods themselves. The lambda passed to Where is closing over state in the outer scope, so the only way to get that data into the lambda is for the C# compiler to generate a class that stores it, and then allocate a delegate that points to it. The delegates to both Where and Sum need to be invoked. Etc.

[ShreyasJejurkar]

Ohhh. OK. Make sense! 👍👍