Неизменяемый словарь Vs Dictionary Vs C5 Vs F # - производительность

Ответ 1

Стандартный словарь уже хорошо оптимизирован. Все, что действительно делает, когда вы выполняете поиск, вычисляет хэш предоставленного ключа (скорость которого зависит от типа ключа и того, как он реализует GetHashCode), операцию по модулю хэш-значения для поиска правильного ведра и затем он выполняет итерацию через содержимое ведра до тех пор, пока не найдет правильное значение (скорость которого зависит от качества функции GetHashCode, поэтому, если ведра хорошо сбалансированы и не содержат слишком много элементов, а скорость метода Equals для типа).

В целом, это не так много для поиска, поэтому я не думаю, что вы сможете найти значительно более быструю общую структуру данных. Однако возможно, что в зависимости от того, как вы планируете использовать словари, вы можете создать более специализированное решение. Например, мне нужен был очень быстрый поиск, где ключ был типом. Вместо использования словаря и выполнения dictionary[typeof(T)] я сделал общий класс следующим образом:

class ValueStore<T> 
{
  public static T Value;
}

Так что я мог бы просто сделать ValueStore<T>.Value с накладными расходами с нулевым поиском.

Действительно ли вы можете сделать что-то подобное (и стоит ли это), действительно зависит от вашего использования; сколько элементов будет храниться в структуре, как часто она считывается и записывается, должна ли она быть потокобезопасной, насколько важна скорость записи и т.д. Например, если скорость записи вообще не имеет значения, но если требуется безопасность потока, вам нужно будет сделать копию на запись, где структура данных никогда не будет записана, а вместо этого скопирована, обеспечивая безопасность потоков и незаблокированные (таким образом: быстрые) чтения за счет скорости записи. Специализируясь на нем, можно было бы переупорядочить структуру записей, чтобы оптимизировать ее, чтобы хэш-ведра не содержали больше N элементов.

PS: если вы действительно отчаянно нуждались в скорости, но не могли создать более специализированную структуру данных, тогда вы могли бы получить небольшую прибыль от копирования Dictionary<TKey,TValue> и удаления различных проверок работоспособности (нулевые проверки и т.д.) и виртуального/интерфейса вызовы методов. Однако я сомневаюсь, что это даст вам более 20% выигрыша, если это.

Ответ 2

Ваше предположение о том, что неизменяемые словари допускают более быстрый поиск, неверно, потому что почти во всех неизменяемых коллекциях удается избежать копирования всей структуры при "модификации" путем хранения данных в дереве и копирования только некоторых узлов при "модификации". ', разделяя все остальные узлы. И доступ к дереву, как правило, будет медленнее, чем доступ к плоскому массиву по индексу, как это делают изменчивые кузены.

Я сравнил производительность однопотокового чтения из Dictionary<,>, ConcurrentDictionary<,> и ImmutableDictionary<,> на основе вашего кода.

средние результаты 30 прогонов после прогрева:

Чтобы почувствовать производительность записи, я также провел тест, который добавляет еще 50 записей в словари. Опять же, средние результаты 30 прогонов после прогрева:

Проверено на

• .net 4.5.1
• Microsoft Bcl Immutable 1.0.34.0

Нотабене Следует отметить, что неизменяемые словари намного быстрее и/или допускают более высокий уровень параллелизма во многих реальных многопоточных приложениях, которые в противном случае должны были бы прибегать к медленным или подверженным ошибкам методам, таким как защитное копирование., блокировка и тому подобное, чтобы справиться с изменчивостью в лице потоков. Это особенно верно, если вам нужна способность к созданию снимков, например, для оптимистичного параллелизма, MVCC.

Кстати, если вы запустите свой пример кода как есть, значение как минимум для неизменяемого словаря будет весьма нетипичным в обычном (более продолжительном) приложении, потому что по какой-то причине неизменному словарю, очевидно, требуется время для разогрева. Разница в производительности огромна. Просто посмотрите на результаты первых 3 прогонов:

Items    Dict   Conc   Immu
===========================
   100   1.90   1.00 361.81
  1000   1.07   1.00   4.33
 10000   1.24   1.00   1.74
100000   1.00   1.33   2.71
---------------------------
   100   1.06   1.00   2.56
  1000   1.03   1.00   4.34
 10000   1.00   1.06   3.54
100000   1.00   1.17   2.76
---------------------------
   100   1.06   1.00   2.50
  1000   1.66   1.00   4.16
 10000   1.00   1.02   3.67
100000   1.00   1.26   3.13

