我调查了性能下降情况,并将其追踪到速度较慢的HashSets.
我有一些 struct ,它们的值可以为空,用作主键.例如:

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>的 struct 比使用带long的 struct 慢3540倍

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

操作系统=Microsoft Windows NT 6.1.7601 Service Pack 1
处理器=英特尔(R)酷睿(TM)i7-5600U CPU 2.60 GHz,ProcessorCount=4
频率=2536269刻度,分辨率=394.2799 ns,计时器=Tsc
clr=ms.net 4.0.30319.42000,Arch=64位版本[RyuJIT]
GC=并发 workstation
JitModules=clrjit-v4.6.1076.0

性能如此差的原因是什么?

推荐答案

这是因为_nullableWrappers的每个元素都有GetHashCode()返回的相同哈希代码,这导致哈希退化为O(N)访问,而不是O(1).

您可以通过打印出所有散列代码来验证这一点.

如果将 struct 修改为:

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.然而,它并没有完全回答这个问题,因为Hans的答案围绕着一个 struct ,该 struct 有两个字段,在计算哈希代码时可以从中 Select ——但在这段代码中,只有一个字段可以 Select ——它是一个值类型(a struct).

然而,这个故事的寓意是:Never rely on the default 100 for value types!


Addendum

我认为所发生的事情可能与Hans在我链接的线程中的答案有关-也许它取的是Nullable<T> struct 中第一个字段(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是第一个字段,但如果交换前后的值,会得到相同的结果:两个字段显然都是哈希代码的组成部分.)

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

哇!因此,如果将第一个字段设为布尔值,则无论任何字段的值是什么,所有散列代码都会得到相同的结果!

在我看来,这仍然像是某种窃听器.

The bug has been fixed in .NET 4, but only for Nullable. Custom types still yield the bad behavior. source

.net相关问答推荐

API响应返回null错误. NET MAUI

从窗体中移除另一个控件中引用的控件时获取设计时通知

双精度的 C++ 和 C# 十六进制值之间的差异

重新启动(回收)应用程序池

RNGCryptoServiceProvider 的优缺点

哪个单元测试框架?

编译错误:显式实现接口时修饰符 'public' 对此项目无效

NuGetPackageImportStamp 有什么用?

我不了解应用程序域

C#As的 VB.NET 类似功能

mscorlib 代表什么?

如何确定字符串是 C# 中的有效 IPv4 还是 IPv6 地址?

为什么 C# 不推断我的泛型类型?

DataGridView 在我的两个屏幕之一上的可怕重绘性能

等待 Async Void 方法调用以进行单元测试

.Net 中 AOP 的最佳实现是什么?

将记录器作为单身人士是一个好习惯吗?

如何获取命名空间中的所有类?

使用 LINQ 搜索树

如何将 MailMessage 对象作为 *.eml 或 *.msg 文件保存到磁盘