既存の要素のHashSetパフォーマンスの追加と含有
-
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