Ваш вопрос касался производительности чтения (замороженных словарей), но характеристики дерева неизменяемых коллекций аналогичным образом отражаются на производительности записи:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
                       Mutable (amortized)  Mutable (worst)  Immutable 
───────────────────────────────────────────────────────────────────────
 Stack.Push            O(1)                 O(n)             O(1)      
 Queue.Enqueue         O(1)                 O(n)             O(1)      
 List.Add              O(1)                 O(n)             O(log n)  
 HashSet.Add           O(1)                 O(n)             O(log n)  
 SortedSet.Add         O(log n)             O(n)             O(log n)  
 Dictionary.Add        O(1)                 O(n)             O(log n)  
 SortedDictionary.Add  O(log n)             O(n log n)       O(log n)  
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Ответ 3

Структура карты F # реализована как двоичное дерево и, как таковая, на самом деле не является словарем. Как отметил здесь, самый быстрый из них вы можете получить в стандартном словаре .net.

Ответ 4

Вот еще несколько тестов.

.NET 4.5 версия 1.3.1 пакета System.Collections.Immutable, 64-разрядная версия.

Dictionary vs ImmutableDictionary:

BuilderBenchmark elapsed time
 Mutable   : Avg= 15.213, Stdev  4.591 [ms] (   10.2x)
 Immutable : Avg=155.883, Stdev 15.145 [ms]
BuilderBenchmark per op
 Mutable   : Avg=  0.152, Stdev  0.046 [us] (   10.2x)
 Immutable : Avg=  1.559, Stdev  0.151 [us]
SetItemBenchmark elapsed time
 Mutable   : Avg= 13.100, Stdev  2.975 [ms] (   30.4x)
 Immutable : Avg=397.932, Stdev 18.551 [ms]
SetItemBenchmark per op
 Mutable   : Avg=  0.131, Stdev  0.030 [us] (   30.4x)
 Immutable : Avg=  3.979, Stdev  0.186 [us]
LookupBenchmark elapsed time
 Mutable   : Avg=  9.439, Stdev  0.942 [ms] (    3.6x)
 Immutable : Avg= 34.250, Stdev  3.457 [ms]
LookupBenchmark per op
 Mutable   : Avg=  0.094, Stdev  0.009 [us] (    3.6x)
 Immutable : Avg=  0.343, Stdev  0.035 [us]

Dictionary vs ImmutableSortedDictionary:

BuilderBenchmark elapsed time
 Mutable   : Avg= 13.654, Stdev  5.124 [ms] (   34.5x)
 Immutable : Avg=471.574, Stdev 20.719 [ms]
BuilderBenchmark per op
 Mutable   : Avg=  0.137, Stdev  0.051 [us] (   34.5x)
 Immutable : Avg=  4.716, Stdev  0.207 [us]
SetItemBenchmark elapsed time
 Mutable   : Avg= 11.838, Stdev  0.530 [ms] (   37.6x)
 Immutable : Avg=444.964, Stdev 11.125 [ms]
SetItemBenchmark per op
 Mutable   : Avg=  0.118, Stdev  0.005 [us] (   37.6x)
 Immutable : Avg=  4.450, Stdev  0.111 [us]
LookupBenchmark elapsed time
 Mutable   : Avg=  9.354, Stdev  0.542 [ms] (    4.4x)
 Immutable : Avg= 40.988, Stdev  3.242 [ms]
LookupBenchmark per op
 Mutable   : Avg=  0.094, Stdev  0.005 [us] (    4.4x)
 Immutable : Avg=  0.410, Stdev  0.032 [us]

Я хотел знать, сколько будет более медленных неизменных коллекций. Обратите внимание, что весь пробег составляет 100 000 операций вставки. Я рад сообщить, что ухудшение производительности поиска составляет всего 4 раза, в то время как ухудшение производительности вставки - 10 раз, все еще довольно прилично. ImmutableDictionary явно превосходит ImmutableSortedDictionary, если вам не нужна сортированная структура данных.

Боковая заметка о копировании на поведение записи. Эти постоянные структуры данных на несколько порядков быстрее, чем любая наивная копия при реализации записи. Это было то, что я использовал. Также очень легко представить изменения (с обнаружением гонки данных) с помощью команды сравнения и свопинга CAS.

Приложения

Program.cs:

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;

using ImmutableDictionary = System.Collections.Immutable.ImmutableDictionary; // select implementation to benchmark here

namespace DictPerf
{
    class Program
    {
        static string alphaNum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

