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

C#Linq

C# Problem Overview


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

Memory Usage

C# Solutions


Solution 1 - C#

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.

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionEugene D. GubenkovView Question on Stackoverflow
Solution 1 - C#Damien_The_UnbelieverView Answer on Stackoverflow