HashSet performance Add vs Contains pour les éléments existants

Question

Pour une raison quelconque, il semble que l'opération Add sur un HashSet soit plus lente que l'opération Contains lorsque l'élément existe déjà dans l'élément < code> HashSet .

En voici la preuve:

    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

Pourquoi contient est-il plus rapide que ajouter pour les éléments existants?

Remarque: j'utilise cette extension Chronomètre d'une autre question 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;
    }

UPDATE : des tests internes ont révélé que le gros différentiel de performances ne se produit que sur la version x64 du framework .NET. Avec la version 32 bits de la structure, la commande Contains semble être exécutée à la même vitesse (en fait, il semble que la version contenant le contient s’exécute un peu plus lentement dans certaines exécutions de test). Sur les versions X64 du cadre, la version contenant le conteneur semble courir environ 15% plus vite.

Answer 1

AddIfNotPresent effectue une division supplémentaire non contenue par Contains. Jetez un coup d’œil à l’IL pour 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

Ceci calcule l'emplacement du compartiment pour le code de hachage. Le résultat est enregistré à l'emplacement de la mémoire locale 1.

AddIfNotPresent fait quelque chose de similaire, mais enregistre également la valeur calculée à l'emplacement 2, afin qu'il puisse insérer l'élément dans la table de hachage à cet emplacement s'il n'existe pas. Cela permet d’économiser car l’un des emplacements est modifié plus tard dans la boucle qui cherche l’élément. Quoi qu’il en soit, voici le code correspondant à 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

Quoi qu'il en soit, je pense que la fracture supplémentaire est ce qui fait que Add prend plus de temps que Contient. À première vue, il semble que cette fracture supplémentaire puisse être prise en compte, mais je ne peux pas vous en assurer, sans passer un peu plus de temps à déchiffrer le livre des informations.

Answer 2

Intéressant, sur ma machine (Dell Latitude D630, dual-core 2,2 Ghz), les résultats des tests sont presque identiques, à moins d’exécuter le chronomètre avec une action null avant les tests. Par exemple:

Je lance les tests avec le code exact que vous avez donné à la question:

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

Si je modifie le code de cette manière:

Après:

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

Ajouter:

watch.Time(null, 0);

Mes résultats deviennent:

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

Cela me semble quelque chose d'étrange à l'intérieur du Chronomètre à l'origine de ces fluctuations.

Answer 3

Je suppose que vous avez exécuté votre test à partir de Visual Studio, ce qui a entraîné la suppression de AddIfNotPresent dans Add , de sorte que vous voyez le résultat d'un extra niveau d'indirection dans les appels de méthode.

Si je compile et lance à partir de la ligne de commande pour supprimer toute supercherie de VS ...

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

... alors il n'y a pas de différence de performance.

Exemples de résultats (représentatifs d'un plus grand nombre de tests):

35036174
35153818

35225763
34862330

35047377
35033323