почему ExpandoObject намного медленнее, чем словарь?

Question

Я провел два теста.

1 - сколько времени требуется, чтобы добавить 100 тыс. Элементов.

2 - сколько поисков он может выполнить за 10 секунд, используя 100 тыс. Элементов.

мои результаты были такими

ExpandoObject Добавить счетчик 97075

Словарь Добавить счетчик 35

ExpandoObject Поиск счетчик 2396

Словарь Поиск счетчик 1957637

заключение:

Добавление элемента ExpandoObject было медленнее в 2773 раза.

Поиск элемента ExpandoObject был медленнее в 817 раз.

Почему ExpandoObject намного медленнее словаря ?

using System;
using System.Dynamic;
using System.Collections.Generic;
using System.Threading;

namespace c_sharp_benchmark

{
    class Program
    {
        static void Main(string[] args)
        {
            BenchmarkExpandoObjectAdd();
            BenchmarkDictionaryAdd();
            BenchmarkExpandoObjectSearch();
            BenchmarkDictionarySearch();
        }
        static void BenchmarkExpandoObjectAdd()
        {
            dynamic exp = new ExpandoObject();
            var expid = (IDictionary<string, object>)exp;
            Random rnd = new Random();
            long old = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
            int i;
            for (i = 0; i < 100000; i++)
            {
                expid.Add("Prop" + i, i);
            }
            Console.WriteLine("ExpandoObject Add counter " + (DateTimeOffset.UtcNow.ToUnixTimeMilliseconds() - old));
        }
        static void BenchmarkDictionaryAdd()
        {
            Dictionary<string, object> dic = new Dictionary<string, object>();
            Random rnd = new Random();


            long old = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
            int i;
            for (i = 0; i < 100000; i++)
            {
                dic.Add("Prop" + i, i);
            }
            Console.WriteLine("Dictionary Add counter " + (DateTimeOffset.UtcNow.ToUnixTimeMilliseconds() - old));
        }

        static void BenchmarkExpandoObjectSearch()
        {
            dynamic exp = new ExpandoObject();
            var expid = (IDictionary<string, object>)exp;
            Random rnd = new Random();
            int i;
            for (i = 0; i < 100000; i++)
            {
                expid.Add("Prop" + i, i);
            }
            int auxval;
            long when_stop = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds() + 10000;
            int counter = 0;
            while (when_stop > DateTimeOffset.UtcNow.ToUnixTimeMilliseconds())
            {
                ++counter;
                auxval = (int)expid["Prop" + rnd.Next(100000)];
            }
            Console.WriteLine("ExpandoObject Search counter " + counter / 10);
        }
        static void BenchmarkDictionarySearch()
        {
            Dictionary<string, object> dic = new Dictionary<string, object>();
            Random rnd = new Random();
            int i;
            for (i = 0; i < 100000; i++)
            {
                dic.Add("Prop" + i, i);
            }
            int auxval;
            long when_stop = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds() + 10000;
            int counter = 0;
            while (when_stop > DateTimeOffset.UtcNow.ToUnixTimeMilliseconds())
            {
                ++counter;
                auxval = (int)dic["Prop" + rnd.Next(100000)];
            }
            Console.WriteLine("Dictionary Search counter " + counter / 10);

        }
    }
}

Answer 1

Основное отличие состоит в том, что объект Expando выполняет линейный поиск o (n) для каждого TryGetValue / TrySetValue.

В то время как в реальном словаре используется GetHashCode() и выполняется поиск в очень маленьком сегменте элементов.

Это особенно заметно при создании больших объектов ExpandoObject, как в вашем тесте.

Это исходный код, который используют как TryGetValue, так и TrySetValue из ExpandoObject:

internal int GetValueIndexCaseSensitive(string name)
{
    for (int i = 0; i < _keys.Length; i++)
    {
        if (string.Equals(_keys[i], name, StringComparison.Ordinal))
        {
            return i;
        }
    }
    return -1;
}

Или посмотрите на код для BindGetOrInvokeMember

private DynamicMetaObject BindGetOrInvokeMember(DynamicMetaObjectBinder binder, string name, bool ignoreCase, DynamicMetaObject fallback, Func<DynamicMetaObject, DynamicMetaObject> fallbackInvoke)
{
    ExpandoClass @class = Value.Class;
    int valueIndex = @class.GetValueIndex(name, ignoreCase, Value);
    ParameterExpression parameterExpression = Expression.Parameter(typeof(object), "value");
    Expression test = Expression.Call(typeof(RuntimeOps).GetMethod("ExpandoTryGetValue"), GetLimitedSelf(), Expression.Constant(@class, typeof(object)), Expression.Constant(valueIndex), Expression.Constant(name), Expression.Constant(ignoreCase), parameterExpression);
    DynamicMetaObject dynamicMetaObject = new DynamicMetaObject(parameterExpression, BindingRestrictions.Empty);
    if (fallbackInvoke != null)
    {
        dynamicMetaObject = fallbackInvoke(dynamicMetaObject);
    }
    dynamicMetaObject = new DynamicMetaObject(Expression.Block(new ParameterExpression[1]
    {
        parameterExpression
    }, Expression.Condition(test, dynamicMetaObject.Expression, fallback.Expression, typeof(object))), dynamicMetaObject.Restrictions.Merge(fallback.Restrictions));
    return AddDynamicTestAndDefer(binder, Value.Class, null, dynamicMetaObject);
}

Кроме того, имеется некоторое количество размышлений vodoo, блокировки и литья для ExpandoObject