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器并执行它。 这将产生最好的结果。

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

除了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类中必须的。

一种可能的解决方法是在LinqRangeLookupSingleLinqRangeLookupSingle谓词,以便将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); } 

有时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工具。

假设你有这样一个循环:

 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循环中,这就是显式循环更快的原因。