¿Por qué el compilador de C# se vuelve loco con esta consulta LINQ anidada?

Question

¿Por qué el compilador de C# se vuelve loco con esta consulta LINQ anidada?

Intente compilar el siguiente código y encontrará que el compilador toma >3 GB de RAM (toda la memoria libre en mi máquina) y mucho tiempo para compilar (en realidad obtengo la excepción de IO después de 10 minutos).

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)))))));
    }
}

¿Alguien puede explicar este curioso comportamiento?

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

Uso de Memoria

95

c#linq

Author: Sam Starling, 2014-04-06

Source

1 answers

score 40 · Accepted Answer

Creo que está relacionado con la inferencia de tipos y/o la generación lambda (cuando la inferencia de tipos tiene que ir en la dirección opuesta a la normal), combinada con la resolución de sobrecarga. Desafortunadamente, simplemente suministrar los parámetros de tipo no ayuda a la situación (donde presumiblemente todavía tiene que realizar la comprobación de tipo).

El siguiente código, que lógicamente debería ser el equivalente del suyo, después de que se hayan analizado las lambdas, compila sin problemas:

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. Si puedo encontrar las referencias relevantes, las agregaré aquí.

La mejor referencia que puedo encontrar es aquí donde Eric está discutiendo el hecho de que es el trabajo de resolución de sobrecarga lo que causa el costo real-recuerde, Enumerable.Sum tiene 10 sobrecargas que aceptan un método lambda/.