当前位置:网站首页>Looking for a small immutable dictionary with better performance

Looking for a small immutable dictionary with better performance

2020-11-09 16:06:29 InfoQ

{"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Dictionary Is a very common key value pair management data structure . But in the case of demanding performance , Dictionary search speed is not high . therefore , We need a faster solution ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Requirement specification "}]},{"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":" here , We need a PropertyInfo The mapping relationship corresponding to the delegate , So we can store 《"},{"type":"link","attrs":{"href":"https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Getter-Setter/","title":null},"content":[{"type":"text","text":" Looking for better performance dynamics Getter and Setter programme "}]},{"type":"text","text":"》 Commission referred to ."}]},{"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":" therefore , This dictionary has these features :"}]},{"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":" Once this dictionary is created, it doesn't need to be modified ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" There are not many dictionary items , Because usually one class There won't be too many attributes ."}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Solutions that "}]},{"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":" programme 1,Switch Expression method . Use expressions to generate a containing switch case Statement delegation ."}]},{"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":" programme 2, Array skip table . We know ,switch case The reason why it is more than continuous if else The reason to be fast is because it generates IL Contains a skip table algorithm . therefore , If we have a way to use consecutive numbers as subscripts , And an array . You can go to C# In the implementation of their own jump table ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Knowledge points "}]},{"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":" Create a delegate using an expression "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":"PropertyInfo There is one int MetadataToken attribute , According to current observation , You can know the properties in a type and its MetadataToken It seems to be continuous , Therefore, it can be used as a skip table after taking the module key."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" The so-called skip watch , It can be simply understood as , Use the subscript of the array to locate a specific element in the array ."}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Implementation code "}]},{"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":" here , Let's go straight to the code used in the benchmark ."}]},{"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":" among :"}]},{"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 Direct reading , No search "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"ArrayIndex Array skip table "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"SwitchExp Expression generation Switch programme "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Dic Traditional dictionary scheme "}]}]}]},{"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":" The benchmark "}]},{"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":" Conclusion "}]},{"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":" A dictionary is a real drag ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":"Framework Really pulling the hip ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":"Net 5 It's just too strong ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" Array skipping is the fastest of the indirect schemes ."}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":3},"content":[{"type":"text","text":" Chart "}]},{"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":" summary "}]},{"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":" Whether it's array skipping or expression Switch All solutions can solve this problem , And it's faster than using a dictionary ."}]},{"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":" But there is a problem , At present, the author has not found anything about MetadataToken Whether you really have the same as class The nature of continuity ."}]},{"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":" Therefore, it is recommended to use Switch Scheme realization ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" I'm just a knowledge Porter "}]},{"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":" Release notes "}]},{"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 Release , More colorful "}]}]}]},{"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 Release , The initial release "}]}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Use samples "}]},{"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 Examples 1"}]}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Share with others "}]},{"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":" Looking for better performance dynamics Getter and Setter programme "}]}]}]},{"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":" Looking for a smaller immutable dictionary with better performance "}]}]}]}]},{"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 Project address :"},{"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 Project address :"},{"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":" The author of this article : "},{"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":" Link to this article :"},{"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":" Copyright notice : "},{"type":"text","text":" All articles in this blog except special statement , All adopt  "},{"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":"  license agreement . Reprint please indicate the source !"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