为什么具有可空值的结构体的hashset非常慢?

本文关键字：hashset 非常 结构体 为什么 空值 | 更新日期: 2023-09-27 18:06:08

我调查了性能下降的原因，并将其归结为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);
}
结果:

<>之前方法|中值|缩放----------------- |---------------- |---------朗斯| 22.8682 us | 0.42NullableLongs | 39.0337 us | 0.62包装| 62.8877 us | 1.00NullableWrappers | 231,993.7278 us | 3,540.34之前

使用Nullable<long>结构体比使用long结构体慢3540倍!
在我的例子中，它产生了800ms和<1ms之间的差异。

下面是来自BenchmarkDotNet的环境信息:

操作系统=Microsoft Windows NT 6.1.7601 Service Pack 1
处理器=Intel(R) Core(TM) i7-5600U CPU 2.60GHz, ProcessorCount=4
频率=2536269 ticks，分辨率=394.2799 ns，定时器=TSC
CLR =女士。NET 4.0.30319.42000, Arch=64位RELEASE [RyuJIT]
GC =并发工作站
JitModules = clrjit-v4.6.1076.0

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

为什么具有可空值的结构体的hashset非常慢?

发生这种情况是因为_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生成相同的哈希码。

(这听起来像是一些异或的东西在幕后发生，但这是猜测。)

顺便说一下，这两个字段都可以显示为哈希码贡献的行为证明了ValueType.GetHashType()参考源中的注释是不准确或错误的:

Action:返回哈希码的算法有点复杂。我们查找第一个非静态字段并获取它的哈希码。如果该类型没有非静态字段，则返回该类型的哈希码。不能取静态成员的哈希码，因为如果该成员与原始成员的类型相同，就会导致无限循环。

如果该注释为真，那么上面示例中的五个哈希码中的四个将是相同的，因为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值使所有哈希码都相同，无论任何字段的值如何!

在我看来这仍然像是某种bug。

这个错误已经在。net 4中修复了，但只针对Nullable。自定义类型仍然会产生不良行为。源

这是由于结构体GetHashCode()行为。如果它找到引用类型-它尝试从第一个非引用类型字段获取哈希值。在您的情况下，它被发现，Nullable<>也是结构，所以它只是弹出它的私有布尔值(4字节)

相关文章：