为什么具有可空值的结构体的哈希集合非常慢？

Question

我调查了性能下降的原因，并将其追踪到缓慢的哈希集上。
我的结构体具有可为空的值，用作主键。例如：

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

结果：

           方法 |         中位数 |   缩放比例
---------------- |--------------- |----------
            长整型 |      22.8682 微秒 |     0.42
    可空长整型 |      39.0337 微秒 |     0.62
         包装类 |      62.8877 微秒 |     1.00
 可空包装类 | 231,993.7278 微秒 | 3,540.34

使用一个带有 Nullable<long> 的结构体与使用一个带有 long 的结构体相比慢了3540倍！
在我的情况下，这使得800毫秒和小于1毫秒之间的差别。

以下是从BenchmarkDotNet中提取的环境信息：

操作系统=Microsoft Windows NT 6.1.7601 Service Pack 1
处理器=Intel(R) Core(TM) i7-5600U CPU 2.60GHz，ProcessorCount=4
频率=2536269 滴答，分辨率=394.2799 纳秒，计时器=TSC
CLR=MS.NET 4.0.30319.42000，架构=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1076.0

为什么性能这么差呢？

- Kobi

---

我也尝试了使字段非只读，但没有帮助。 - Kobi

你是否在你的结构体中实现了 GetHashCode 和 Equals 方法？默认实现会使用反射。为了避免装箱，你还应该实现 IEquatable<NullableLongWrapper> 接口。 - Lee

@Lee - 不是的 - 这是一个完整的例子。没有实现 GetHashCode 和 Equals。不过这是一个很好的解决方法，我还没有尝试过。 - Kobi

这是你的实际代码吗？因为 long? 已经是一个“可空长整型包装器”（其实际类型为 Nullable<long>），所以没有必要为它创建一个结构体。 - BlueRaja - Danny Pflughoeft

@BlueRaja - 不，这只是一个能够演示问题的最小例子。我的真实结构体中有两个 long?。它类似于外部连接的结果，其中左边或右边可能是 null。 - Kobi

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的哈希码都相同。

答案在此主题中讨论过。然而，它并没有完全回答这个问题，因为Hans的回答围绕着结构体有两个字段可以选择计算哈希码-但在这段代码中，只有一个可供选择的字段，它是一个值类型（一个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时生成相同的哈希码。

（听起来好像背后发生了一些异或运算，但这只是猜测。）

顺便说一下，这种“BOTH”字段都可以显示为哈希码所贡献的行为证明了对于ValueType.GetHashType()的参考源代码中的注释是不准确或错误的：

“操作：我们返回哈希码的算法有点复杂。我们寻找第一个非静态字段并获取它的哈希码。如果类型没有非静态字段，则返回类型的哈希码。我们不能获取静态成员的哈希码，因为如果该成员与原始类型相同，我们将陷入无限循环。”

如果那个注释是真的，那么上面示例中的五个哈希码中的四个将是相同的，因为所有这些情况下， A 都具有相同的值 0。（这假设 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

哇！所以将第一个字段设置为布尔类型会使得所有哈希码都相同，无论其他任何字段的值是什么！

对我来说，这仍然看起来像某种错误。

.NET 4中修复了这个错误，但只针对可空类型。自定义类型仍然会产生不良行为。来源

- Matthew Watson

---

我太天真了，我相信了他们。谢谢！ - Kobi

“文档”大致表示“不要使用ValueType的默认GetHashCode”。在这种特殊情况下，可能与唯一字段被装箱有关。 - J0HN

此外，似乎任何具有 Nullable<T> 类型的第一个字段的 struct 都将返回相同的哈希码。可能与默认实现的工作方式有关，尽管 Hans 的答案没有提到 nullables。 - vgru

@MatthewWatson：但是Nullable<T>不是引用类型，它应该是一个struct，里面有一个额外的bool字段，对吧？ - vgru

是的，根据开发者的评论，这是一个错误。微软的实现与微软的评论不一致。唉，这种事情时有发生。 - eocron

Answer 2

这是由于结构体的 GetHashCode() 行为造成的。如果它发现引用类型，它会尝试从第一个非引用类型字段中获取哈希值。在你的情况下，它被找到了，并且 Nullable<> 也是结构体，因此它刚好弹出了它的私有布尔值（4个字节）。

- eocron

---

“内部布尔值”是什么意思？ - Matthew Watson

抱歉，我是指“私有的”。 - eocron

嗯，但是布尔值只有一个字节，但也许它在某个地方使用了地址。 - Matthew Watson

如果您没有指定对齐方式，则默认为4字节。机器字。这是为了性能而实现的标准。 - eocron