为什么LINQ中的LastOrDefault(predicate)比FirstOrDefault(predicate)更快？

Question

介绍

今天在测试某些LinQ函数的性能差异时，我注意到LastOrDefault(predicate)比FirstOrDefault(predicate)几乎总是更快，这引起了我的兴趣，因此我编写了一些测试用例来测试两个函数之间的差异。

我创建了一个包含从1到1000000的整数值的列表，如下所示：

List<int> l = new List<int>();
for (int i = 1; i <= 1000000; i++)
  {
    l.Add(i);
  }

然后编写了两种方法first()和last()

 static void first(List<int> l)
{
  int e = l.FirstOrDefault(x => x == 500000);
  int z = l.FirstOrDefault(x => x == 500000);
  int d = l.FirstOrDefault(x => x == 500000);
  int v = l.FirstOrDefault(x => x == 500000);
  int f = l.FirstOrDefault(x => x == 500000);
}

我将其放在一个for循环中运行1000次，并设置断点条件，在最后一次迭代后停止，但在我测试的每种情况下，LastOrDefault都更快。

测试用例

• 两者都设置为列表中间的元素（LastOrDefault几乎是First的两倍快）
• 两者都设置为列表内相同距离的元素（如250k和750k）-再次LastOrDefault更快
• 交换我的方法调用顺序（先调用Last()再调用First()）- 没有区别
• 在它们自己的列表中运行而不是在同一个列表上运行（仍然没有区别）
• 运行一个，关闭应用程序，重新打开，运行另一个（仍然LastOrDefault更快）
• 将谓词设置为不在列表中的元素（仍然是一样的）
• 将谓词更改为多个合格对象（仍然是一样的）

• 创建一个降序列表而不是升序列表（没有区别）

  .Net Core版本：3.0

由于调试器可能不准确，我尝试了以下代码:

  Console.WriteLine(DateTime.Now + ":" + DateTime.Now.Millisecond);
  for (int i = 0; i < 1000; i++)
  {
    first(l);
  }
  Console.WriteLine(DateTime.Now + ":" + DateTime.Now.Millisecond);
  for (int i = 0; i < 1000; i++)
  {
    last(l);
  }
  Console.WriteLine(DateTime.Now + ":" + DateTime.Now.Millisecond);

在我的所有测试案例中，为什么LastOrDefault比FirstOrDefault快得那么明显呢？此外，FirstOrDefault返回了34秒，而LastOrDefault返回了23秒。

问题

为什么在我的所有测试案例中，LastOrDefault都比FirstOrDefault快得那么明显？

- Azzarrel

---

那么确切的结果是什么？你是如何测试的？你有考虑热身时间吗？ - Patrick Hofman

由于可枚举对象是一个列表，我非常怀疑在您遍历列表时，方向会有任何性能差异。它可以是 0..end 或者 end..0。没有其他的区别。 - Patrick Hofman

可能是因为FirstOrDefault使用枚举器和MoveNext，而LastOrDefault使用反向循环（对于List）。实际上取决于类型以及是否具有谓词。 - misticos

@steve16351 我认为这就是答案了。.NET Standard没有Last的优化，而且Last需要大约两倍的时间，正如你所预期的那样，但我在.NET Core中看到与OP相同的情况。 - Rawling

@RenéVogt 请查看Rawling的回答。我确定我在某个地方读到过它，它在.NET Core代码库中。 - Patrick Hofman

Answer 1

steve16351 在一条已删除的评论中指出，在.NET Core中，Last 有以下优化：

if (source is IList<TSource> list)
{
    for (int i = list.Count - 1; i >= 0; --i)
    {
        TSource result = list[i];
        if (predicate(result))
        {
            found = true;
            return result;
        }
    }
}

但是First不会这样做，它最终会运行：

foreach (TSource element in source)
{
    if (predicate(element))
    {
        found = true;
        return element;
    }
}

