Pourquoi les HashSets de structures avec des valeurs nulles sont-ils incroyablement lents?

J’ai enquêté sur la dégradation des performances et l’ai suivi pour ralentir les HashSets.
J’ai des structures avec des valeurs nulles qui sont utilisées comme clé primaire. Par exemple:

public struct NullableLongWrapper { private readonly long? _value; public NullableLongWrapper(long? value) { _value = value; } } 

J’ai remarqué que la création d’un HashSet est extrêmement lente.

Voici un exemple d’utilisation de BenchmarkDotNet : ( Install-Package BenchmarkDotNet )

 using System.Collections.Generic; using System.Linq; using BenchmarkDotNet.Atsortingbutes; using BenchmarkDotNet.Configs; using BenchmarkDotNet.Jobs; using BenchmarkDotNet.Running; public class Program { static void Main() { BenchmarkRunner.Run(); } } public class Config : ManualConfig { public Config() { Add(Job.Dry.WithWarmupCount(1).WithLaunchCount(3).WithTargetCount(20)); } } public struct NullableLongWrapper { private readonly long? _value; public NullableLongWrapper(long? value) { _value = value; } public long? Value => _value; } public struct LongWrapper { private readonly long _value; public LongWrapper(long value) { _value = value; } public long Value => _value; } [Config(typeof (Config))] public class HashSets { private const int ListSize = 1000; private readonly List _nullables; private readonly List _longs; private readonly List _nullableWrappers; private readonly List _wrappers; public HashSets() { _nullables = Enumerable.Range(1, ListSize).Select(i => (long?) i).ToList(); _longs = Enumerable.Range(1, ListSize).Select(i => (long) i).ToList(); _nullableWrappers = Enumerable.Range(1, ListSize).Select(i => new NullableLongWrapper(i)).ToList(); _wrappers = Enumerable.Range(1, ListSize).Select(i => new LongWrapper(i)).ToList(); } [Benchmark] public void Longs() => new HashSet(_longs); [Benchmark] public void NullableLongs() => new HashSet(_nullables); [Benchmark(Baseline = true)] public void Wrappers() => new HashSet(_wrappers); [Benchmark] public void NullableWrappers() => new HashSet(_nullableWrappers); } 

Résultat:

            Méthode |  Médiane |  Escaladé
 ----------------- | ---------------- | ---------
             Longs |  22.8682 nous |  0,42
     NullableLongs |  39.0337 nous |  0,62
          Enveloppes |  62.8877 nous |  1.00
  NullableWrappers |  231,993.7278 us |  3 540,34

L’utilisation d’une structure avec un Nullable par rapport à une structure long est 3540 fois plus lente!
Dans mon cas, il a fait la différence entre 800ms et <1ms.

Voici les informations d’environnement de BenchmarkDotNet:

OS = Microsoft Windows NT 6.1.7601 Service Pack 1
Processeur = Processeur Intel® Core i7-5600U 2.60 GHz, ProcessorCount = 4
Fréquence = 2536269 ticks, Résolution = 394.2799 ns, Minuterie = TSC
CLR = MS.NET 4.0.30319.42000, Arch = 64-bit RELEASE [RyuJIT]
GC = Poste de travail simultané
JitModules = clrjit-v4.6.1076.0

Quelle est la raison la performance est ce pauvre?

Cela est dû au fait que chacun des éléments de _nullableWrappers a le même code de hachage renvoyé par GetHashCode() , ce qui entraîne une dégradation du hachage en access O (N) plutôt qu’en O (1).

Vous pouvez le vérifier en imprimant tous les codes de hachage.

Si vous modifiez votre structure en tant que telle:

 public struct NullableLongWrapper { private readonly long? _value; public NullableLongWrapper(long? value) { _value = value; } public override int GetHashCode() { return _value.GetHashCode(); } public long? Value => _value; } 

ça marche beaucoup plus vite.

Maintenant, la question évidente est de savoir NullableLongWrapper le code de hachage de chaque NullableLongWrapper identique.

