测量速度时 List.Contains 和 List.IndexOf 的行为不一致

Question

我需要使用 C# 快速处理大量字符串。为了找到最快的方法，我一直在使用以下基准测试函数：

delegate void Test();
static void time(Test test, int iter, string label)
    {
        Stopwatch timer = new Stopwatch();
        timer.Reset();
        timer.Start();

        int i = 0;
        while (i < iter)
        {
            test();
            i++;
        }

        Console.WriteLine(label + ": " + timer.ElapsedMilliseconds.ToString());
        timer.Reset();
    }

当我运行这段代码时：

int iter = 10000000;
string[] array = new string[] { "cat", "dog", "horse", "cow", "dimorphodon", "a", "a", "dog", "horse", "cow", "dimorphodon", "a", "a", "pig" };
List<string> list = new List<string>(array);

time(() => { int i = 0; while (i < array.Length) { if (array[i] == "cat") { return; } i++; } return; }, iter, "array search near        ");
time(() => { int i = 0; while (i < array.Length) { if (array[i] == "pig") { return; } i++; } return; }, iter, "array search far         ");
time(() => { int i = Array.IndexOf(array, "cat"); }, iter, "array IndexOf near       ");
time(() => { int i = Array.IndexOf(array, "pig"); }, iter, "array IndexOf far        ");
time(() => { list.Contains("cat"); }, iter, "list contains near        ");
time(() => { list.Contains("pig"); }, iter, "list contains far         ");
time(() => { int i = list.IndexOf("cat"); }, iter, "list IndexOf near        ");
time(() => { int i = list.IndexOf("pig"); }, iter, "list IndexOf far         ");
time(() => { int i = 0; while (i < list.Count) { if (list[i] == "cat") { return; } i++; } return; }, iter, "list search near         ");
time(() => { int i = 0; while (i < list.Count) { if (list[i] == "pig") { return; } i++; } return; }, iter, "list search far          ");

启用优化后，我一直认为迭代搜索数组是最快的选择，搜索列表的速度稍慢，而 List.IndexOf 和 Array.IndexOf 是很多较慢（靠近列表前面的值慢 3-4 倍，索引越高，差距越小，大约 20-30 个元素时慢 2 倍），List.Contains 是所有元素中最慢的（比 IndexOf 慢 1.2 倍，有或没有优化）。

我看到一些关于为什么 Contains 可能比迭代搜索慢的讨论 here (Contains is implemented generically and so creates a generic EqualityComparer object that is unneeded when dealing with strings), but although the difference between the implementation of Contains and IndexOf is elaborated on here，仅查看实现似乎确认 contains 应该是相同的（它们都创建了一个通用的 EqualityComparer 并将其用于将列表的内部数组的元素与参数进行比较）。

这表明我的基准测试功能可能存在问题。我遗漏了 Contains 和 IndexOf 之间的差异，还是我的基准测试函数有问题？

编辑：我现在确定我的基准测试有问题。执行一组略有不同的测试：

time(() => { list.Contains("cat"); }, iter, "list short contains ");
time(() => { list.Contains("cat"); }, iter, "list short indexof  ");
time(() => { list.Contains("cat"); }, iter*10, "list long contains  ");
time(() => { list.Contains("cat"); }, iter*10, "list long indexof   ");
time(() => { list.Contains("cow"); }, iter, "list short contains ");
time(() => { list.Contains("cow"); }, iter, "list short indexof  ");
time(() => { list.Contains("cow"); }, iter * 10, "list long contains  ");
time(() => { list.Contains("c"); }, iter * 10, "list long indexof   ");

结果完全不同，indexof 和 contains 的表现更接近。我不知道这怎么可能或为什么可能。

再次编辑：明确地说，我几乎可以肯定计时的怪异与我对计时函数的实现有关，尽管它可能与优化器有关。我通常看到 List.Contains 比 List.IndexOf 慢，但不是所有时候，并且改变我测量时间的顺序会以某种方式给我不同的结果。我的问题是，导致上述时间不一致的原因是什么？