通过索引器访问列表元素可能比使用foreach和迭代器更快。相比之下，.NET Standard没有对Last进行这种优化，而是遍历完整个输入，所以Last的运行速度比你预期的First要慢。

- Rawling

---

哦，我已经想知道为什么他的评论消失得这么快了，当时看起来他是正确的，但当我重新加载页面时它就不见了。谢谢。 - Azzarrel

Answer 2

我尝试执行ExecuteFirst和ExecuteLast，甚至改变它们的执行顺序，但LastOrDefault总是比FirstOrDefault花费更多时间。

class Program
{
    static void Main(string[] args)
    {
        List<int> numbers = new List<int>();
        for (int i = 1; i <= 1000000; i++)
        {
            numbers.Add(i);
        }

        for (int i = 1; i <= 100; i++)
        {
            Stopwatch stopwatch = new Stopwatch();
            ExecuteFirst(ref stopwatch, ref numbers);
            stopwatch.Reset();
            ExecuteLast(ref stopwatch, ref numbers);
        }

        for (int i = 1; i <= 100; i++)
        {
            Stopwatch stopwatch = new Stopwatch();
            ExecuteLast(ref stopwatch, ref numbers);
            stopwatch.Reset();
            ExecuteFirst(ref stopwatch, ref numbers);
        }
    }

    private static void ExecuteFirst(ref Stopwatch stopwatch, ref List<int> numbers)
    {
        stopwatch.Start();
        int first = numbers.FirstOrDefault(x => x == 500000);
        stopwatch.Stop();
        Console.WriteLine("First: " + stopwatch.Elapsed);
    }

    private static void ExecuteLast(ref Stopwatch stopwatch, ref List<int> numbers)
    {
        stopwatch.Start();
        int last = numbers.LastOrDefault(x => x == 500000);
        stopwatch.Stop();
        Console.WriteLine("Last: " + stopwatch.Elapsed);
    }
}

ExecuteFirst then ExecuteLast版本的输出：

