Looking for a small immutable dictionary with better performance

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 ：

1. Once this dictionary is created, it doesn't need to be modified .
2. 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

1. Create a delegate using an expression
2. 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.
3. 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

1. A dictionary is a real drag .
2. Framework Really pulling the hip .
3. Net 5 It's just too strong .
4. 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

• Working with Expression Trees in C#

Release notes

• Newbe.ObjectVisitor 0.2.10 Release , More colorful
• Newbe.ObjectVisitor 0.1.4 Release , The initial release

Use samples

• Newbe.ObjectVisitor Examples 1

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 ！