foreach + break vs linq FirstOrDefault性能差异

我有两个类执行date范围数据提取特定的日子。

public class IterationLookup<TItem> { private IList<Item> items = null; public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector) { this.items = items.OrderByDescending(keySelector).ToList(); } public TItem GetItem(DateTime day) { foreach(TItem i in this.items) { if (i.IsWithinRange(day)) { return i; } } return null; } } public class LinqLookup<TItem> { private IList<Item> items = null; public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector) { this.items = items.OrderByDescending(keySelector).ToList(); } public TItem GetItem(DateTime day) { return this.items.FirstOrDefault(i => i.IsWithinRange(day)); } } 

然后我做速度testing，显示Linq版本慢了大约5倍 。 这将是有意义的，当我将本地存储项目，而不使用ToList枚举它们。 这会让速度变慢，因为每次调用FirstOrDefault ，linq都会执行OrderByDescending 。 但事实并非如此，所以我不知道发生了什么事情。 Linq应该与迭代非常相似。

这是测量我的时间的代码摘录

 IList<RangeItem> ranges = GenerateRanges(); // returns List<T> var iterLookup = new IterationLookup<RangeItems>(ranges, r => r.Id); var linqLookup = new LinqLookup<RangeItems>(ranges, r => r.Id); Stopwatch timer = new Stopwatch(); timer.Start(); for(int i = 0; i < 1000000; i++) { iterLookup.GetItem(GetRandomDay()); } timer.Stop(); // display elapsed time timer.Restart(); for(int i = 0; i < 1000000; i++) { linqLookup.GetItem(GetRandomDay()); } timer.Stop(); // display elapsed time 

为什么我知道它应该performance更好？ 因为当我编写一个非常相似的代码而不使用这些查找类时，Linq执行与foreach迭代非常相似…

 // continue from previous code block // items used by both order as they do in classes as well IList<RangeItem> items = ranges.OrderByDescending(r => r.Id).ToList(); timer.Restart(); for(int i = 0; i < 1000000; i++) { DateTime day = GetRandomDay(); foreach(RangeItem r in items) { if (r.IsWithinRange(day)) { // RangeItem result = r; break; } } } timer.Stop(); // display elapsed time timer.Restart(); for(int i = 0; i < 1000000; i++) { DateTime day = GetRandomDay(); items.FirstOrDefault(i => i.IsWithinRange(day)); } timer.Stop(); // display elapsed time 

这是我认为非常类似的代码。 FirstOrDefault和我所知的一样，也只是迭代，直到它到达一个有效的项目或者直到它结束。 这在某种程度上和break foreach是一样的。

但即使迭代类比我简单的foreach迭代循环，这也是一个谜，因为所有的开销是一个类的方法相比，直接访问的调用。

题

我在LINQ类中做错了什么，它执行得如此之慢？
我在迭代类中做了什么错误，所以它的执行速度是直接foreach循环的两倍？

哪些时间正在测量？

我做了这些步骤：

1. 生成范围（如结果中所示）
2. 为IterationLookup，LinqLookup创build对象实例（以及我的优化date范围类BitCountLookup，这不是讨论的一部分）
3. 启动计时器并通过使用先前实例化的IterationLookup类，在最大date范围内的随机天内执行100万次查找（如结果中所示）。
4. 启动计时器并通过使用先前实例化的LinqLookup类，在最大date范围内的随机天内执行1百万次查找（如结果中所示）。
5. 启动定时器，并使用手动foreach + break循环和Linq调用执行100万次查找（6次）。

正如你所看到的， 对象实例化是不被测量的 。

附录I：结果超过百万查找

在这些结果中显示的范围不重叠，这应该使两种方法更加类似，以防LINQ版本在成功匹配时不会中断循环（很有可能这样做）。

生成的范围：

 ID范围000000000111111111122222222223300000000011111111112222222222
                 123456789012345678901234567890112345678901234567890123456789
 09 22.01.-30.01。  | ------- |
 08 14.01.-16.01。  |  -  |
 07 16.02.-19.02。  |  -  |
 06 15.01.-17.01。  |  -  |
 05 19.02.-23.02。  | --- |
 04 01.01.-07.01。| ----- |
 03 02.01.-10.01。  | ------- |
 02 11.01.-13.01。  |  -  |
 01 16.01.-20.01。  | --- |
 00 29.01.-06.02。  | ------- |

查找类...

 - 迭代：1028ms
  -  Linq：4517ms !!!  这就是问题 ！！！
 -  BitCounter：401ms

手动循环...

 -  Iter：786ms
 Linq：981ms
 -  Iter：787ms
 -  Linq：996ms
 -  Iter：787ms
 -  Linq：977ms
 -  Iter：783ms
 Linq：979ms

附录二：GitHub：Gist代码来自己testing

我已经提出了一个要点，所以你可以自己得到完整的代码，看看发生了什么。 创build一个控制台应用程序，并将Program.cs复制到其中，添加其他文件，这是这个要点的一部分。

在这里抓住它。

附录三：最后的想法和测量testing

最有问题的东西当然是LINQ实现非常缓慢。 原来，这一切都与委托编译器优化。 卢克提供了最好和最有用的解决scheme ，实际上让我尝试不同的方法。 我在GetItem方法（或GetPointData因为它在Gist中调用）尝试了各种不同的方法：

1. 大多数开发人员会这样做的常用方法（在Gist中也是这样实现的，结果显示这并不是最好的方式）：

    return this.items.FirstOrDefault(item => item.IsWithinRange(day)); 

