c# - List.Contains() 的循环实现看起来比内置的更快。是吗？如果是这样，为什么？

Question

( This question arises from a discussion that started here )

我正在比较寻找 true 的时间List<bool> 中的值使用 List.Contains()与那些用于手卷循环。

我看到的结果与其他人报告的结果不同。我已经在几个系统上试过了，在我试过的所有系统上，循环似乎快了 2 到 3.5 倍。这些系统的范围从使用 .Net 4 运行 XP 的 5 年前笔记本电脑到最近运行 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() (这应该使它比循环慢)它也在使用私有(private) _items[]数组，这避免了将用于我的循环实现的索引范围检查。

我有三个问题:

1. 其他人能否复制我看到的结果？ (记得在调试器之外运行发布版本。)
2. 如果是这样，谁能解释一下我的循环为什么比List.Contains() 快得多？ ？
3. 如果不是，谁能解释为什么我发现我的循环变快了？

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

[编辑]

我突然想到这可能与处理器有关。我试过的所有系统都有 Intel 处理器，尽管型号非常不同，从 3.8GHz 的四核到 1.6GHz 的 Pentium M 单核……

对于那些看到循环运行速度较慢的人，您是否在运行 Intel 处理器？

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 或优化编译器检查它们是否这样做。