La réponse à cela est discutée dans ce fil . Cependant, il ne répond pas tout à fait à la question, puisque la réponse de Hans tourne autour de la structure ayant deux champs à choisir lors du calcul du code de hachage – mais dans ce code, il n’y a qu’un seul champ à choisir. (une struct ).

Cependant, la morale de cette histoire est la suivante: Ne vous fiez jamais au GetHashCode() par défaut pour les types de valeur!


Addenda

Je pensais que peut-être ce qui se passait était lié à la réponse de Hans dans le fil de discussion que j’avais lié – peut-être prenait-il la valeur du premier champ (le booléen) dans la Nullable ) et mes expériences indiquent-il liés – mais c’est compliqué:

Considérez ce code et sa sortie:

 using System; public class Program { static void Main() { var a = new Test {A = 0, B = 0}; var b = new Test {A = 1, B = 0}; var c = new Test {A = 0, B = 1}; var d = new Test {A = 0, B = 2}; var e = new Test {A = 0, B = 3}; Console.WriteLine(a.GetHashCode()); Console.WriteLine(b.GetHashCode()); Console.WriteLine(c.GetHashCode()); Console.WriteLine(d.GetHashCode()); Console.WriteLine(e.GetHashCode()); } } public struct Test { public int A; public int B; } Output: 346948956 346948957 346948957 346948958 346948959 

Notez que les deuxième et troisième codes de hachage (pour 1/0 et 0/1) sont identiques, mais que les autres sont tous différents. Je trouve cela étrange parce que changer clairement A change le code de hachage, tout comme changer B, mais étant donné deux valeurs X et Y, le même code de hachage est généré pour A = X, B = Y et A = Y, B = X.

(Cela ressemble à quelque chose de XOR qui se passe dans les coulisses, mais c’est deviner.)

Incidemment, ce comportement, dans lequel les deux champs peuvent être présentés comme consortingbuant au code de hachage, prouve que le commentaire dans la source de référence pour ValueType.GetHashType() est inexact ou incorrect:

Action: Notre algorithme de retour du hashcode est un peu complexe. Nous cherchons le premier champ non statique et obtenons son code de hachage. Si le type n’a pas de champs non statiques, nous renvoyons le code de hachage du type. Nous ne pouvons pas prendre le code de hachage d’un membre statique, car si ce membre est du même type que le type d’origine, nous nous retrouverons dans une boucle infinie.

Si ce commentaire était vrai, alors quatre des cinq codes de hachage dans l’exemple ci-dessus seraient les mêmes, puisque A a la même valeur, 0, pour tous ceux-là. (Cela suppose que A est le premier champ, mais vous obtenez les mêmes résultats si vous échangez les valeurs: Les deux champs consortingbuent clairement au code de hachage.)

Ensuite, j’ai essayé de changer le premier champ pour être un bool:

 using System; public class Program { static void Main() { var a = new Test {A = false, B = 0}; var b = new Test {A = true, B = 0}; var c = new Test {A = false, B = 1}; var d = new Test {A = false, B = 2}; var e = new Test {A = false, B = 3}; Console.WriteLine(a.GetHashCode()); Console.WriteLine(b.GetHashCode()); Console.WriteLine(c.GetHashCode()); Console.WriteLine(d.GetHashCode()); Console.WriteLine(e.GetHashCode()); } } public struct Test { public bool A; public int B; } Output 346948956 346948956 346948956 346948956 346948956 

Hou la la! Faire en sorte que le premier champ soit boolé rend tous les codes de hachage identiques, quelles que soient les valeurs de TOUS les champs!

Cela ressemble toujours à une sorte de bug pour moi.

Le bogue a été corrigé dans .NET 4, mais uniquement pour Nullable. Les types personnalisés génèrent toujours le mauvais comportement. la source

Cela est dû au comportement de GetHashCode (). S’il trouve des types de référence, il essaie d’obtenir le hachage à partir du premier champ de type non référence. Dans votre cas, il a été trouvé, et Nullable <> est aussi struct, donc il vient de sortir sa valeur booléenne privée (4 octets)