在比较字典查找与多个数据时,意外的性能结果是.NET 4.7中的运算符

Question

我有问题,我需要根据对象类型进行动态调度.我需要调度的类型在编译时是已知的 - 在我的例子中它们是17.

我最初的猜测是使用a Dictionary<Type, Action<Object>>进行调度并obj.GetType()用于找出适当的操作.但后来我决定使用BenchmarkDotNet来看看我是否可以做得更好以及调度查找的确切成本.贝娄是我用于基准测试的代码.

public class Program
{
    private static readonly Object Value = Guid.NewGuid();
    private static readonly Dictionary<Type, Action<Object>> Dictionary = new Dictionary<Type, Action<Object>>()
    {
        [ typeof( Byte ) ] = x => Empty( (Byte)x ),
        [ typeof( Byte[] ) ] = x => Empty( (Byte[])x ),
        [ typeof( SByte ) ] = x => Empty( (SByte)x ),
        [ typeof( Int16 ) ] = x => Empty( (Int16)x ),
        [ typeof( UInt16 ) ] = x => Empty( (UInt16)x ),
        [ typeof( Int32 ) ] = x => Empty( (Int32)x ),
        [ typeof( UInt32 ) ] = x => Empty( (UInt32)x ),
        [ typeof( Int64 ) ] = x => Empty( (Int64)x ),
        [ typeof( UInt64 ) ] = x => Empty( (UInt64)x ),
        [ typeof( Decimal ) ] = x => Empty( (Decimal)x ),
        [ typeof( Single ) ] = x => Empty( (Single)x ),
        [ typeof( Double ) ] = x => Empty( (Double)x ),
        [ typeof( String ) ] = x => Empty( (String)x ),
        [ typeof( DateTime ) ] = x => Empty( (DateTime)x ),
        [ typeof( TimeSpan ) ] = x => Empty( (TimeSpan)x ),
        [ typeof( Guid ) ] = x => Empty( (Guid)x ),
        [ typeof( Char ) ] = x => Empty( (Char)x ),
    };


    [Benchmark]
    public void Switch() => Switch( Value );


    [Benchmark]
    public void Lookup() => Lookup( Value );


    private static void Switch( Object value )
    {
        if ( value is Byte ) goto L_Byte;
        if ( value is SByte ) goto L_SByte;
        if ( value is Int16 ) goto L_Int16;
        if ( value is UInt16 ) goto L_UInt16;
        if ( value is Int32 ) goto L_Int32;
        if ( value is UInt32 ) goto L_UInt32;
        if ( value is Int64 ) goto L_Int64;
        if ( value is UInt64 ) goto L_UInt64;
        if ( value is Decimal ) goto L_Decimal;
        if ( value is Single ) goto L_Single;
        if ( value is Double ) goto L_Double;
        if ( value is DateTime ) goto L_DateTime;
        if ( value is TimeSpan ) goto L_TimeSpan;
        if ( value is DateTimeOffset ) goto L_DateTimeOffset;
        if ( value is String ) goto L_String;
        if ( value is Byte[] ) goto L_ByteArray;
        if ( value is Char ) goto L_Char;
        if ( value is Guid ) goto L_Guid;

        return;

        L_Byte: Empty( (Byte)value ); return;
        L_SByte: Empty( (SByte)value ); return;
        L_Int16: Empty( (Int16)value ); return;
        L_UInt16: Empty( (UInt16)value ); return;
        L_Int32: Empty( (Int32)value ); return;
        L_UInt32: Empty( (UInt32)value ); return;
        L_Int64: Empty( (Int64)value ); return;
        L_UInt64: Empty( (UInt64)value ); return;
        L_Decimal: Empty( (Decimal)value ); return;
        L_Single: Empty( (Single)value ); return;
        L_Double: Empty( (Double)value ); return;
        L_DateTime: Empty( (DateTime)value ); return;
        L_DateTimeOffset: Empty( (DateTimeOffset)value ); return;
        L_TimeSpan: Empty( (TimeSpan)value ); return;
        L_String: Empty( (String)value ); return;
        L_ByteArray: Empty( (Byte[])value ); return;
        L_Char: Empty( (Char)value ); return;
        L_Guid: Empty( (Guid)value ); return;
    }


    private static void Lookup( Object value )
    {
        if ( Dictionary.TryGetValue( value.GetType(), out var action ) )
        {
            action( value );
        }
    }


    [MethodImpl( MethodImplOptions.NoInlining )]
    private static void Empty<T>( T value ) { }


    static void Main( string[] args )
    {
        BenchmarkRunner.Run( typeof( Program ) );

        Console.ReadLine();
    }
}

在我的例子中,我使用盒装Guid运行测试,这是手工制作的Switch功能中最糟糕的情况.至少可以说结果令人惊讶:

BenchmarkDotNet=v0.10.11, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.125)
    Processor=Intel Core i7-4790K CPU 4.00GHz (Haswell), ProcessorCount=8
    Frequency=3903988 Hz, Resolution=256.1483 ns, Timer=TSC
      [Host]     : .NET Framework 4.7 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2600.0
      DefaultJob : .NET Framework 4.7 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2600.0

     Method |     Mean |     Error |    StdDev |
    ------- |---------:|----------:|----------:|
     Switch | 13.21 ns | 0.1057 ns | 0.0989 ns |
     Lookup | 28.22 ns | 0.1082 ns | 0.1012 ns |

在最糟糕的情况下,开关功能快2倍.如果我重新排序ifs,那么最常见的类型首先是平均值,我希望它运行速度快3-5倍.

我的问题是18个检查如何比单个字典查找快得多？我错过了一些明显的东西吗

编辑:

原始测试是x64机器上的x86(Prefer 32bit)模式.我也在64版本的构建中运行测试:

    Method |      Mean |     Error |    StdDev |
---------- |----------:|----------:|----------:|
    Switch | 12.451 ns | 0.0600 ns | 0.0561 ns |
    Lookup | 22.552 ns | 0.1108 ns | 0.1037 ns |

Answer 1

我绝不是一个IL性能大师,但如果你反编译,特别是看IL,这是有道理的.

所述is操作者仅4的操作码(ldarg,isinst,ldnull,CGT),和在总每个开关部件只有7与添加的跳转.的动作部分Switch调用Empty()然后另一个6,得到17*7 + 6 = 125最大.

相比之下,Dictionary.TryGetValue可能只有一个方法调用,但在此内部它正在进行大量的工作散列,循环和比较值:

http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,2e5bc6d8c0f21e67

public bool TryGetValue(TKey key, out TValue value) {
    int i = FindEntry(key);
    if (i >= 0) {
        value = entries[i].value;
        return true;
    }
    value = default(TValue);
    return false;
}

http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,bcd13bb775d408f1

private int FindEntry(TKey key) {
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    return -1;
}

FindEntry单独的for循环内部每个循环有31个操作码,仅为此部分提供最多527个操作码.

这是非常基本的分析,但很容易看出开关应该更高效.通常情况下,您需要考虑性能与可读性和可维护性.如果使用字典查找为您提供更好的代码,那么性能损失(15ns)很少会超过该优势.