Skip to main content

寻找性能更优秀的不可变小字典

Dictionary 是一个很常用的键值对管理数据结构。但是在性能要求严苛的情况下,字典的查找速度并不高。所以,我们需要更快的方案。

需求说明

这里,我们需要一个 PropertyInfo 和委托对应的映射关系,这样我们就可以存储《Newbe.ObjectVisitor/Better-Performance-Getter-Setter》提到的委托。

因此,这个字典有这些特点:

  1. 这个字典一旦创建就不需要修改。
  2. 字典项目并不多,因为通常一个 class 不会有太多属性。

方案说明

方案 1,Switch 表达式法。使用表达式生成一个包含 switch case 语句的委托。

方案 2,数组跳表。我们知道,switch case 之所以比连续的 if else 要快的原因是因为其生成的 IL 中包含一个跳表算法。因此,如果我们有办法使用连续数字作为下标,以及一个数组。就可以在 C#中自己实现跳表。

知识要点

  1. 使用表达式创建委托
  2. PropertyInfo 有一个 int MetadataToken 属性,根据目前的观察,可以知道在一个类型中的属性其 MetadataToken 似乎是连续的,因此可以取模后作为跳表的 key。
  3. 所谓的跳表,可以简单理解为,使用数组的下标来定位数组中的特定元素。

实现代码

这里,我们直接给出基准测试中使用的代码。

其中:

  • Directly 直接读,没有任何查找
  • ArrayIndex 数组跳表
  • SwitchExp 表达式生成 Switch 方案
  • Dic 传统字典方案
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using BenchmarkDotNet.Attributes;

namespace Newbe.ObjectVisitor.BenchmarkTest
{
[Config(typeof(Config))]
public class FuncSearchTest
{
private Func<Yueluo, object>[] _target;
private readonly Yueluo _yueluo;
private readonly Func<Yueluo, string> _func;
private readonly PropertyInfo _nameP;
private readonly Func<PropertyInfo, Func<Yueluo, object>> _switcher;
private readonly Dictionary<PropertyInfo, Func<Yueluo, object>> _dic;

public FuncSearchTest()
{
_yueluo = Yueluo.Create();
var propertyInfos = typeof(Yueluo).GetProperties().ToArray();

CreateCacheArrayD(propertyInfos);

_switcher = ValueGetter.CreateGetter<Yueluo, object>(propertyInfos,
info => Expression.SwitchCase(Expression.Constant(CreateFunc(info)), Expression.Constant(info)));
_dic = propertyInfos.ToDictionary(x => x, CreateFunc);

_nameP = typeof(Yueluo).GetProperty(nameof(Yueluo.Name));
_func = x => x.Name;
}

private void CreateCacheArrayD(IReadOnlyCollection<PropertyInfo> propertyInfos)
{
_target = new Func<Yueluo, object>[propertyInfos.Count];
foreach (var info in propertyInfos)
{
var key = GetKey(info);
var index = key % propertyInfos.Count;
_target[index] = CreateFunc(info);
}
}

private static Func<Yueluo, object> CreateFunc(PropertyInfo info)
{
var pExp = Expression.Parameter(typeof(Yueluo), "x");
var bodyExp = Expression.Property(pExp, info);
var finalExp =
Expression.Lambda<Func<Yueluo, object>>(Expression.Convert(bodyExp, typeof(object)), pExp);
return finalExp.Compile();
}

private static int GetKey(MemberInfo info)
{
var token = info.MetadataToken;
return token;
}

[Benchmark(Baseline = true)]
public string Directly() => _func(_yueluo);

[Benchmark]
public string ArrayIndex() => (string) _target[_nameP.MetadataToken % _target.Length](_yueluo);

[Benchmark]
public string SwitchExp() => (string) _switcher(_nameP)(_yueluo);

[Benchmark]
public string Dic() => (string) _dic[_nameP](_yueluo);
}
}

基准测试


BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.572 (2004/?/20H1)
Intel Xeon CPU E5-2678 v3 2.50GHz, 1 CPU, 24 logical and 12 physical cores
.NET Core SDK=5.0.100-rc.2.20479.15
[Host] : .NET Core 2.1.23 (CoreCLR 4.6.29321.03, CoreFX 4.6.29321.01), X64 RyuJIT
net461 : .NET Framework 4.8 (4.8.4250.0), X64 RyuJIT
net48 : .NET Framework 4.8 (4.8.4250.0), X64 RyuJIT
netcoreapp21 : .NET Core 2.1.23 (CoreCLR 4.6.29321.03, CoreFX 4.6.29321.01), X64 RyuJIT
netcoreapp31 : .NET Core 3.1.9 (CoreCLR 4.700.20.47201, CoreFX 4.700.20.47203), X64 RyuJIT
netcoreapp5 : .NET Core 5.0.0 (CoreCLR 5.0.20.47505, CoreFX 5.0.20.47505), X64 RyuJIT

结论

  1. 字典真拉胯。
  2. Framework 真拉胯。
  3. Net 5 简直太强了。
  4. 数组跳表是非直接方案中最快的。

图表

FuncSearch

数据

MethodJobRuntimeMeanErrorStdDevRatioRatioSDRank
Directlynet461.NET 4.6.10.9347 ns0.0363 ns0.0321 ns1.000.001
ArrayIndexnet461.NET 4.6.115.0904 ns0.3820 ns0.3752 ns16.130.642
SwitchExpnet461.NET 4.6.117.1585 ns0.0624 ns0.0521 ns18.300.563
Dicnet461.NET 4.6.134.3348 ns0.2447 ns0.2169 ns36.771.184
Directlynet48.NET 4.80.6338 ns0.0233 ns0.0218 ns1.000.001
ArrayIndexnet48.NET 4.815.3098 ns0.2794 ns0.2613 ns24.170.692
SwitchExpnet48.NET 4.817.8113 ns0.0740 ns0.0656 ns28.200.983
Dicnet48.NET 4.833.7930 ns0.4538 ns0.4245 ns53.361.644
Directlynetcoreapp21.NET Core 2.11.2153 ns0.1168 ns0.1434 ns1.000.001
ArrayIndexnetcoreapp21.NET Core 2.14.6545 ns0.1044 ns0.0871 ns4.010.512
SwitchExpnetcoreapp21.NET Core 2.18.1995 ns0.2567 ns0.2747 ns6.810.903
Dicnetcoreapp21.NET Core 2.124.2669 ns0.5440 ns0.5586 ns20.072.514
Directlynetcoreapp31.NET Core 3.10.7382 ns0.1148 ns0.1074 ns1.000.001
ArrayIndexnetcoreapp31.NET Core 3.14.3580 ns0.1299 ns0.1085 ns6.100.772
SwitchExpnetcoreapp31.NET Core 3.17.5985 ns0.1310 ns0.1161 ns10.451.413
Dicnetcoreapp31.NET Core 3.122.2433 ns0.2756 ns0.2443 ns30.614.204
Directlynetcoreapp5.NET Core 5.01.3323 ns0.0527 ns0.0493 ns1.000.001
ArrayIndexnetcoreapp5.NET Core 5.05.0058 ns0.1361 ns0.1206 ns3.770.152
SwitchExpnetcoreapp5.NET Core 5.09.0576 ns0.0985 ns0.0921 ns6.810.263
Dicnetcoreapp5.NET Core 5.020.4052 ns0.2724 ns0.2275 ns15.440.594

总结

不论是数组跳表还是表达式 Switch 方案都可以解决这个问题,而且都要比使用字典要快。

但是这里有一个问题,就是目前作者还没有找到任何有关 MetadataToken 是否真的具备同 class 连续的性质。

因此建议还是使用 Switch 方案实现。

我只是知识的搬运工


欢迎关注的我微信公众号,第一时间获取我的最新文章。