Почему компилятор C # сходит с ума от этого вложенного запроса LINQ?

97

Попробуйте скомпилировать следующий код, и вы обнаружите, что компилятор занимает> 3 ГБ ОЗУ (вся свободная память на моем компьютере) и очень много времени для компиляции (на самом деле я получаю исключение ввода-вывода через 10 минут).

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

Кто-нибудь может объяснить это любопытное поведение?

Версия CS: Microsoft (R) Visual C # Compiler версии 4.0.30319.17929
Имя ОС: Microsoft Windows 7 Ultimate.
Версия ОС: 6.1.7601, пакет обновления 1, сборка 7601

Использование памяти

Евгений Дмитриевич Губенков
источник
5
Хороший звонок! Я просто вставил код в Visual Studio, и он израсходовал все 4 Гб, разрешенных 32-битному процессу, а затем завершился сбоем (2013 Ultimate в Windows 8.1).
satnhak 06
2
Добавьте этот код в общую базу кода (с помощью блокнота) и наблюдайте за тем, как компьютеры ваших коллег ломаются.
usr
3
Похоже, неплохо сообщить о Microsoft Connect и команде Roslyn, если их компилятор демонстрирует такое же поведение.
Trillian
3
Мне кажется, я слышал, как Эрик Липперт где-то говорил (хотя я не помню, где именно), что слишком частое вложение лямбда-выражений с выводом типа может вызвать у компилятора неприятные головные боли. Я не могу вспомнить, где я это видел, поэтому не могу привести ссылку. Надеюсь, этот человек сам увидит это и прокомментирует ...
Крис
2
Молодец, урежьте его, и, возможно, у вас будет хороший ответ на этот вопрос: выведите из строя ваш любимый компилятор
Натан Купер,

Ответы:

40

Я считаю, что это связано с выводом типа и / или генерацией лямбда (когда вывод типа должен идти в направлении, противоположном нормальному) в сочетании с разрешением перегрузки. К сожалению, простая передача параметров типа не помогает в ситуации (где, по-видимому, все еще необходимо выполнить проверку типа).

Следующий код, который логически должен быть эквивалентом вашего кода, после анализа лямбда-выражений компилируется без проблем:

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

Я считаю, что Эрик Липперт опубликовал сообщение до того, что вывод типа является одним из тех мест в компиляторе C #, где (определенные проблемы) могут заставить компилятор попытаться решить проблему NP-Complete, и его единственная реальная стратегия (как здесь) - это грубая сила. Если я найду соответствующие ссылки, я добавлю их сюда.


Лучшая ссылка, которую я могу найти, - это здесь, где Эрик обсуждает тот факт, что именно работа по разрешению перегрузки вызывает реальные затраты - помните, Enumerable.Sum имеет 10 перегрузок, которые принимают лямбда / метод.

Damien_The_Unbeliever
источник
1
Итак, в основном компилятор перебирает 10^nкомбинации (где n- количество связанных методов). Звучит разумно (то есть в качестве объяснения).
DarkWanderer
1
@DarkWanderer:that^numberofpossibletypes
leppie
@Damien_The_Unbeliever, я понимаю ваше мышление, швы действительно разумные (кстати, код не компилируется )
Евгений Д. Губенков
15
Ваш анализ здесь верен. Каждая лямбда представляет десять возможных перегрузок, и все комбинации должны быть проверены. Я подумал о добавлении кода, который помогал бы, когда количество комбинаций стало большим, но так и не смог его реализовать.
Эрик Липперт
2
@EricLippert Пора сделать пул-реквест! : D
Rob H