Warum sind HashSets von Strukturen mit Nullwerten unglaublich langsam?

Question

Ich untersuchte die Leistungseinbußen und verfolgte sie, um HashSets zu verlangsamen.
Ich habe Strukturen mit Nullable-Werten, die als Primärschlüssel verwendet werden. Zum Beispiel:

public struct NullableLongWrapper 
{ 
    private readonly long? _value; 

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

Ich bemerkte, dass ein HashSet<NullableLongWrapper> Schaffung außergewöhnlich langsam ist.

Hier ist ein Beispiel unter Verwendung von BenchmarkDotNet: (Install-Package BenchmarkDotNet)

using System.Collections.Generic; 
using System.Linq; 
using BenchmarkDotNet.Attributes; 
using BenchmarkDotNet.Configs; 
using BenchmarkDotNet.Jobs; 
using BenchmarkDotNet.Running; 

public class Program 
{ 
    static void Main() 
    { 
     BenchmarkRunner.Run<HashSets>(); 
    } 
} 

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<long?> _nullables; 
    private readonly List<long> _longs; 
    private readonly List<NullableLongWrapper> _nullableWrappers; 
    private readonly List<LongWrapper> _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<long>(_longs); 

    [Benchmark] 
    public void NullableLongs() => new HashSet<long?>(_nullables); 

    [Benchmark(Baseline = true)] 
    public void Wrappers() => new HashSet<LongWrapper>(_wrappers); 

    [Benchmark] 
    public void NullableWrappers() => new HashSet<NullableLongWrapper>(_nullableWrappers); 
} 

Ergebnis:

 
      Method |   Median | Scaled 
----------------- |---------------- |--------- 
      Longs |  22.8682 us |  0.42 
    NullableLongs |  39.0337 us |  0.62 
     Wrappers |  62.8877 us |  1.00 
NullableWrappers | 231,993.7278 us | 3,540.34 

eine Struktur mit einem Nullable<long> Verwendung im Vergleich zu einer Struktur mit einem long ist 3540-mal langsamer!
In meinem Fall machte es den Unterschied zwischen 800ms und < 1ms.

Hier ist die Umgebung Informationen aus BenchmarkDotNet:

OS = Microsoft Windows NT 6.1.7601 Service Pack 1
Processor = Intel (R) Core (TM) i7-5600U CPU 2.60GHz, ProcessorCount = Frequency 4
= 2.536.269 Zecken, Auflösung = 394,2799 ns, Timer = TSC
CLR = MS.NET 4.0.30319.42000, Arch = 64-Bit-RELEASE [RyuJIT]
GC = Concurrent Workstation
JitModules = clrjit-v4. 6.1076.0

Aus welchem ​​Grund ist die Leistung so schlecht?

Answer 1

Dies passiert, weil jedes der Elemente von _nullableWrappers den gleichen Hash-Code hat, der von GetHashCode() zurückgegeben wird, was dazu führt, dass das Hashing in O (N) -Zugriff degeneriert anstatt O (1).

Sie können dies überprüfen, indem Sie alle Hashcodes ausdrucken.

Wenn Sie Ihre Struktur als so ändern:

public struct NullableLongWrapper 
{ 
    private readonly long? _value; 

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

    public override int GetHashCode() 
    { 
     return _value.GetHashCode(); 
    } 

    public long? Value => _value; 
} 

es viel schneller arbeitet.

Nun ist die offensichtliche Frage, WARUM ist der Hash-Code jeder NullableLongWrapper gleich.

Die Antwort darauf ist discussed in this thread. Allerdings beantwortet es die Frage nicht ganz, da sich Hans 'Antwort darauf dreht, dass die Struktur ZWEI Felder hat, aus denen bei der Berechnung des Hash-Codes gewählt werden kann - aber in diesem Code gibt es nur ein Feld zur Auswahl - und es ist ein Werttyp (a struct).

Allerdings ist die Moral dieser Geschichte: Verlassen Sie sich nie auf die Standardeinstellung GetHashCode() für Werttypen!

---

Nachtrag

Ich dachte, dass vielleicht das, was ich im Zusammenhang mit Hans' Antwort im Thread verwendet war vorging - vielleicht den Wert des ersten Feldes wurde unter (der Bool) in der Nullable<T> struct) und meine Experimente zeigen, dass es in Zusammenhang stehen können - aber es ist kompliziert:

diesen Code Betrachten und seine Ausgabe:

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 

Beachten Sie, wie die zweiten und dritten Hash-Codes (für 1/0 und 0/1) gleich sind, aber die anderen sind alle unterschiedlich. Ich finde das merkwürdig, weil das Ändern von A den Hash-Code ändert, ebenso wie das Ändern von B, aber bei zwei Werten X und Y wird derselbe Hash-Code für A = X, B = Y und A = Y, B = X erzeugt.

(Das klingt wie einige XOR Sachen hinter den Kulissen passiert, aber das ist zu erraten.)

übrigens dieses Verhalten in den beiden Felder angezeigt werden können, um den Hash-Code beitragen beweist, dass der Kommentar in der Referenzquelle für ValueType.GetHashType() ist ungenau oder falsch:

Aktion: Unser Algorithmus der Hash-Code ist ein wenig komplex für die Rückkehr. Wir suchen nach dem ersten nicht statischen Feld und erhalten seinen Hashcode. Wenn der Typ keine nicht statischen Felder enthält, geben wir den Hashcode des Typs zurück. Wir können den Hash-Code eines statischen Members nicht verwenden, da dieser Member vom gleichen Typ wie der Originaltyp ist und in einer Endlosschleife endet.

Wenn das Kommentar wahr war, dann vier der fünf Hash-Codes in dem obigen Beispiel wäre das gleiche, da A den gleichen Wert hat, 0, für alle, die. (Das setzt voraus, A das erste Feld ist, aber Sie bekommen die gleichen Ergebnisse, wenn Sie die Werte tauschen um. Beiden Felder eindeutig den Hash-Code beitragen)

Dann habe ich versucht, das erste Feld Ändern ein Bool zu sein:

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 

Wow! Wenn Sie also das erste Feld zu einem Bool machen, werden alle Hash-Codes gleich, ungeachtet der Werte von ANY der Felder!

Das sieht immer noch wie eine Art Bug für mich aus.

Der Fehler wurde in .NET 4 behoben, aber nur für Nullable. Benutzerdefinierte Typen führen immer noch zu einem schlechten Verhalten. source

Answer 2

Dies ist aufgrund der Struktur GetHashCode() Verhalten. Wenn es Referenztypen findet, versucht es, Hash aus dem ersten Nicht-Referenztyp-Feld zu erhalten. In Ihrem Fall wurde es gefunden, und Nullable <> ist auch struct, so dass es nur seinen privaten booleschen Wert (4 Bytes) poped