Answer 1

除非我弄错了，否则 List.Contains 只是遍历列表以查看某个项目是否存在。我不认为它是为快速查找而设计的。

尝试使用 HashSet 或 SortedList 进行测试。

Answer 2

我会对此稍加思考，基准测试是一门复杂的艺术，有许多微妙之处和陷阱。这种测试的更大问题是您正在分析 fast 的代码。我在我的笔记本电脑上将阵列搜索测试计时为 8 纳秒。这样的结果是强海森堡的，测试本身对测量有很大影响。

要使非常快速的代码执行，需要做很多事情。委托目标需要即时编译，委托需要绑定到 jitted 代码，委托调用始终是间接调用，无法优化。而重复测试 iter 次的 while() 循环本身会增加开销。所有执行时间包含在测量中但不是您真正关心的代码。

测试结果的一个重要随机因素是处理器本身。现代的具有极其不确定的代码执行行为。它们严重依赖于内存缓存的状态以及内核对代码执行方式的了解程度，分支预测器严重影响执行时间。

代码的放置会影响测试结果，这是处理器处理抖动生成的机器代码的副作用。处理器不再直接执行该代码。处理器的实际执行引擎执行完全不同类型的指令，微操作。针对类似 RISC 的处理器，微操作是简单的指令，可以轻松地分布在各种执行单元之间并乱序执行。像 Haswell 这样的处理器可以同时执行多达 8 个微操作。

这在实践中并不经常发生。处理器中一个非常重要的电路是指令解码器，它是需要将 x86 或 x64 机器代码转换为微操作的逻辑。这里的心智模型是一个即时编译器，就像 .NET 使用的那样。但有很大的不同，这是一个抖动，需要从一个非常复杂的指令集和可变长度指令转换为一个非常饥饿的执行引擎，每个时钟周期可以吞下 8 个微操作.这完全有效是一项了不起的壮举，我不知道硬件设计师是如何做到这一点的。实际上，解码器无法跟上该速率，并且如果代码是分支的，通常会落后。就像在您的 "near" 测试中一样。 L1 指令缓存中的代码对齐起着重要作用，这就是放置很重要的原因。不是你可以调整的旋钮。

None 这种行为很容易观察到，而且是相当随机的。我使用的准则是，相差 15% 或更少的测量值没有统计意义。

您的基准代码有缺陷，有些缺陷不会影响结果。一个严重的缺陷是您没有让代码完成任何事情，您没有使用计算结果。换句话说，您根本不使用 i 结果。抖动优化器喜欢这样的代码，最快的可能代码是不执行的代码。然后它可以将消除这样的代码。

在这个测试中不会发生这种情况，字符串比较太复杂了。默认比较使用 StringComparison.CurrentCulture，这需要调用一个 CLR 辅助方法，该方法咨询一个 oracle，该 oracle 说明应该如何根据 Thread.CurrentCulture 指示的内容比较字符串。该代码无法内联，因此优化器无法消除它。这发生在代码的内部循环中，因此无法消除任何内容。

所以总的来说，你得到的结果可能足够准确，编写自己的 Array.IndexOf() 方法是事实上最快的方法短数组。如果您查看 Array.IndexOf() source code，这就不足为奇了。添加 null 和 Rank 测试，使其适用于不一致的数组并依赖 Object.Equals() 并不是免费的。它非常快，但您确实看到了开销，因为其余代码非常快。

Microsoft 认为 Array.IndexOf() 的额外工作值得开销，它确实使 更好的 代码以更可诊断的方式失败并且更通用.在实际使用中已经足够便宜了。

benchmarking的关键，测试越接近程序中的实际应用，使用真实数据代替猫和牛，测试结果越可信。很怀疑你到达那里。

测量速度时 List.Contains 和 List.IndexOf 的行为不一致

Inconsistent behavior of List.Contains and List.IndexOf when measuring speed

c#

performance

benchmarking

list