Warum wird der C # -Compiler bei dieser verschachtelten LINQ-Abfrage verrückt?

97

Wenn Sie versuchen, den folgenden Code zu kompilieren, werden Sie feststellen, dass der Compiler> 3 GB RAM (der gesamte freie Speicher auf meinem Computer) und sehr lange Zeit zum Kompilieren benötigt (tatsächlich erhalte ich nach 10 Minuten eine E / A-Ausnahme).

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

Kann jemand dieses merkwürdige Verhalten erklären?

CS-Version: Microsoft (R) Visual C # Compiler Version 4.0.30319.17929
Betriebssystemname: Microsoft Windows 7 Ultimate
Betriebssystemversion: 6.1.7601 Service Pack 1 Build 7601

Speichernutzung

Eugene D. Gubenkov
quelle
5
Guter Anruf! Ich habe den Code gerade in Visual Studio eingefügt und er verbrauchte alle 4 GB, die ein 32-Bit-Prozess zulässt, und stürzte dann ab (2013 Ultimate unter Windows 8.1).
Satnhak
2
Fügen Sie diesen Code einer gemeinsam genutzten Codebasis hinzu (mithilfe des Notizblocks) und beobachten Sie, wie die Computer Ihrer Mitarbeiter abstürzen.
usr
3
Klingt nach einer guten Sache, über Microsoft Connect und an das Roslyn-Team zu berichten, wenn der Compiler dasselbe Verhalten aufweist.
Trillian
3
Ich glaube, ich habe Eric Lippert irgendwo sagen hören (obwohl ich mich nicht erinnere, wo), dass das Verschachteln von Lambdas mit Typinferenz dem Compiler böse Kopfschmerzen bereiten kann. Ich kann mir nicht vorstellen, wo ich es gesehen habe, kann also keine Referenz zitieren. Hoffentlich kann der Mann selbst dies sehen und kommentieren ...
Chris
2
Gut gemacht, schneiden Sie es ab und Sie haben vielleicht eine gute Antwort darauf: Absturz Ihres Lieblings-Compilers
Nathan Cooper

Antworten:

40

Ich glaube, dass dies mit der Typinferenz und / oder der Lambda-Erzeugung zusammenhängt (wenn die Typinferenz in die entgegengesetzte Richtung zur Normalen gehen muss), kombiniert mit der Überlastungsauflösung. Leider hilft es nicht, nur die Typparameter anzugeben (wo vermutlich noch die Typprüfung durchgeführt werden muss).

Der folgende Code, der logischerweise der entsprechende Code von Ihnen sein sollte, wird nach der Analyse von Lambdas problemlos kompiliert:

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

Ich glaube, Eric Lippert hat geschrieben, bevor diese Typinferenz eine der Stellen im C # -Compiler ist, an denen (bestimmte Probleme) den Compiler zwingen können, ein NP-Complete-Problem zu lösen, und seine einzige wirkliche Strategie (wie hier) ist Brute Force. Wenn ich die relevanten Referenzen finde, füge ich sie hier hinzu.


Die beste Referenz, die ich finden kann, ist hier, wo Eric die Tatsache diskutiert, dass es die Überlastungsauflösungsarbeit ist, die die tatsächlichen Kosten verursacht - denken Sie daran, Enumerable.Sum hat 10 Überladungen, die ein Lambda / eine Lambda-Methode akzeptieren.

Damien_The_Unbeliever
quelle
1
Im Grunde genommen drängt sich der Compiler brutal durch 10^nKombinationen (wo nist die Anzahl der verketteten Methoden). Klingt vernünftig (als Erklärung).
DarkWanderer
1
@ DarkWanderer:that^numberofpossibletypes
Leppie
@ Damien_The_Unbeliever, ich verstehe Ihr Denken, Nähte wirklich vernünftig (übrigens der Code nicht kompiliert )
Eugene D. Gubenkov
15
Ihre Analyse hier ist korrekt. Jedes Lambda führt einen Faktor von zehn möglichen Überlastungen ein, und alle Kombinationen müssen überprüft werden. Ich überlegte, Code hinzuzufügen, der ausfiel, als die Anzahl der Kombinationen groß wurde, aber nie implementiert wurde.
Eric Lippert
2
@EricLippert Zeit für eine Pull-Anfrage! : D
Rob H