First: 00:00:00.0056298
Last: 00:00:00.0089494
First: 00:00:00.0039494
Last: 00:00:00.0084491
First: 00:00:00.0041225
Last: 00:00:00.0087664
First: 00:00:00.0039685
Last: 00:00:00.0083576
First: 00:00:00.0064472
Last: 00:00:00.0109716
First: 00:00:00.0041366
Last: 00:00:00.0111575
First: 00:00:00.0039746
Last: 00:00:00.0085590
First: 00:00:00.0040453
Last: 00:00:00.0083751
First: 00:00:00.0057352
Last: 00:00:00.0090655
First: 00:00:00.0041225
Last: 00:00:00.0081635
First: 00:00:00.0042336
Last: 00:00:00.0085277
First: 00:00:00.0038742
Last: 00:00:00.0088863
First: 00:00:00.0039309
Last: 00:00:00.0141321
First: 00:00:00.0044766
Last: 00:00:00.0088888
First: 00:00:00.0044096
Last: 00:00:00.0147227
First: 00:00:00.0042950
Last: 00:00:00.0177956
First: 00:00:00.0064265
Last: 00:00:00.0158906
First: 00:00:00.0051914
Last: 00:00:00.0177836
First: 00:00:00.0067148
Last: 00:00:00.0123487
First: 00:00:00.0045096
Last: 00:00:00.0113824
First: 00:00:00.0040213
Last: 00:00:00.0145903
First: 00:00:00.0061554
Last: 00:00:00.0123555
First: 00:00:00.0047815
Last: 00:00:00.0119132
First: 00:00:00.0055103
Last: 00:00:00.0141871
First: 00:00:00.0069865
Last: 00:00:00.0115481
First: 00:00:00.0052736
Last: 00:00:00.0167697
First: 00:00:00.0062566
Last: 00:00:00.0111363
First: 00:00:00.0051245
Last: 00:00:00.0120161
First: 00:00:00.0044649
Last: 00:00:00.0086359
First: 00:00:00.0039902
Last: 00:00:00.0089326
First: 00:00:00.0070409
Last: 00:00:00.0093965
First: 00:00:00.0047403
Last: 00:00:00.0143759
First: 00:00:00.0052523
Last: 00:00:00.0105465
First: 00:00:00.0072541
Last: 00:00:00.0113418
First: 00:00:00.0064120
Last: 00:00:00.0139322
First: 00:00:00.0062902
Last: 00:00:00.0173657
First: 00:00:00.0068329
Last: 00:00:00.0163935
First: 00:00:00.0056465
Last: 00:00:00.0100116
First: 00:00:00.0057379
Last: 00:00:00.0084148
First: 00:00:00.0058303
Last: 00:00:00.0167930
First: 00:00:00.0065232
Last: 00:00:00.0100014
First: 00:00:00.0039309
Last: 00:00:00.0093778
First: 00:00:00.0047291
Last: 00:00:00.0133724
First: 00:00:00.0044344
Last: 00:00:00.0095120
First: 00:00:00.0044793
Last: 00:00:00.0083334
First: 00:00:00.0048849
Last: 00:00:00.0091849
First: 00:00:00.0042633
Last: 00:00:00.0095615
First: 00:00:00.0074706
Last: 00:00:00.0081830
First: 00:00:00.0046968
Last: 00:00:00.0086369
First: 00:00:00.0055665
Last: 00:00:00.0088337
First: 00:00:00.0045883
Last: 00:00:00.0112508
First: 00:00:00.0078855
Last: 00:00:00.0149504
First: 00:00:00.0065615
Last: 00:00:00.0102155
First: 00:00:00.0046303
Last: 00:00:00.0104928
First: 00:00:00.0063564
Last: 00:00:00.0119335
First: 00:00:00.0048461
Last: 00:00:00.0092795
First: 00:00:00.0042306
Last: 00:00:00.0090954
First: 00:00:00.0042236
Last: 00:00:00.0090376
First: 00:00:00.0039102
Last: 00:00:00.0087163
First: 00:00:00.0047897
Last: 00:00:00.0093651
First: 00:00:00.0051779
Last: 00:00:00.0101453
First: 00:00:00.0041795
Last: 00:00:00.0086312
First: 00:00:00.0039371
Last: 00:00:00.0087337
First: 00:00:00.0048348
Last: 00:00:00.0114352
First: 00:00:00.0049419
Last: 00:00:00.0134430
First: 00:00:00.0063191
Last: 00:00:00.0096597
First: 00:00:00.0041087
Last: 00:00:00.0100510
First: 00:00:00.0055977
Last: 00:00:00.0122221
First: 00:00:00.0046453
Last: 00:00:00.0097579
First: 00:00:00.0050965
Last: 00:00:00.0108959
First: 00:00:00.0061811
Last: 00:00:00.0093178
First: 00:00:00.0060297
Last: 00:00:00.0085977
First: 00:00:00.0040451
Last: 00:00:00.0114430
First: 00:00:00.0046424
Last: 00:00:00.0118572
First: 00:00:00.0064396
Last: 00:00:00.0147170
First: 00:00:00.0052414
Last: 00:00:00.0108874
First: 00:00:00.0045109
Last: 00:00:00.0082625
First: 00:00:00.0044640
Last: 00:00:00.0136483
First: 00:00:00.0049840
Last: 00:00:00.0087787
First: 00:00:00.0049482
Last: 00:00:00.0138222
First: 00:00:00.0055885
Last: 00:00:00.0109636
First: 00:00:00.0052437
Last: 00:00:00.0130392
First: 00:00:00.0053844
Last: 00:00:00.0103824
First: 00:00:00.0062271
Last: 00:00:00.0125599
First: 00:00:00.0043152
Last: 00:00:00.0091548
First: 00:00:00.0059537
Last: 00:00:00.0125432
First: 00:00:00.0057340
Last: 00:00:00.0099097
First: 00:00:00.0052127
Last: 00:00:00.0087050
First: 00:00:00.0045914
Last: 00:00:00.0095816
First: 00:00:00.0065290
Last: 00:00:00.0090501
First: 00:00:00.0045474
Last: 00:00:00.0108880
First: 00:00:00.0054650
Last: 00:00:00.0092074
First: 00:00:00.0042946
Last: 00:00:00.0129336
First: 00:00:00.0045581
Last: 00:00:00.0172552
First: 00:00:00.0058246
Last: 00:00:00.0080876
First: 00:00:00.0040249
Last: 00:00:00.0112583
First: 00:00:00.0047926
Last: 00:00:00.0085989
First: 00:00:00.0045357
Last: 00:00:00.0088068
First: 00:00:00.0039247
Last: 00:00:00.0094145
First: 00:00:00.0039182
Last: 00:00:00.0085856