        static string NextString(Random r, char[] buf)
        {
            int i = 0, len = r.Next(buf.Length) + 1;
            for (; i < len; i++)
            {
                buf[i] = alphaNum[r.Next(alphaNum.Length)];
            }
            return new string(buf, 0, len);
        }

        static HashSet<string> strings = new HashSet<string>();

        private static void Seed()
        {
            var r = new Random();
            var buf = new char[64];
            for (int i = 0; i < 100000; i++)
            {
                strings.Add(NextString(r, buf));
            }
        }

        static void Main(string[] args)
        {
            Seed();

            Benchmark(RunDictionaryBuilderBenchmark, RunImmutableDictionaryBuilderBenchmark, "BuilderBenchmark");
            Benchmark(RunDictionarySetItemBenchmark, RunImmutableDictionarySetItemBenchmark, "SetItemBenchmark");
            Benchmark(RunDictionaryLookupBenchmark, RunImmutableDictionaryLookupBenchmark, "LookupBenchmark");
        }

        private static string Stats(IEnumerable<double> source)
        {
            var avg = source.Average();
            var variance = source.Select(val => (val - avg) * (val - avg)).Sum();
            var stdev = Math.Sqrt(variance / (source.Count() - 1));
            return $"Avg={avg,7:0.000}, Stdev{stdev,7:0.000}";
        }

        private static void Benchmark(Action<ICollection<string>, Stopwatch> benchmark1, Action<ICollection<string>, Stopwatch> benchmark2, string benchmarkName)
        {
            var xs = new List<double>();
            var ys = new List<double>();

            var sw = Stopwatch.StartNew();
            for (int i = 0; i < 10; i++)
            {
                sw.Restart();
                benchmark1(strings, sw);
                xs.Add(sw.Elapsed.TotalMilliseconds);
                sw.Restart();
                benchmark2(strings, sw);
                ys.Add(sw.Elapsed.TotalMilliseconds);
            }

            var x = xs.Average();
            var y = ys.Average();
            var a = xs.Select(v => v / 100).Average();
            var b = ys.Select(v => v / 100).Average();

            Console.WriteLine($"{benchmarkName} elapsed time");
            Console.WriteLine($" Mutable   : {Stats(xs)} [ms] ({y / x,7:0.0}x)");
            Console.WriteLine($" Immutable : {Stats(ys)} [ms]");
            Console.WriteLine($"{benchmarkName} per op");
            Console.WriteLine($" Mutable   : {Stats(xs.Select(v => v / 100))} [us] ({b / a,7:0.0}x)");
            Console.WriteLine($" Immutable : {Stats(ys.Select(v => v / 100))} [us]");
        }

        private static void RunDictionaryBuilderBenchmark(ICollection<string> strings, Stopwatch sw)
        {
            var d = new Dictionary<string, object>();
            foreach (var s in strings)
            {
                d[s] = null;
            }
        }

        private static void RunImmutableDictionaryBuilderBenchmark(ICollection<string> strings, Stopwatch sw)
        {
            var d = ImmutableDictionary.CreateBuilder<string, object>();
            foreach (var s in strings)
            {
                d[s] = null;
            }
            d.ToImmutableDictionary();
        }

        private static void RunDictionarySetItemBenchmark(ICollection<string> strings, Stopwatch sw)
        {
            var d = new Dictionary<string, object>();
            foreach (var s in strings)
            {
                d[s] = null;
            }
        }

        private static void RunImmutableDictionarySetItemBenchmark(ICollection<string> strings, Stopwatch sw)
        {
            var d = ImmutableDictionary.Create<string, object>();
            foreach (var s in strings)
            {
                d = d.SetItem(s, null);
            }
        }

        private static void RunDictionaryLookupBenchmark(ICollection<string> strings, Stopwatch timer)
        {
            timer.Stop();

            var d = new Dictionary<string, object>();
            foreach (var s in strings)
            {
                d[s] = null;
            }

            timer.Start();

            foreach (var s in strings)
            {
                object v;
                d.TryGetValue(s, out v);
            }
        }

        private static void RunImmutableDictionaryLookupBenchmark(ICollection<string> strings, Stopwatch timer)
        {
            timer.Stop();

            var d = ImmutableDictionary.CreateBuilder<string, object>();
            foreach (var s in strings)
            {
                d[s] = null;
            }
            var x = d.ToImmutableDictionary();

            timer.Start();

            foreach (var s in strings)
            {
                object v;
                x.TryGetValue(s, out v);
            }
        }
    }
}