当前位置:网站首页>Looking for a small immutable dictionary with better performance
Looking for a small immutable dictionary with better performance
2020-11-08 19:28:00 【Newbe36524】
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 .
Requirement specification
here , We need a PropertyInfo The mapping relationship corresponding to the delegate , So we can store 《 Looking for better performance dynamics Getter and Setter programme 》 Commission referred to .
therefore , This dictionary has these features :
- Once this dictionary is created, it doesn't need to be modified .
- There are not many dictionary items , Because usually one class There won't be too many attributes .
Solutions that
programme 1,Switch Expression method . Use expressions to generate a containing switch case Statement delegation .
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 .
Knowledge points
- Create a delegate using an expression
- 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.
- 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 .
Implementation code
here , Let's go straight to the code used in the benchmark .
among :
- Directly Direct reading , No search
- ArrayIndex Array skip table
- SwitchExp Expression generation Switch programme
- Dic Traditional dictionary scheme
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);
}
} |
The benchmark
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 |
Conclusion
- A dictionary is a real drag .
- Framework Really pulling the hip .
- Net 5 It's just too strong .
- Array skipping is the fastest of the indirect schemes .
Chart
data
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 |
summary
Whether it's array skipping or expression Switch All solutions can solve this problem , And it's faster than using a dictionary .
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 .
Therefore, it is recommended to use Switch Scheme realization .
I'm just a knowledge Porter
Release notes
- Newbe.ObjectVisitor 0.2.10 Release , More colorful
- Newbe.ObjectVisitor 0.1.4 Release , The initial release
Use samples
Share with others
- Looking for better performance dynamics Getter and Setter programme
- Looking for a smaller immutable dictionary with better performance
GitHub Project address :https://github.com/newbe36524/Newbe.ObjectVisitor
Gitee Project address :https://gitee.com/yks/Newbe.ObjectVisitor
- The author of this article : newbe36524
- Link to this article : https://www.newbe.pro/Newbe.ObjectVisitor/Better-Performance-Small-Map/
- Copyright notice : All articles in this blog except special statement , All adopt BY-NC-SA license agreement . Reprint please indicate the source !
版权声明
本文为[Newbe36524]所创,转载请带上原文链接,感谢
边栏推荐
- CountDownLatch 瞬间炸裂!同基于 AQS,凭什么 CyclicBarrier 可以这么秀?
- Express framework
- CountDownLatch 瞬间炸裂!同基于 AQS,凭什么 CyclicBarrier 可以这么秀?
- How much disk IO does a byte of read file actually take place?
- 在Python中创建文字云或标签云
- 第一部分——第1章概述
- PHP生成唯一字符串
- To introduce to you, this is my flow chart software—— draw.io
- Iptables from introduction to mastery
- Swagger介绍和应用
猜你喜欢
SQL 速查
An online accident caused by improper use of thread pool
MongoDB数据库
在Python中创建文字云或标签云
Countdownlatch explodes instantly! Based on AQS, why can cyclicbarrier be so popular?
write文件一个字节后何时发起写磁盘IO
总结: 10月海外DeFi新项目,更多资管策略来了!
一分钟全面看懂forsage智能合约全球共享以太坊矩阵计划
AI perfume is coming. Will you buy it?
Your random IO hard disk
随机推荐
C / C + + knowledge sharing: function pointer and pointer function, can you understand after reading this article?
Simulink中封装子系统
【Elasticsearch 技术分享】—— 十张图带大家看懂 ES 原理 !明白为什么说:ES 是准实时的!
Array acquaintance
How much faster is a server equipped with a SSD than a mechanical hard disk
Dynamic ReLU:微软推出提点神器,可能是最好的ReLU改进 | ECCV 2020
c++ opencv4.3 sift匹配
11 important operations of Python list
Django之简易用户系统(3)
Flink's sink: a preliminary study
Implementation of warehouse management system with ABP (net core) + easyUI + efcore
Dynamic query processing method of stored procedure
An online accident caused by improper use of thread pool
第二章编程练习
Case analysis of entitycore framework
Simple process of reading pictures by QT program developed by Python
Process thread coroutine
在Python中创建文字云或标签云
Using k3s to create local development cluster
net.sf.json.JSONObject对时间戳的格式化处理