ExecuteLast then ExecuteFirst版本的输出：

Last: 00:00:00.0087140
First: 00:00:00.0045242
Last: 00:00:00.0082524
First: 00:00:00.0040122
Last: 00:00:00.0081924
First: 00:00:00.0039598
Last: 00:00:00.0081365
First: 00:00:00.0041632
Last: 00:00:00.0087045
First: 00:00:00.0040455
Last: 00:00:00.0082440
First: 00:00:00.0041200
Last: 00:00:00.0082281
First: 00:00:00.0041470
Last: 00:00:00.0087138
First: 00:00:00.0039467
Last: 00:00:00.0082286
First: 00:00:00.0099966
Last: 00:00:00.0159285
First: 00:00:00.0059864
Last: 00:00:00.0103221
First: 00:00:00.0045370
Last: 00:00:00.0102541
First: 00:00:00.0042682
Last: 00:00:00.0081628
First: 00:00:00.0062049
Last: 00:00:00.0130017
First: 00:00:00.0046107
Last: 00:00:00.0146495
First: 00:00:00.0060628
Last: 00:00:00.0140509
First: 00:00:00.0042348
Last: 00:00:00.0087499
First: 00:00:00.0043035
Last: 00:00:00.0119328
First: 00:00:00.0053357
Last: 00:00:00.0095866
First: 00:00:00.0081749
Last: 00:00:00.0157497
First: 00:00:00.0065187
Last: 00:00:00.0165949
First: 00:00:00.0062613
Last: 00:00:00.0139213
First: 00:00:00.0058088
Last: 00:00:00.0121819
First: 00:00:00.0054371
Last: 00:00:00.0095390
First: 00:00:00.0070151
Last: 00:00:00.0110936
First: 00:00:00.0073251
Last: 00:00:00.0104844
First: 00:00:00.0058563
Last: 00:00:00.0131254
First: 00:00:00.0064146
Last: 00:00:00.0100039
First: 00:00:00.0045887
Last: 00:00:00.0102629
First: 00:00:00.0051754
Last: 00:00:00.0086035
First: 00:00:00.0041619
Last: 00:00:00.0104485
First: 00:00:00.0055513
Last: 00:00:00.0097863
First: 00:00:00.0047921
Last: 00:00:00.0097700
First: 00:00:00.0049790
Last: 00:00:00.0129902
First: 00:00:00.0049853
Last: 00:00:00.0090255
First: 00:00:00.0044574
Last: 00:00:00.0085991
First: 00:00:00.0061191
Last: 00:00:00.0144359
First: 00:00:00.0048091
Last: 00:00:00.0133516
First: 00:00:00.0056255
Last: 00:00:00.0084006
First: 00:00:00.0063759
Last: 00:00:00.0193624
First: 00:00:00.0062311
Last: 00:00:00.0176409
First: 00:00:00.0069601
Last: 00:00:00.0168154
First: 00:00:00.0069095
Last: 00:00:00.0099649
First: 00:00:00.0057600
Last: 00:00:00.0087139
First: 00:00:00.0040068
Last: 00:00:00.0085248
First: 00:00:00.0061416
Last: 00:00:00.0085084
First: 00:00:00.0043856
Last: 00:00:00.0089587
First: 00:00:00.0044830
Last: 00:00:00.0093276
First: 00:00:00.0043679
Last: 00:00:00.0110072
First: 00:00:00.0042437
Last: 00:00:00.0126469
First: 00:00:00.0042610
Last: 00:00:00.0112851
First: 00:00:00.0044525
Last: 00:00:00.0146068
First: 00:00:00.0067056
Last: 00:00:00.0126607
First: 00:00:00.0048659
Last: 00:00:00.0083654
First: 00:00:00.0062265
Last: 00:00:00.0097216
First: 00:00:00.0061381
Last: 00:00:00.0089756
First: 00:00:00.0042742
Last: 00:00:00.0106504
First: 00:00:00.0059941
Last: 00:00:00.0129825
First: 00:00:00.0052327
Last: 00:00:00.0086158
First: 00:00:00.0048668
Last: 00:00:00.0087767
First: 00:00:00.0040427
Last: 00:00:00.0097813
First: 00:00:00.0042703
Last: 00:00:00.0086771
First: 00:00:00.0051560
Last: 00:00:00.0097772
First: 00:00:00.0051117
Last: 00:00:00.0086385
First: 00:00:00.0050181
Last: 00:00:00.0092713
First: 00:00:00.0044719
Last: 00:00:00.0094507
First: 00:00:00.0041345
Last: 00:00:00.0090835
First: 00:00:00.0041929
Last: 00:00:00.0101841
First: 00:00:00.0045660
Last: 00:00:00.0132945
First: 00:00:00.0042977
Last: 00:00:00.0102504
First: 00:00:00.0041772
Last: 00:00:00.0087283
First: 00:00:00.0058613
Last: 00:00:00.0095019
First: 00:00:00.0058306
Last: 00:00:00.0098703
First: 00:00:00.0062143
Last: 00:00:00.0143740
First: 00:00:00.0058965
Last: 00:00:00.0146650
First: 00:00:00.0049196
Last: 00:00:00.0101419
First: 00:00:00.0045298
Last: 00:00:00.0096505
First: 00:00:00.0047797
Last: 00:00:00.0107579
First: 00:00:00.0059183
Last: 00:00:00.0126266
First: 00:00:00.0055267
Last: 00:00:00.0126165
First: 00:00:00.0054118
Last: 00:00:00.0120701
First: 00:00:00.0051365
Last: 00:00:00.0153770
First: 00:00:00.0053540
Last: 00:00:00.0153887
First: 00:00:00.0070967
Last: 00:00:00.0130810
First: 00:00:00.0058005
Last: 00:00:00.0099139
First: 00:00:00.0045073
Last: 00:00:00.0086909
First: 00:00:00.0050152
Last: 00:00:00.0092414
First: 00:00:00.0045098
Last: 00:00:00.0081899
First: 00:00:00.0039903
Last: 00:00:00.0088524
First: 00:00:00.0044292
Last: 00:00:00.0085165
First: 00:00:00.0041663
Last: 00:00:00.0079039
First: 00:00:00.0040911
Last: 00:00:00.0083395
First: 00:00:00.0041872
Last: 00:00:00.0093267
First: 00:00:00.0041617
Last: 00:00:00.0092689
First: 00:00:00.0042109
Last: 00:00:00.0088358
First: 00:00:00.0041233
Last: 00:00:00.0081352
First: 00:00:00.0046823
Last: 00:00:00.0085252
First: 00:00:00.0042007
Last: 00:00:00.0083383
First: 00:00:00.0041155
Last: 00:00:00.0096344
First: 00:00:00.0046664
Last: 00:00:00.0110845
First: 00:00:00.0047776

- Marco Salerno