尋找性能更優秀的不可變小字典

  • 2020 年 11 月 10 日
  • 筆記

Dictionary 是一個很常用的鍵值對管理數據結構。但是在性能要求嚴苛的情況下,字典的查找速度並不高。所以,我們需要更快的方案。

需求說明

這裡,我們需要一個 PropertyInfo 和委託對應的映射關係,這樣我們就可以存儲《尋找性能更優秀的動態 Getter 和 Setter 方案》提到的委託。

因此,這個字典有這些特點:

  1. 這個字典一旦創建就不需要修改。
  2. 字典項目並不多,因為通常一個 class 不會有太多屬性。

方案說明

方案 1,Switch 表達式法。使用表達式生成一個包含 switch case 語句的委託。

方案 2,數組跳錶。我們知道,switch case 之所以比連續的 if else 要快的原因是因為其生成的 IL 中包含一個跳錶演算法。因此,如果我們有辦法使用連續數字作為下標,以及一個數組。就可以在 C# 中自己實現跳錶。

知識要點

  1. 使用表達式創建委託
  2. PropertyInfo 有一個 int MetadataToken 屬性,根據目前的觀察,可以知道在一個類型中的屬性其 MetadataToken 似乎是連續的,因此可以取模後作為跳錶的 key。
  3. 所謂的跳錶,可以簡單理解為,使用數組的下標來定位數組中的特定元素。

實現程式碼

這裡,我們直接給出基準測試中使用的程式碼。

其中:

  • 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

結論

  1. 字典真拉胯。
  2. Framework 真拉胯。
  3. Net 5 簡直太強了。
  4. 數組跳錶是非直接方案中最快的。

圖表

FuncSearch

數據

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

Newbe.ObjectVisitor