Hashset Performance Add Add VS enthält für vorhandene Elemente

Question

Aus irgendeinem Grund scheint es das Add Operation auf a HashSet ist langsamer als die Contains Betrieb, wenn das Element bereits in der vorhanden ist HashSet.

Hier ist Beweis:

    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

Warum ist Contains schneller als Add Für bereits bestehende Elemente?

Hinweis: Ich benutze das Stopwatch Erweiterung aus einer anderen Frage.

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

AKTUALISIEREN: Interne Tests haben gezeigt, dass der große Leistungsdiff nur in der X64 -Version des .NET -Frameworks auftritt. Mit der 32 -Bit -Version des Frameworks scheint die Version mit identischen Geschwindigkeit zu addieren (in der Tat scheint es, dass die Version mit dem enthält eine prozentuale Läufe in einigen Testläufen auf X64 -Versionen des Frameworks läuft. betreiben etwa 15% schneller.

Answer 1

Addifnotpresent führt eine zusätzliche Kluft durch, die nicht funktioniert. Schauen Sie sich die IL für enthält:

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

Dies berechnet den Bucket -Standort für den Hash -Code. Das Ergebnis wird am lokalen Speicherort 1 gespeichert.

Addifnotpresent macht etwas ähnliches, spart aber auch den berechneten Wert an Position 2, sodass er das Element in die Hash -Tabelle an dieser Position einfügen kann, wenn das Element nicht vorhanden ist. Dies speichert das, weil einer der Standorte später in der Schleife geändert wird, die nach dem Artikel gesucht wird. Wie auch immer, hier ist der entsprechende Code für 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

Wie auch immer, ich denke, die zusätzliche Kluft ist das, was dazu führt, dass sie mehr Zeit in Anspruch nehmen als enthält. Auf den ersten Blick sieht es so aus, als könnte diese zusätzliche Kluft berücksichtigt werden, aber ich kann nicht sicher sagen, ohne ein bisschen mehr Zeit zu verbringen, um die IL zu entschlüsseln.

Answer 2

Interessant, auf meiner Maschine (Dell Latitude D630, Dual-Core 2,2 GHz) bekomme ich für beide Tests nahezu identische Ergebnisse null Aktion vor den Tests. Zum Beispiel:

Ich führe die Tests mit dem genauen Code durch, den Sie in der Frage gegeben haben:

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

Wenn ich den Code auf diese Weise ändere:

Nach:

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

Hinzufügen:

watch.Time(null, 0);

Meine Ergebnisse werden:

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

Das scheint mir so, als ob etwas Seltsames im Inneren des Stopwatch Das verursacht diese Schwankungen.

Answer 3

Ich vermute, dass Sie Ihren Test aus Visual Studio durchgeführt haben AddIfNotPresent hinein Add Um zu unterdrücken, sehen Sie das Ergebnis einer zusätzlichen Indirektion in den Methodenaufrufen.

Wenn ich kompiliere und aus der Befehlszeile renne, um VS -Tricks zu entfernen ...

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

... dann gibt es keinen Leistungsunterschied.

Probenausgänge (repräsentativ für eine größere Anzahl von Tests):

35036174
35153818

35225763
34862330

35047377
35033323