既存の要素のHashSetパフォーマンスの追加と含有

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

  •  06-07-2019
  •  | 
  •  

質問

何らかの理由で、 HashSet での Add 操作は、 Contains 操作が要素が< code> 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 よりも Contains が速いのはなぜですか？

注：別のSO質問からこの Stopwatch 拡張機能を使用しています。

    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;
    }

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

役に立ちましたか？

解決

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を解読するためにもう少し時間を費やさずに確実に言うことはできません。

他のヒント

私のマシン（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 内で奇妙なことが起こっているように思えます。

推測では、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