foreach + break vs linq FirstOrDefault性能差异

Question

我有两个类来执行特定日期的日期范围数据获取.

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

然后我做了速度测试,表明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

为什么我知道它应该表现更好？因为当我在不使用这些查找类的情况下编写非常相似的代码时,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据我所知,迭代只持续很长时间才能到达有效项目或直到它到达终点.而这在某种程度上一样foreach用break.

但即使是迭代类也比我的简单foreach迭代循环表现更差,这也是一个谜,因为它所拥有的所有开销是与直接访问相比对类中方法的调用.

题

我在LINQ课程中做错了什么,它表现得非常慢？
我在Iteration类中做错了什么,所以它的执行速度是直接foreach循环的两倍？

正在测量哪些时间？

我这样做了:

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

如您所见,不会测量对象实例化.

附录I:结果超过百万次查找

这些结果中显示的范围不重叠,这应该使两种方法更加相似,以防LINQ版本在成功匹配时不会中断循环(很可能这样做).

Generated Ranges:

ID Range        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.                            |-------|

Lookup classes...

- Iteration: 1028ms
- Linq: 4517ms   !!! THIS IS THE PROBLEM !!!
- BitCounter: 401ms

Manual loops...

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

附录II:GitHub:用于测试自己的Gist代码

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

抓住这里.

附录III:最终想法和测量测试

最有问题的当然是LINQ implementatino非常慢.事实证明,这与委托编译器优化有关.LukeH提供了最好,最实用的解决方案,实际上让我尝试了不同的方法.我在方法中尝试了各种不同的GetItem方法(或者GetPointData在Gist中调用):

1. 大多数开发人员会做的常规方式(并且在Gist中实现,并且在结果显示这不是最佳方式之后未更新):

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

2. 通过定义本地谓词变量:

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

3. 本地谓词构建器:

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

4. 本地谓词构建器和本地谓词变量:

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

5. 类级别(静态或实例)谓词构建器:

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

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

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

   在执行此方法时,我还采用了两种方法:

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

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

   2. 谓词构建器定义外部for循环:

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

结果 - 表现最佳

为了比较使用迭代类时,它需要大约.770ms,在随机生成的范围内执行100万次查找.

1. 3本地谓词构建器被证明是最佳的编译器优化,因此它的执行速度几乎与通常的迭代一样快.800毫秒.

2. 6.2谓词构建器定义的外部for循环:885ms

3. 6.1 for循环内定义的谓词:1525ms

4. 所有其他人都在4200ms到4360ms之间,因此被认为无法使用.

因此,无论何时在外部频繁可调用的方法中使用谓词,请定义构建器并执行该操作.这将产生最佳结果.

对我来说,最大的惊喜是代表(或谓词)可能需要花费很多时间.

Answer 1

有时LINQ看起来较慢,因为在循环中生成委托(特别是方法调用的非显而易见的循环)可以增加时间.相反,您可能需要考虑将您的finder移出类,使其更通用(如您的键选择器正在构建):

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

由于您不在迭代代码中使用lambda,这可能有点不同,因为它必须在每次循环中创建委托.通常,这个时间对于每天的编码来说都是无关紧要的,调用委托的时间并不比其他方法调用贵,只是在紧密循环中创建委托,可以增加一点额外的时间.

在这种情况下,由于委托从不更改类,您可以在循环的代码之外创建它,它会更有效.

更新:

实际上,即使没有任何优化,在我的机器上的发布模式下编译我也看不到5x的差异.我只是在一个Item只有一个DateTime字段的情况下执行了1,000,000次查找,列表中有5,000个项目.当然,我的数据等是不同的,但是当您抽象出委托时,您可以看到时间实际上非常接近:

迭代:14279毫秒,0.014279毫秒/呼叫

linq w opt:17400毫秒,0.0174毫秒/电话

这些时间差异非常小,值得使用LINQ的可读性和可维护性改进.我没有看到5x的差异,这让我相信我们在你的测试工具中没有看到的东西.

Answer 2

继Gabe的回答之后,我可以确认差异似乎是由每次呼叫重建代表的成本造成的GetPointData.

如果我GetPointData在你的IterationRangeLookupSingle类中为方法添加一行,那么它会减慢到与之相同的爬行速度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以便point将其作为参数传递给它.这意味着委托只需要构造一次,而不是每次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 3

假设你有一个这样的循环:

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

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