测量速度时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倍).

我看到的为什么包含可能比迭代搜索会比较慢一些讨论在这里(包含一般被实现,因此创建一个通用EqualityComparer对象与字符串处理时是不需要的),不过虽然实施之间的差异包含并IndexOf阐述在这里看看实现似乎只是确认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   ");

导致完全不同的时间,索引和包含更紧密的联系.我不知道如何或为什么这可能.

再次编辑:为了清楚起见,我几乎可以肯定时间的奇怪与我的计时功能的实现有关,尽管它可能与优化器有关.我看到通常,List.Contains比List.IndexOf慢,但不是所有的时间,并且改变我测量时间的顺序以某种方式给我不同的结果.我的问题是,导致上述时间不一致的原因是什么？

Answer 1

我会稍微谈一下,基准测试是一项复杂的艺术,并且有许多细微之处和陷阱.这种测试的更大问题是您正在快速分析代码.我在我的poky笔记本电脑上以8纳秒计时阵列搜索测试.这样的结果是强烈的海森堡式,测试本身显着影响测量.

要实现非常快速的代码,需要做很多事情.委托目标需要及时编译,委托需要绑定到jitted代码,委托调用始终是无法优化的间接调用.而同时()循环重复测试ITER时代本身的开销增加了.所有代码的执行时间都包含在测量中,但不包括您实际关注的内容.

测试结果的一个重要随机函数是处理器本身.现代的代码执行行为非常不确定.它们严格依赖于内存缓存的状态以及内核对代码执行方式的了解程度,分支预测器会严重影响执行时间.

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

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

这种行为都不容易被观察到并且相当随机.我使用的指南是相差15%或更少的测量值在统计上没有意义.

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

在这个测试中没有发生这种情况,字符串比较过于复杂.默认比较使用StringComparison.CurrentCulture,并且需要调用CLR帮助器方法,该方法参考oracle,该oracle根据Thread.CurrentCulture规定的内容说明如何比较字符串.该代码无法内联,因此优化器无法消除它.这发生在代码的内部循环中,因此无法消除任何内容.

因此,通过和大型,你得到的结果可能是不够准确,编写自己的Array.IndexOf()方法是在实际上在很短阵的最快方式.如果你看一下Array.IndexOf()源代码,这并不奇怪.添加null和Rank测试,使其适用于不符合要求的数组并依赖于Object.Equals()并不是免费的.这是非常快的,但你确实看到了开销,因为其余的代码是如此之快.

微软认为Array.IndexOf()确实值得开销的额外工作,它确实使更好的代码以更可诊断的方式失败并且更具普遍性.它在实际使用中足够便宜.

哪个是基准测试的关键,测试越接近程序中的实际使用,使用真实数据而不是猫和奶牛,测试结果越可靠.你到那儿相当怀疑.