Prestazioni di HashSet Aggiungi vs Contiene per elementi esistenti

Question

Per qualche motivo, sembra che l'operazione Aggiungi su un HashSet sia più lenta dell'operazione Contains quando l'elemento esiste già nell'elemento < code> HashSet .

Ecco la prova:

    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

Perché Contains è più veloce di Aggiungi per elementi già esistenti?

Nota: sto usando questa estensione Stopwatch da un'altra domanda 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;
    }

AGGIORNAMENTO : i test interni hanno rivelato che le differenze di prestazioni elevate si verificano solo sulla versione x64 di .NET framework. Con la versione a 32 bit del framework Contains sembra funzionare alla stessa velocità da aggiungere (in effetti sembra che la versione con il contenuto sia più lenta in alcune esecuzioni di test) Nelle versioni X64 del framework, la versione con il contenuto sembra correre circa il 15% più veloce.

Answer 1

AddIfNotPresent esegue una divisione aggiuntiva che Contains non esegue. Dai un'occhiata a 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

Questo sta calcolando la posizione del bucket per il codice hash. Il risultato viene salvato nella posizione di memoria locale 1.

AddIfNotPresent fa qualcosa di simile, ma salva anche il valore calcolato nella posizione 2, in modo che possa inserire l'elemento nella tabella hash in quella posizione se l'elemento non esiste. Lo fa risparmiando perché una delle posizioni viene modificata successivamente nel ciclo che va a cercare l'elemento. Ad ogni modo, ecco il codice pertinente per 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

Ad ogni modo, penso che la divisione extra sia ciò che sta causando Add per richiedere più tempo di Contiene. A prima vista, sembra che il divario in più possa essere preso in considerazione, ma non posso dirlo con certezza senza spendere un po 'più di tempo a decifrare l'IL.

Answer 2

Interessante, sulla mia macchina (Dell Latitude D630, dual-core 2,2 Ghz) Sto ottenendo risultati quasi identici per entrambi i test a meno che non esegua il cronometro contro un'azione null prima dei test. Ad esempio:

Eseguo i test con il codice esatto che hai fornito nella domanda:

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

Se modifico il codice in questo modo:

Dopo:

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

Add:

watch.Time(null, 0);

I miei risultati diventano:

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

Mi sembra che stia succedendo qualcosa di strano all'interno del Cronometro che sta causando queste fluttuazioni.

Answer 3

Suppongo che tu abbia eseguito il tuo test da Visual Studio che ha causato la soppressione di AddIfNotPresent in Aggiungi , quindi stai vedendo il risultato di un extra livello di riferimento indiretto nelle chiamate del metodo.

Se compilo ed eseguo dalla riga di comando per rimuovere qualsiasi trucco VS ...

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

... quindi non c'è differenza di prestazioni.

Output di esempio (rappresentativi di un numero maggiore di test):

35036174
35153818

35225763
34862330

35047377
35033323