尋找性能更優秀的不可變小字典
- 2020 年 11 月 10 日
- 筆記
Dictionary 是一個很常用的鍵值對管理數據結構。但是在性能要求嚴苛的情況下,字典的查找速度並不高。所以,我們需要更快的方案。
需求說明
這裡,我們需要一個 PropertyInfo 和委託對應的映射關係,這樣我們就可以存儲《尋找性能更優秀的動態 Getter 和 Setter 方案》提到的委託。
因此,這個字典有這些特點:
- 這個字典一旦創建就不需要修改。
- 字典項目並不多,因為通常一個 class 不會有太多屬性。
方案說明
方案 1,Switch 表達式法。使用表達式生成一個包含 switch case 語句的委託。
方案 2,數組跳錶。我們知道,switch case 之所以比連續的 if else 要快的原因是因為其生成的 IL 中包含一個跳錶演算法。因此,如果我們有辦法使用連續數字作為下標,以及一個數組。就可以在 C# 中自己實現跳錶。
知識要點
- 使用表達式創建委託
- PropertyInfo 有一個 int MetadataToken 屬性,根據目前的觀察,可以知道在一個類型中的屬性其 MetadataToken 似乎是連續的,因此可以取模後作為跳錶的 key。
- 所謂的跳錶,可以簡單理解為,使用數組的下標來定位數組中的特定元素。
實現程式碼
這裡,我們直接給出基準測試中使用的程式碼。
其中:
- 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
|
結論
- 字典真拉胯。
- Framework 真拉胯。
- Net 5 簡直太強了。
- 數組跳錶是非直接方案中最快的。
圖表
數據
Method | Job | Runtime | Mean | Error | StdDev | Ratio | RatioSD | Rank |
---|---|---|---|---|---|---|---|---|
Directly | net461 | .NET 4.6.1 | 0.9347 ns | 0.0363 ns | 0.0321 ns | 1.00 | 0.00 | 1 |
ArrayIndex | net461 | .NET 4.6.1 | 15.0904 ns | 0.3820 ns | 0.3752 ns | 16.13 | 0.64 | 2 |
SwitchExp | net461 | .NET 4.6.1 | 17.1585 ns | 0.0624 ns | 0.0521 ns | 18.30 | 0.56 | 3 |
Dic | net461 | .NET 4.6.1 | 34.3348 ns | 0.2447 ns | 0.2169 ns | 36.77 | 1.18 | 4 |
Directly | net48 | .NET 4.8 | 0.6338 ns | 0.0233 ns | 0.0218 ns | 1.00 | 0.00 | 1 |
ArrayIndex | net48 | .NET 4.8 | 15.3098 ns | 0.2794 ns | 0.2613 ns | 24.17 | 0.69 | 2 |
SwitchExp | net48 | .NET 4.8 | 17.8113 ns | 0.0740 ns | 0.0656 ns | 28.20 | 0.98 | 3 |
Dic | net48 | .NET 4.8 | 33.7930 ns | 0.4538 ns | 0.4245 ns | 53.36 | 1.64 | 4 |
Directly | netcoreapp21 | .NET Core 2.1 | 1.2153 ns | 0.1168 ns | 0.1434 ns | 1.00 | 0.00 | 1 |
ArrayIndex | netcoreapp21 | .NET Core 2.1 | 4.6545 ns | 0.1044 ns | 0.0871 ns | 4.01 | 0.51 | 2 |
SwitchExp | netcoreapp21 | .NET Core 2.1 | 8.1995 ns | 0.2567 ns | 0.2747 ns | 6.81 | 0.90 | 3 |
Dic | netcoreapp21 | .NET Core 2.1 | 24.2669 ns | 0.5440 ns | 0.5586 ns | 20.07 | 2.51 | 4 |
Directly | netcoreapp31 | .NET Core 3.1 | 0.7382 ns | 0.1148 ns | 0.1074 ns | 1.00 | 0.00 | 1 |
ArrayIndex | netcoreapp31 | .NET Core 3.1 | 4.3580 ns | 0.1299 ns | 0.1085 ns | 6.10 | 0.77 | 2 |
SwitchExp | netcoreapp31 | .NET Core 3.1 | 7.5985 ns | 0.1310 ns | 0.1161 ns | 10.45 | 1.41 | 3 |
Dic | netcoreapp31 | .NET Core 3.1 | 22.2433 ns | 0.2756 ns | 0.2443 ns | 30.61 | 4.20 | 4 |
Directly | netcoreapp5 | .NET Core 5.0 | 1.3323 ns | 0.0527 ns | 0.0493 ns | 1.00 | 0.00 | 1 |
ArrayIndex | netcoreapp5 | .NET Core 5.0 | 5.0058 ns | 0.1361 ns | 0.1206 ns | 3.77 | 0.15 | 2 |
SwitchExp | netcoreapp5 | .NET Core 5.0 | 9.0576 ns | 0.0985 ns | 0.0921 ns | 6.81 | 0.26 | 3 |
Dic | netcoreapp5 | .NET Core 5.0 | 20.4052 ns | 0.2724 ns | 0.2275 ns | 15.44 | 0.59 | 4 |
總結
不論是數組跳錶還是表達式 Switch 方案都可以解決這個問題,而且都要比使用字典要快。
但是這裡有一個問題,就是目前作者還沒有找到任何有關 MetadataToken 是否真的具備同 class 連續的性質。
因此建議還是使用 Switch 方案實現。
我只是知識的搬運工
發布說明
使用樣例
番外分享
GitHub 項目地址://github.com/newbe36524/Newbe.ObjectVisitor
Gitee 項目地址://gitee.com/yks/Newbe.ObjectVisitor
- 本文作者: newbe36524
- 本文鏈接: //www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Small-Map/
- 版權聲明: 本部落格所有文章除特別聲明外,均採用 BY-NC-SA 許可協議。轉載請註明出處!