なぜnull可能な値を持つ構造体のHashSetが非常に遅いのですか？

Question

私はパフォーマンスの低下を調査し、それを追跡してHashSetを遅くしました。
私は主キーとして使用されるnull可能な値を持つ構造体を持っています。たとえば：

public struct NullableLongWrapper 
{ 
    private readonly long? _value; 

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

私はHashSet<NullableLongWrapper>の作成は非常に緩慢であることに気づきました。ここで

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

結果：longを持つ構造体に比べNullable<long>を持つ構造体を使用して

 
      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 

が3540倍遅いです！
私の場合は、800msと<の差が1msです。ここで

はBenchmarkDotNetからの環境情報です：

OS =のMicrosoft Windows NT 6.1.7601 Service Pack 1を
プロセッサ=インテル（R）Core（TM）i7-5600U CPU 2.60GHz、ProcessorCount = 4
周波数= 2536269ティック、分解能= 394.2799 NS、タイマ= TSC
CLR = MS.NET 4.0.30319.42000、アーチ= 64ビットRELEASE [RyuJIT]
GC =同時ワークステーション
JitModules = clrjit-V4。 6.1076.0

なぜパフォーマンスが悪いのですか？

Answer 1

これは、_nullableWrappersの要素のすべてがGetHashCode()によって返された同じハッシュコードを持ち、その結果、O（1）ではなくO（N）アクセスに分解されるために起こります。

これを確認するには、すべてのハッシュコードを印刷します。

ように、あなたの構造体を変更した場合：

public struct NullableLongWrapper 
{ 
    private readonly long? _value; 

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

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

    public long? Value => _value; 
} 

それははるかに速く動作します。

ここで明らかなのは、すべてNullableLongWrapperのハッシュコードが同じであることです。

答えはdiscussed in this threadです。しかし、ハンスの答えはハッシュコードを計算するときに選択する2つのフィールドを持つ構造体を中心にしているので、これは疑問にはあまり答えていませんが、このコードでは選択できるフィールドは1つだけです。 （struct）。

ただし、この物語の道徳は次のとおりです。値の種類にはデフォルトのGetHashCode()を絶対に使用しないでください！

---

補遺

私は私がリンクされたスレッドでハンスの回答に関連して起こっていたかもしれないものをと思った - 多分それはの最初のフィールド（ブール値）の値を取っていましたNullable<T>構造体）、そして私の実験は、それが関連することができることを示している - しかし、それは複雑だ：

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 

：

はこのコードとその出力を考えてみましょう

2番目と3番目のハッシュコード（1/0と0/1の場合）がどのように同じであるが、他のハッシュコードはすべて異なっていることに注意してください。 AをX、B = Y、A = Y、B = Xに対して同じハッシュコードが生成されるため、Aを明示的に変更するとハッシュコードが変更されるので、これは奇妙です。

（一部のXORのものが舞台裏で起こっているようにそれは聞こえるが、それは推測です。）ちなみに

、両方のフィールドはハッシュコードに寄与することを示すことができるこの動作を証明している参照ソース内のコメントValueType.GetHashType()のために不正確または間違っている：

はアクション：当社のアルゴリズムハッシュコードを返すために少し複雑です。私たちは最初の非静的フィールドを探し、そのハッシュコードを取得します。型に非静的フィールドがない場合は、その型のハッシュコードを返します。そのメンバが元の型と同じ型の場合、無限ループに終わるので、静的メンバのハッシュコードを取得することはできません。

そのコメントが真であった場合Aはすべての人のための同じ値0を有しているので、上記の例では5つのハッシュコード4は、同じです。 （それはAを想定すると、最初のフィールドですが、あなたはあなたの周りの値を交換する場合、同じ結果を得る：。両方のフィールドが明確にハッシュコードに貢献）

それから私は、ブール値であることを最初のフィールドを変更してみました：

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 

うわー！したがって、最初のフィールドをboolにすると、フィールドのANYの値に関係なく、すべてのハッシュコードが同じになります！

これはまだ私に何らかのバグのようです。

バグは.NET 4では修正されていますが、Nullableに対してのみ修正されています。カスタムタイプは依然として悪い動作をもたらします。 source

Answer 2

これは、構造体GetHashCode（）の動作によるものです。参照型が見つかった場合は、最初の非参照型フィールドからハッシュを取得しようとします。あなたのケースではそれが見つかりました、Nullable <も構造体なので、それはそれがプライベートブール値（4バイト）をポップしました