Why does the C# compiler go mad on this nested LINQ query?

Try to compile following code and you'll find that compiler takes >3 GB of RAM (all free memory on my machine) and very long time to compile (actually I get IO exception after 10 minutes).

using System;
using System.Linq;

public class Test
{
    public static void Main()
    {
        Enumerable.Range(0, 1).Sum(a =>
        Enumerable.Range(0, 1).Sum(b =>
        Enumerable.Range(0, 1).Sum(c =>
        Enumerable.Range(0, 1).Sum(d =>
        Enumerable.Range(0, 1).Sum(e =>
        Enumerable.Range(0, 1).Sum(f =>
        Enumerable.Range(0, 1).Count(g => true)))))));
    }
}

Can anybody explain this curious behavior?

CS Version:     Microsoft (R) Visual C# Compiler version 4.0.30319.17929
OS Name:        Microsoft Windows 7 Ultimate
OS Version:     6.1.7601 Service Pack 1 Build 7601

Solution 1:

I believe that it's related to type inference and/or lambda generation (when type inference has to go in the opposite direction to normal), combined with overload resolution. Unfortunately, just supplying the type parameters doesn't help the situation (where it presumably still has to perform the type checking).

The following code, which should logically be the equivalent code from yours, after lambdas have been analyzed, compiles without issue:

static void Main()
{
    var x = Enumerable.Range(0, 1).Sum(a);
}

private static int a(int a)
{
    return Enumerable.Range(0, 1).Sum(b);
}
private static int b(int b)
{
    return Enumerable.Range(0, 1).Sum(c);
}
private static int c(int c)
{
    return Enumerable.Range(0, 1).Sum(d);
}
private static int d(int d)
{
    return Enumerable.Range(0, 1).Sum(e);
}
private static int e(int e)
{
    return Enumerable.Range(0, 1).Sum(f);
}
private static int f(int f)
{
    return Enumerable.Range(0, 1).Count(g);
}
private static bool g(int g)
{
    return true;
}

I believe Eric Lippert has posted before that type inference is one of the places in the C# compiler where (certain problems) may force the compiler to try to solve an NP-Complete problem and its only real strategy (as here) is brute force. If I can find the relevant references, I'll add them here.

The best reference I can find is here where Eric's discussing the fact that it's the overload resolution work that causes the real cost - remember, Enumerable.Sum has 10 overloads that accept a lambda/method.