List.Contains()的循环实现看起来比内置的快.是吗？如果是这样,为什么？

Question

(这个问题来自于此处开始的讨论)

我是比较时机与寻找true一个值List<bool>使用List.Contains()与那些手卷循环.

我看到其他人报道的结果不同.我已经在几个系统上尝试过它,在我尝试过的所有系统上,循环看起来要快2到3.5倍.这些系统的范围从运行XP.4的笔记本电脑到运行Windows 8和.Net 4.5的最新PC.

其他人报告的结果不同,即List.Contains()与循环速度大致相同或略快于循环.

这是我的测试代码.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    internal class Program
    {
        private static void Main()
        {
            int size = 10000000;
            int count = 10;
            List<bool> data = new List<bool>(size);

            for (int i = 0; i < size; ++i)
                data.Add(false);

            var sw = new Stopwatch();

            for (int trial = 0; trial < 5; ++trial)
            {
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaLoop(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaLoop()");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaListContains(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaListContains()");
                Console.WriteLine();
            }
        }

        static bool TestViaLoop(List<bool> data)
        {
            for (int i = 0; i < data.Count; ++i)
                if (data[i])
                    return true;

            return false;
        }

        static bool TestViaListContains(List<bool> data)
        {
            return data.Contains(true);
        }
    }
}

要测试此代码,您应该将其编译为x86 RELEASE构建,并从调试器外部运行它.

以下是我使用.Net 4.5框架的Windows 8 x64 PC的结果(尽管我在.Net 4中获得了类似的结果):

Times are in milliseconds

126 TestViaLoop()
441 TestViaListContains()

122 TestViaLoop()
428 TestViaListContains()

131 TestViaLoop()
431 TestViaListContains()

138 TestViaLoop()
426 TestViaListContains()

122 TestViaLoop()
439 TestViaListContains()

如您所见,循环在我的系统上花费大约1/3的时间.

现在,如果我们使用它Resharper来查看List.Contains()它的实现,看起来像这样:

bool Contains(T item)
{
    if (item == null)
    {
        for (int j = 0x0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    EqualityComparer<T> comparer = EqualityComparer<T>.Default;
    for (int i = 0x0; i < this._size; i++)
    {
        if (comparer.Equals(this._items[i], item))
        {
            return true;
        }
    }
    return false;
}

虽然它正在使用Comparer.Equals()(它应该使它比循环慢),但它也_items[]直接使用私有数组,这避免了将用于我的循环实现的索引范围检查.

我有三个问题:

1. 任何人都可以复制我看到的结果吗？(请记住在调试器外部运行发布版本.)
2. 如果是这样,有人可以解释我的循环如何比这快得多List.Contains()吗？
3. 如果没有,任何人都可以解释为什么我看到我的循环更快？

这不仅仅是学术上的兴趣,因为我编写的代码可以处理大量的数字数据,并且需要尽可能快,这是我需要了解的事情.(注意:是的,我描述了一些东西,只是尝试优化需要优化的东西......我知道过早优化的问题.)

[编辑]

我发现这可能与处理器有关.我尝试过的所有系统都配备了英特尔处理器,虽然型号从3.8GHz的四核到1.6GHz的奔腾M单核不等......

对于那些看到循环运行较慢的人,你在运行英特尔处理器吗？

Answer 1

它使用 GenericEqualityComparer，如果我们看一下 Equals 方法的实现，它看起来像这样：

public override bool Equals(T x, T y)
{
  if ((object) x != null)
  {
    if ((object) y != null)
      return x.Equals(y);
    else
      return false;
  }
  else
    return (object) y == null;
}

当它检查对象是否不等于 null 时，它会对它们进行装箱，并且您会得到两次装箱操作。此 IL 代码显示了它的外观：

IL_0002: box !T
IL_0007: ldnull
IL_0008: ceq

280Z28 编辑：相同方法的 CIL 在 .NET 4.5 中略有不同。

public override bool Equals(T x, T y)
{
    if (x != null)
        return ((y != null) && x.Equals(y));

    if (y != null)
        return false;

    return true;
}

这是IL。对于任何查看 Reflector 的人，请注意brfalse.s和brnull.s是相同的说明。

L_0000: ldarg.1 
L_0001: box !T
L_0006: brnull.s L_0021
...

基线 JIT 编译器不会优化掉盒子操作，但我还没有检查 NGen 或优化编译器以查看它们是否会这样做。