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

{"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Dictionary 是一个很常用的键值对管理数据结构。但是在性能要求严苛的情况下，字典的查找速度并不高。所以，我们需要更快的方案。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"需求说明"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"这里，我们需要一个 PropertyInfo 和委托对应的映射关系，这样我们就可以存储《"},{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Getter-Setter/","title":null},"content":[{"type":"text","text":"寻找性能更优秀的动态 Getter 和 Setter 方案"}]},{"type":"text","text":"》提到的委托。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"因此，这个字典有这些特点："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":null,"normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":"这个字典一旦创建就不需要修改。"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":"字典项目并不多，因为通常一个 class 不会有太多属性。"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"方案说明"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"方案 1，Switch 表达式法。使用表达式生成一个包含 switch case 语句的委托。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"方案 2，数组跳表。我们知道，switch case 之所以比连续的 if else 要快的原因是因为其生成的 IL 中包含一个跳表算法。因此，如果我们有办法使用连续数字作为下标，以及一个数组。就可以在 C# 中自己实现跳表。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"知识要点"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":null,"normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":"使用表达式创建委托"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":"PropertyInfo 有一个 int MetadataToken 属性，根据目前的观察，可以知道在一个类型中的属性其 MetadataToken 似乎是连续的，因此可以取模后作为跳表的 key。"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":"所谓的跳表，可以简单理解为，使用数组的下标来定位数组中的特定元素。"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"实现代码"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"这里，我们直接给出基准测试中使用的代码。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"其中："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Directly 直接读，没有任何查找"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"ArrayIndex 数组跳表"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"SwitchExp 表达式生成 Switch 方案"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Dic 传统字典方案"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"csharp"},"content":[{"type":"text","text":"using System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing System.Linq.Expressions;\nusing System.Reflection;\nusing BenchmarkDotNet.Attributes;\n\nnamespace Newbe.ObjectVisitor.BenchmarkTest\n{\n [Config(typeof(Config))]\n public class FuncSearchTest\n {\n private Func[] _target;\n private readonly Yueluo _yueluo;\n private readonly Func _func;\n private readonly PropertyInfo _nameP;\n private readonly Func> _switcher;\n private readonly Dictionary> _dic;\n\n public FuncSearchTest()\n {\n _yueluo = Yueluo.Create();\n var propertyInfos = typeof(Yueluo).GetProperties().ToArray();\n\n CreateCacheArrayD(propertyInfos);\n\n _switcher = ValueGetter.CreateGetter(propertyInfos,\n info => Expression.SwitchCase(Expression.Constant(CreateFunc(info)), Expression.Constant(info)));\n _dic = propertyInfos.ToDictionary(x => x, CreateFunc);\n\n _nameP = typeof(Yueluo).GetProperty(nameof(Yueluo.Name));\n _func = x => x.Name;\n }\n\n private void CreateCacheArrayD(IReadOnlyCollection propertyInfos)\n {\n _target = new Func[propertyInfos.Count];\n foreach (var info in propertyInfos)\n {\n var key = GetKey(info);\n var index = key % propertyInfos.Count;\n _target[index] = CreateFunc(info);\n }\n }\n\n private static Func CreateFunc(PropertyInfo info)\n {\n var pExp = Expression.Parameter(typeof(Yueluo), \"x\");\n var bodyExp = Expression.Property(pExp, info);\n var finalExp =\n Expression.Lambda>(Expression.Convert(bodyExp, typeof(object)), pExp);\n return finalExp.Compile();\n }\n\n private static int GetKey(MemberInfo info)\n {\n var token = info.MetadataToken;\n return token;\n }\n\n [Benchmark(Baseline = true)]\n public string Directly() => _func(_yueluo);\n\n [Benchmark]\n public string ArrayIndex() => (string) _target[_nameP.MetadataToken % _target.Length](_yueluo);\n\n [Benchmark]\n public string SwitchExp() => (string) _switcher(_nameP)(_yueluo);\n\n [Benchmark]\n public string Dic() => (string) _dic[_nameP](_yueluo);\n }\n}"}]},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"基准测试"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.572 (2004/?/20H1)\nIntel Xeon CPU E5-2678 v3 2.50GHz, 1 CPU, 24 logical and 12 physical cores\n.NET Core SDK=5.0.100-rc.2.20479.15\n [Host] : .NET Core 2.1.23 (CoreCLR 4.6.29321.03, CoreFX 4.6.29321.01), X64 RyuJIT\n net461 : .NET Framework 4.8 (4.8.4250.0), X64 RyuJIT\n net48 : .NET Framework 4.8 (4.8.4250.0), X64 RyuJIT\n netcoreapp21 : .NET Core 2.1.23 (CoreCLR 4.6.29321.03, CoreFX 4.6.29321.01), X64 RyuJIT\n netcoreapp31 : .NET Core 3.1.9 (CoreCLR 4.700.20.47201, CoreFX 4.700.20.47203), X64 RyuJIT\n netcoreapp5 : .NET Core 5.0.0 (CoreCLR 5.0.20.47505, CoreFX 5.0.20.47505), X64 RyuJIT"}]},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"结论"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":null,"normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":"字典真拉胯。"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":"Framework 真拉胯。"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":"Net 5 简直太强了。"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":"数组跳表是非直接方案中最快的。"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":"图表"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/9e/9e02126fc21282fe892c07571757fc56.png","alt":"FuncSearch","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"heading","attrs":{"align":null,"level":3}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"总结"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"不论是数组跳表还是表达式 Switch 方案都可以解决这个问题，而且都要比使用字典要快。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"但是这里有一个问题，就是目前作者还没有找到任何有关 MetadataToken 是否真的具备同 class 连续的性质。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"因此建议还是使用 Switch 方案实现。"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"我只是知识的搬运工"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://tyrrrz.me/blog/expression-trees","title":null},"content":[{"type":"text","text":"Working with Expression Trees in C#"}]}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"发布说明"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Release-Note-0-2-10/","title":null},"content":[{"type":"text","text":"Newbe.ObjectVisitor 0.2.10 发布，更花里胡哨"}]}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Release-Note-0-1-4/","title":null},"content":[{"type":"text","text":"Newbe.ObjectVisitor 0.1.4 发布，初始版本"}]}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"使用样例"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Example-1/","title":null},"content":[{"type":"text","text":"Newbe.ObjectVisitor 样例 1"}]}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"番外分享"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Getter-Setter/","title":null},"content":[{"type":"text","text":"寻找性能更优秀的动态 Getter 和 Setter 方案"}]}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Small-Map/","title":null},"content":[{"type":"text","text":"寻找性能更优秀的不可变小字典"}]}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"GitHub 项目地址："},{"type":"link","attrs":{"href":"https://github.com/newbe36524/Newbe.ObjectVisitor","title":null},"content":[{"type":"text","text":"https://github.com/newbe36524/Newbe.ObjectVisitor"}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Gitee 项目地址："},{"type":"link","attrs":{"href":"https://gitee.com/yks/Newbe.ObjectVisitor","title":null},"content":[{"type":"text","text":"https://gitee.com/yks/Newbe.ObjectVisitor"}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"本文作者： "},{"type":"text","text":"newbe36524"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"本文链接："},{"type":"text","text":" "},{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Small-Map/","title":null},"content":[{"type":"text","text":"https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Small-Map/"}]}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"版权声明： "},{"type":"text","text":"本博客所有文章除特别声明外，均采用 "},{"type":"link","attrs":{"href":"https://creativecommons.org/licenses/by-nc-sa/4.0/","title":null},"content":[{"type":"text","text":"BY-NC-SA"}]},{"type":"text","text":" 许可协议。转载请注明出处！"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}