2. 通过定义一个本地谓词variables：

    Func<TItem, bool> predicate = item => item.IsWithinRange(day); return this.items.FirstOrDefault(predicate); 

3. 本地谓词构build器：

    Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d); return this.items.FirstOrDefault(builder(day)); 

4. 本地谓词构build器和本地谓词variables：

    Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d); Func<TItem, bool> predicate = builder(day); return this.items.FirstOrDefault(predicate); 

5. 类级别（静态或实例）谓词构build器：

    return this.items.FirstOrDefault(classLevelBuilder(day)); 

6. 外部定义的谓词并作为方法参数提供

    public TItem GetItem(Func<TItem, bool> predicate) { return this.items.FirstOrDefault(predicate); } 

   当执行这个方法时，我也采取了两种方法：

   1. 谓词直接在for循环中的方法调用中for ：

       for (int i = 0; i < 1000000; i++) { linqLookup.GetItem(item => item.IsWithinRange(GetRandomDay())); } 

   2. 在for循环外部定义的谓词构build器：

       Func<DateTime, Func<Ranger, bool>> builder = d => r => r.IsWithinRange(d); for (int i = 0; i < 1000000; i++) { linqLookup.GetItem(builder(GetRandomDay())); } 

结果 – 什么效果最好

为了比较使用迭代类，它需要约。 770毫秒 ，对随机生成的范围执行100万次查找。

1. 3本地谓词构build器被certificate是最好的编译器优化，所以它的执行速度几乎和平常一样快。 800ms 。

2. 6.2循环外定义的谓词构build器： 885ms

3. 6.1 for循环中定义的谓词： 1525ms

4. 所有其他人都采取了4200毫秒至4360毫秒之间的地方，因此被认为是无法使用的。

所以无论何时在外部频繁调用方法中使用谓词，定义一个构build器并执行它。 这将产生最好的结果。

对我来说，最令我感到惊讶的是，代表（或谓词）可能会花费很多时间。

Answer 1

除了Gabe的回答 ，我可以确认这种差异似乎是由于每次调用GetPointData重新构造委托所造成的。

如果我在IterationRangeLookupSingle类中将一行添加到GetPointData方法，那么它会降低到与LinqRangeLookupSingle相同的爬行速度。 尝试一下：

 // in IterationRangeLookupSingle<TItem, TKey> public TItem GetPointData(DateTime point) { // just a single line, this delegate is never used Func<TItem, bool> dummy = i => i.IsWithinRange(point); // the rest of the method remains exactly the same as before // ... } 

（我不知道为什么编译器和/或抖动不能忽略我上面添加的多余的委托，显然，这个委托在你的LinqRangeLookupSingle类中是必须的。

一种可能的解决方法是在LinqRangeLookupSingle中LinqRangeLookupSingle谓词，以便将point作为parameter passing给它。 这意味着委托只需要构造一次 ，而不是每次调用GetPointData方法。 例如，以下更改将加快LINQ版本，以便与foreach版本相当：

 // in LinqRangeLookupSingle<TItem, TKey> public TItem GetPointData(DateTime point) { Func<DateTime, Func<TItem, bool>> builder = x => y => y.IsWithinRange(x); Func<TItem, bool> predicate = builder(point); return this.items.FirstOrDefault(predicate); } 

Answer 2

有时LINQ显得比较慢，因为在一个循环中代理的生成（特别是方法调用的非显而易见的循环）可以增加时间。 相反，您可能需要考虑将您的查找器移出课程，以使其更为通用（如您的关键select器正在构build中）：

 public class LinqLookup<TItem, TKey> { private IList<Item> items = null; public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> keySelector) { this.items = items.OrderByDescending(keySelector).ToList(); } public TItem GetItem(Func<TItem, TKey> selector) { return this.items.FirstOrDefault(selector); } } 

由于在迭代代码中不使用lambdaexpression式，所以这可能有点不同，因为它必须在每次循环中创build委托。 通常，这个时间对于日常编码来说是微不足道的，调用委托的时间并不比其他方法调用更昂贵，它只是在紧密的循环中创build代理，可以增加一点额外的时间。

在这种情况下，由于委托从不改变类，你可以在你正在循环的代码之外创build它，这将是更有效的。

更新 ：

其实，即使没有任何优化，在我的机器上的发布模式编译我没有看到5倍的差异。 我只对一个只有DateTime字段的Item执行了1,000,000个查找，列表中有5,000个项目。 当然，我的数据等等是不一样的，但是当你抽象出代理的时候，你可以看到时间真的很接近：

迭代：14279毫秒，0.014279毫秒/呼叫

linq w opt：17400 ms，0.0174 ms / call

这些时间差异非常小，值得使用LINQ的可读性和可维护性改进。 虽然我没有看到5倍的差异，但是我相信我们没有看到你的testing工具。

Answer 3

假设你有这样一个循环：

 for (int counter = 0; counter < 1000000; counter++) { // execute this 1M times and time it DateTime day = GetRandomDay(); items.FirstOrDefault(i => i.IsWithinRange(day)); } 

此循环将创build1,000,000个lambda对象，以便i.IsWithinRange调用访问day 。 在每个lambda创build之后，调用i.IsWithinRange的委托在平均1,000,000 * items.Length / 2次被调用。 这两个因素都不存在于你的foreach循环中，这就是显式循环更快的原因。