14

何らかの理由で、 要素が に既に存在する場合の操作よりも、 でのAdd操作のHashSet方が遅いようです。ContainsHashSet

ここに証拠があります：

    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

既存の要素Containsよりも速いのはなぜですか?Add

注:Stopwatch別の 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;
    }

更新: 内部テストにより、大きなパフォーマンスの違いは .NET フレームワークの x64 バージョンでのみ発生することが明らかになりました。フレームワークの 32 ビット バージョンでは、Contains を追加するのと同じ速度で実行されるように見えます (実際、contains を含むバージョンは、一部のテスト実行でパーセント遅く実行されるようです)。フレームワークの X64 バージョンでは、contains を含むバージョンは約 15% 速く実行されます。

4

3 に答える 3

11

AddIfNotPresentは、Containsが実行しない追加の除算を実行します。含むのILを見てください：

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に保存するため、アイテムが存在しない場合は、その位置のハッシュテーブルにアイテムを挿入できます。場所の1つがアイテムを探しに行くループの後半で変更されるので、それはそれを保存します。とにかく、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がContainsよりも時間がかかる原因になっていると思います。一見、余分な分割を考慮に入れることができるように見えますが、ILの解読にもう少し時間を費やさなければ、はっきりとは言えません。

于 2009-03-09T23:12:51.300 に答える
1

興味深いことに、私のマシン (Dell 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これは、これらの変動を引き起こしている内部で何か奇妙なことが起こっているように思えます。

于 2009-03-09T22:20:38.693 に答える
1

私の推測では、Visual Studio からテストを実行したために inliningが抑制AddIfNotPresentされAddたため、メソッド呼び出しで余分なレベルの間接化の結果が表示されています。

コマンドラインからコンパイルして実行すると、VSのトリックを削除できます...

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

...では、パフォーマンスの違いはありません。

サンプル出力 (多数のテストの代表):

35036174
35153818

35225763
34862330

35047377
35033323
于 2009-03-09T22:29:40.200 に答える