HashSet性能添加vs包含现有元素

StackOverflow https://stackoverflow.com/questions/628141

  •  06-07-2019
  •  | 
  •  

题

由于某种原因， HashSet 上的 Add 操作似乎比 Contains 操作慢，当元素已经存在于<代码> HashSet的。

以下是证据：

    Stopwatch watch = new Stopwatch();
    int size = 10000;
    int iterations = 10000;


    var s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            s.Add(i);
        }
    }, iterations));

    s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    // outputs: 47,074,764

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            if (!s.Contains(i))
                s.Add(i);
        }
    }, iterations));

    // outputs: 41,125,219

为什么包含比已经存在的元素的 Add 更快？

注意：我正在使用另一个SO问题的秒表扩展名。

    public static long Time(this Stopwatch sw, Action action, int iterations) {
        sw.Reset();
        sw.Start();
        for (int i = 0; i < iterations; i++) {
            action();
        }
        sw.Stop();

        return sw.ElapsedTicks;
    }

UPDATE ：内部测试表明，大型性能差异只发生在.NET框架的x64版本上。使用32位版本的框架Contains似乎以相同的速度运行添加（实际上看起来带有包含的版本在某些测试运行中运行速度慢了一些）在X64版本的框架上，带有包含的版本似乎运行速度提高约15％。

有帮助吗？

解决方案

AddIfNotPresent执行Contains不执行的额外划分。看一下IL for Contains：

IL_000a:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_000f:  stloc.0
  IL_0010:  ldarg.0
  IL_0011:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0016:  ldloc.0
  IL_0017:  ldarg.0
  IL_0018:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001d:  ldlen
  IL_001e:  conv.i4
  IL_001f:  rem
  IL_0020:  ldelem.i4
  IL_0021:  ldc.i4.1
  IL_0022:  sub
  IL_0023:  stloc.1

这是计算哈希码的存储区位置。结果保存在本地内存位置1。

AddIfNotPresent做了类似的事情，但它也将计算值保存在位置2，这样如果项目不存在，它就可以将项目插入到该位置的哈希表中。这样做可以节省，因为其中一个位置稍后会在寻找项目的循环中进行修改。无论如何，这是AddIfNotPresent的相关代码：

IL_0011:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_0016:  stloc.0
  IL_0017:  ldloc.0
  IL_0018:  ldarg.0
  IL_0019:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001e:  ldlen
  IL_001f:  conv.i4
  IL_0020:  rem
  IL_0021:  stloc.1
  IL_0022:  ldarg.0
  IL_0023:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0028:  ldloc.0
  IL_0029:  ldarg.0
  IL_002a:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_002f:  ldlen
  IL_0030:  conv.i4
  IL_0031:  rem
  IL_0032:  ldelem.i4
  IL_0033:  ldc.i4.1
  IL_0034:  sub
  IL_0035:  stloc.2

无论如何，我认为额外的分歧是导致Add比Part包含更多时间的原因。乍一看，似乎可以将多余的分歧考虑在内，但我不能肯定地说，不花一点时间来破译IL。

其他提示

有趣的是，在我的机器上（戴尔Latitude D630，双核2.2 Ghz）我得到的测试几乎完全相同，除非我在测试之前针对 null 动作运行秒表。例如：

我使用你在问题中给出的确切代码运行测试：

Without Contains(): 8205794
With Contains():    8207596

如果我以这种方式修改代码：

后：

Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;

添加：

watch.Time(null, 0);

我的结果变成了：

Without Contains(): 8019129
With Contains():    8275771

在我看来， Stopwatch 内部会发生奇怪的事情，导致这些波动。

我的猜测是你从Visual Studio运行测试，导致 AddIfNotPresent 内嵌到 Add 被抑制，所以你看到了额外的结果方法调用中的间接级别。

如果我从命令行编译并运行以删除任何VS技巧...... 

> csc /o+ /t:exe Program.cs
> Program.exe

...然后没有性能差异。

样本输出（代表大量测试）：

35036174
35153818

35225763
34862330

35047377
35033323
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top