c# - 为什么具有可为空值的结构的 HashSet 非常慢？

Question

我调查了性能下降并跟踪它以减慢 HashSets。
我有用作主键的具有可为空值的结构。例如:

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

结果:

           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

使用带有 Nullable<long> 的结构与具有 long 的结构相比慢了3540倍!
在我的例子中，它造成了 800 毫秒和 <1 毫秒之间的差异。

这是来自 BenchmarkDotNet 的环境信息:

OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Core(TM) i7-5600U CPU 2.60GHz, ProcessorCount=4
Frequency=2536269 ticks, Resolution=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

性能这么差的原因是什么？

Answer 1

发生这种情况是因为 _nullableWrappers 的每一个元素与 GetHashCode() 返回的哈希码相同，这导致哈希退化为 O(N) 访问而不是 O(1)。

您可以通过打印出所有哈希码来验证这一点。

如果你这样修改你的结构:

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 .然而，它并没有完全回答这个问题，因为汉斯的回答围绕着在计算哈希码时有两个字段可供选择的结构——但在这段代码中，只有一个字段可供选择——而且它是一种值类型(struct)。

但是，这个故事的寓意是:永远不要依赖默认值 GetHashCode()对于值类型!

---

附录

我认为可能发生的事情与我链接的线程中 Hans 的回答有关 - 也许它正在获取 Nullable<T> 中第一个字段(bool)的值。结构)，我的实验表明它可能是相关的 - 但它很复杂:

考虑这段代码及其输出:

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

请注意第二个和第三个哈希码(1/0 和 0/1)是如何相同的，但其他的都不同。我觉得这很奇怪，因为显然改变 A 会改变哈希码，改变 B 也会改变哈希码，但是给定两个值 X 和 Y，将为 A=X、B=Y 和 A=Y、B=X 生成相同的哈希码。

(这听起来像是在幕后发生了一些 XOR 事情，但这是猜测。)

顺便说一句，可以显示两个字段都有助于散列码的这种行为证明了 ValueType.GetHashType() 的引用源中的注释。不准确或错误:

Action: Our algorithm for returning the hashcode is a little bit complex. We look for the first non-static field and get it's hashcode. If the type has no non-static fields, we return the hashcode of the type. We can't take the hashcode of a static member because if that member is of the same type as the original type, we'll end up in an infinite loop.

如果该评论为真，则上述示例中的五个哈希码中有四个将相同，因为 A对于所有这些，都具有相同的值 0。 (假设 A 是第一个字段，但如果交换值，您会得到相同的结果:这两个字段显然都对哈希码有贡献。)

然后我尝试将第一个字段更改为 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

哇!因此，无论任何字段的值如何，将第一个字段设置为 bool 值都会使所有哈希码都相同!

这对我来说仍然像是某种错误。

该错误已在 .NET 4 中修复，但仅限于 Nullable。自定义类型仍然会产生不良行为。 source