在Linq谓词中,编译器是否会优化对Enumerable.Min()的"标量"调用,还是会为每个项调用它？

Question

我只是在看" 使用Lambda Expression的SubQuery "这个问题,并想知道Linq谓词的编译器优化.

假设我有一个List<string>被叫names,我正在寻找字符串长度最短的项目.所以我们有查询names.Where(x => x.Length == names.Min(y => y.Length))(来自上面提到的问题).很简单.

现在,我们知道C#规范不允许您在枚举时修改集合.因此,我认为假设上述调用Min()始终为每次调用返回相同的值在技术上是安全的.

但是,我的假设是编译器真的无法知道Enumerable.Min扩展方法中的lambda 返回什么.因为,例如我们可以这样做:

int i = 0;
return names.Where(x => x.Length == names.Min(y => ++i));

这意味着有问题的查询实际上是O(n²) - Min()将为每次迭代计算结果.要获得所需的O(n)实现,您必须明确:

int minLength = names.Min(y => y.Length);
return names.Where(x => x.Length == minLength);

我的假设是正确的,还是有一些关于Linq或C#规范的特殊内容,它允许编译器查看lambda内部并优化此调用Min()？

---

@spender绝对正确.请考虑以下代码段:

List<string> names = new List<string>(new[] { "r", "abcde", "bcdef", "cdefg", "q" });
return names.Where(x => 
{
    bool b = (x.Length == names.Min(y => y.Length)); 
    names = new List<string>(new[] { "ab" }); 
    return b; 
});

这将只返回"r",而不是"q",因为当旧的引用names被迭代(foreachx)时,Min第一次迭代之后的调用实际上是用新的实例调用的names.但是,在问题顶部查看查询的人可以说肯定没有任何内容被修改.所以我的问题仍然存在:编译器是否足够聪明才能看到这个？

Answer 1

想知道Linq谓词的编译器优化.

C#编译器不知道如何实现BCL类型.它可以查看您引用的程序集,但这些程序集可以随时更改.编译器不能假设编译程序将运行的机器将具有相同的二进制文件.因此,C#编译器无法合法地执行这些优化,因为您可以区分它们.

JIT可以进行这样的优化(目前还没有).

现在,我们知道C#规范不允许您在枚举时修改集合.因此,我认为假设上面对Min()的调用将始终为每个调用返回相同的值,这在技术上是安全的.

C#的规范对库一无所知.它根本没有说.每个实现都IEnumerable可以决定是否允许这样的行为.

但是,我的假设是编译器真的无法知道Enumerable.Min扩展方法中的lambda返回什么.

是的,它可以做任何事情.在运行时,JIT可以推断出这样的属性,但事实并非如此.注意,推断甚至基本事实很难,因为有反射,运行时代码生成和多线程之类的东西.

我的假设是正确的,还是有一些关于Linq或C#规范的特殊内容,它允许编译器查看lambda内部并优化对Min()的调用？

不,LINQ只有库优化.LINQ to objects完全按照您编写的方式执行.其他LINQ提供商的做法不同.

如果你想知道JIT是否会执行一些高级优化,那么答案通常不是.NET 4.5.