Задался вопросом: кто будет быстрее
обычный Dictionary на одном потоке
или ConcurrentDictionary на нескольких
Написал тест, результаты шокировали.
Даже на 8 ядерном процессоре Dictionary на одном потоке быстрее, чем ConcurrentDictionary на 8 потоках.
Ожидаемо самая высока производительность достигается при совпадении числа параллельных процессов с количеством ядер.
При дальнейшем увеличении количества параллельных процессов происходит деградация производительности.
Аномальные значения получаются при 2-х параллельных процессах, видимо на такое количество ядер оптимизированы механизмы синхронизации ConcurrentDictionary.

Вот тест:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace DictionariesTest
{
    class Program
    {
        private const int _itarationsCount = 8000000;

        static void Main(string[] args)
        {
            Dictionary<int, string> dictionary = new Dictionary<int, string>();

            Console.WriteLine("Testing Dictionary in single thread...");
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            for (int i = 0; i < 8000000; i++)
            {
                dictionary.Add(i, i.ToString());
            }
            stopwatch.Stop();
            Console.WriteLine("Add: {0}", stopwatch.ElapsedMilliseconds);


            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < 8000000; i++)
            {
                string s = dictionary[i];
            }
            stopwatch.Stop();
            Console.WriteLine("Get: {0}", stopwatch.ElapsedMilliseconds);
            Console.WriteLine(string.Empty);

            runConcurrentDictionaryTest(1);
            runConcurrentDictionaryTest(2);
            runConcurrentDictionaryTest(4);
            runConcurrentDictionaryTest(8);
            runConcurrentDictionaryTest(16);

            Console.ReadLine();
        }

        private static void runConcurrentDictionaryTest(int threadsCount)
        {
            ConcurrentDictionary<int, string> concurrentDictionary = new ConcurrentDictionary<int, string>();

            Console.WriteLine("Testing ConcurrentDictionary in {0} parallel treads...", threadsCount);

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            runInMultileThreads(threadsCount, i => concurrentDictionary.TryAdd(i, i.ToString()));
            stopwatch.Stop();
            Console.WriteLine("Add: {0}", stopwatch.ElapsedMilliseconds);

            stopwatch.Reset();
            stopwatch.Start();
            runInMultileThreads(threadsCount, i => {string result = concurrentDictionary[i];});
            stopwatch.Stop();
            Console.WriteLine("Get: {0}", stopwatch.ElapsedMilliseconds);

            Console.WriteLine(string.Empty);
        }

        private static void runInMultileThreads(int threadsCount, Action<int> iterationAction)
        {
            Thread[] threads = new Thread[threadsCount];
            int step = _itarationsCount / threadsCount;

            for (int threadNumber = 1; threadNumber <= threadsCount; threadNumber++)
            {
                int min = 1 + step * (threadNumber - 1);
                int max = step * threadNumber;
                Thread thread = new Thread(() =>
                {
                    for (int i = min; i <= max; i++)
                    {
                        iterationAction(i);
                    }
                });
                threads[threadNumber - 1] = thread;
            }

            foreach (Thread thread in threads)
            {
                thread.Start();
            }


            foreach (Thread thread in threads)
            {
                thread.Join();
            }

        }
    }
}

Результаты для Intel(R) Core(TM) i7-3770 @ 3.40GHz (8 логических ядра, 4 физических) процессора:

Testing Dictionary in single thread...
Add: 1959
Get: 103

Testing ConcurrentDictionary in 1 parallel treads...
Add: 5201
Get: 195

Testing ConcurrentDictionary in 2 parallel treads...
Add: 3787
Get: 102

Testing ConcurrentDictionary in 4 parallel treads...
Add: 4780
Get: 88

Testing ConcurrentDictionary in 8 parallel treads...
Add: 3425
Get: 70

Testing ConcurrentDictionary in 16 parallel treads...
Add: 5066
Get: 65

Здесь не понятны результаты для 2 параллельных процессов — выбиваются из тренда.




Результаты для Intel(R) Core(TM) i5-2400 (4 логических ядра, 4 физических):

Testing Dictionary in single thread...
Dictionary Add: 2606
Dictionary Get: 150

Testing ConcurrentDictionary in 1 parralel treads...
Add: 6448
Get: 359

Testing ConcurrentDictionary in 2 parallel treads...
Add: 4794
Get: 188

Testing ConcurrentDictionary in 4 parallel treads...
Add: 5239
Get: 279

Testing ConcurrentDictionary in 8 parallel treads...
Add: 6029
Get: 207

Testing ConcurrentDictionary in 16 parallel treads...
Add: 6500
Get: 294

Здесь не понятны результаты для 2 параллельных процессах — выбиваются из тренда.

Здравствуйте, igor-booch, Вы писали:

IB>Задался вопросом: кто будет быстрее
IB>обычный Dictionary на одном потоке
IB>или ConcurrentDictionary на нескольких
IB>Написал тест, результаты шокировали.
IB>Даже на 8 ядерном процессоре Dictionary на одном потоке быстрее, чем ConcurrentDictionary на 8 потоках.
1. Может имеет смысл сравнивать результаты с одинаковым числом потоков и необходимой для Dictionary синхронизацией? Ведь ConcurrentDictionary прикручен не для того что бы обгонять Dictionary на 1-м потоке, а для того что бы не требовалась синхронизация потоков при доступе к Dictionary.
2. Может имеет смысл замерять без времени создания потоков?

S>1. Может имеет смысл сравнивать результаты с одинаковым числом потоков и необходимой для Dictionary синхронизацией? Ведь ConcurrentDictionary прикручен не для того что бы обгонять Dictionary на 1-м потоке, а для того что бы не требовалась синхронизация потоков при доступе к Dictionary.
Тогда ConcurentDictionary будет быстрее конечно, у него механизмы синхронизации более низкоуровневные, чем в Monitor lock.
Такие тесты уже делались http://arbel.net/2013/02/03/best-practices-for-using-concurrentdictionary/
Я так понимаю что ConcurentDictionary нужен если программист выбирает между 2-мя следующими конструкциями:

lock (dictionary)
{
    dictionary.Add(key, value);
}

и

concurrentDictionary.TryAdd(key, value);

Здесь однозначно побеждает СoncurrentDictionary.

А если программист выбирает между

lock (locker)
{
    dictionary1.Add(key1, value1);
    dictionary2.Add(key2, value2);
    dictionary3.Add(key3, value3);
    dictionary4.Add(key4, value4);
    dictionary5.Add(key5, value5);
    dictionary6.Add(key6, value6);
    dictionary7.Add(key7, value7);
    dictionary8.Add(key8, value8);
    ...
}

и

concurrentDictionary1.TryAdd(key1, value1);
concurrentDictionary2.TryAdd(key2, value2);
concurrentDictionary3.TryAdd(key3, value3);
concurrentDictionary4.TryAdd(key4, value4);
concurrentDictionary5.TryAdd(key5, value5);
concurrentDictionary6.TryAdd(key6, value6);
concurrentDictionary7.TryAdd(key7, value7);
concurrentDictionary8.TryAdd(key8, value8);
...

то здесь скорей всего победит Dictionary.


S>2. Может имеет смысл замерять без времени создания потоков?
Сделал, результаты особо не изменились.

Здравствуйте, igor-booch, Вы писали:

S>>1. Может имеет смысл сравнивать результаты с одинаковым числом потоков и необходимой для Dictionary синхронизацией? Ведь ConcurrentDictionary прикручен не для того что бы обгонять Dictionary на 1-м потоке, а для того что бы не требовалась синхронизация потоков при доступе к Dictionary.
IB>Тогда ConcurentDictionary будет быстрее конечно, у него механизмы синхронизации более низкоуровневные, чем в Monitor lock.
Те же самые у него механизмы, тот же самый Monitor.Enter, только не весь контейнер блокируется эксклюзивно, а отдельные Bucket-ы + эксклюзивный GrowTable.
Кстати, именно эксклюзивным GrowTable можно объяснить увеличение времени работы на числе потоков > 2.

IB>Такие тесты уже делались http://arbel.net/2013/02/03/best-practices-for-using-concurrentdictionary/
IB>Я так понимаю что ConcurentDictionary нужен если программист выбирает между 2-мя следующими конструкциями:

Вот именно, назначение у ConcurrentDictionary другое. Это не быстрый словарь, это словарь, который в условиях многопоточности не нуждается в дополнительной синхронизации и работает быстрее чем обычный с синхронизацией.
И так как он использует те же самые Monitor.Enter для синхронизации, он по определению не сможет обогнать словарь без синхронизации на одном потоке. (если бы обогнал, то зачем бы нужен был Dictionary?).

Здравствуйте, igor-booch, Вы писали:

Всё дело в тестовых данных я думаю, он не предназначен для такого синтетического теста и обязан проваливать его.
ConcurrentDictionary использует кучу блокировок, для того что бы лочить только часть таблицы на время блокировки.
Однако он делает это на основе хэш кода — hashCode % numberOfLocks.
В результате — когда добавляем целочисленные ключи 1...N — имеем наихудший сценарий, когда все потоки последовательно бегут по всем блокировкам, и скорее всего ещё и дерутся за них.

Здравствуйте, igor-booch, Вы писали:

IB>Написал тест, результаты шокировали.
Тест не корректен: при тестировании параллельного кода в замеры времени попадает создание потоков.

S>Те же самые у него механизмы, тот же самый Monitor.Enter, только не весь контейнер блокируется эксклюзивно, а отдельные Bucket-ы + эксклюзивный GrowTable.
Да те же, чего-то мне показалось, что я там MemoryBarrier видел, наверное где-то в другом месте видел.


S>Кстати, именно эксклюзивным GrowTable можно объяснить увеличение времени работы на числе потоков > 2.
Можно поподробнее? Вот метод, который выполняется в начале GetRowTable:

    private void AcquireLocks(int fromInclusive, int toExclusive, ref int locksAcquired)
    {
      object[] objArray = this.m_tables.m_locks;
      for (int index = fromInclusive; index < toExclusive; ++index)
      {
        bool lockTaken = false;
        try
        {
          Monitor.Enter(objArray[index], ref lockTaken);
        }
        finally
        {
          if (lockTaken)
            ++locksAcquired;
        }
      }
    }

Почему они просто не написали, Monitor.Enter(this) для эксклюзивной блокировки?


S>И так как он использует те же самые Monitor.Enter для синхронизации, он по определению не сможет обогнать словарь без синхронизации на одном потоке. (если бы обогнал, то зачем бы нужен был Dictionary?).
Обгонял бы на 8 потоках, было бы с него больше толку.

0>Тест не корректен: при тестировании параллельного кода в замеры времени попадает создание потоков.
На результаты влияет незначительно

Здравствуйте, igor-booch, Вы писали:

0>>Тест не корректен: при тестировании параллельного кода в замеры времени попадает создание потоков.
IB>На результаты влияет незначительно
Верю, но тем не менее

Здравствуйте, igor-booch, Вы писали:

IB>Написал тест, результаты шокировали.
Попробуй заюзать Parallel.For

0>Тест не корректен: при тестировании параллельного кода в замеры времени попадает создание потоков.
Если тест служит для выбора между одно поточной реализацией и многопоточной, то все корректно: создание потоков это издержки многопоточной реализации

0>Попробуй заюзать Parallel.For
Медленней будет, Parallel.For каждую итерацию будет в отдельном потоке выполнять.
Хотя конечно используется пул потоков, но все-равно должно быть медленнее.

Здравствуйте, igor-booch, Вы писали:

IB>Медленней будет, Parallel.For каждую итерацию будет в отдельном потоке выполнять.
IB>Хотя конечно используется пул потоков, но все-равно должно быть медленнее.
Рекомендую проверить экспериметном, поскольку есть сильное подозрение, что выделенное неверно.

Здравствуйте, igor-booch, Вы писали:

S>>Те же самые у него механизмы, тот же самый Monitor.Enter, только не весь контейнер блокируется эксклюзивно, а отдельные Bucket-ы + эксклюзивный GrowTable.
IB>Да те же, чего-то мне показалось, что я там MemoryBarrier видел, наверное где-то в другом месте видел.
Может там он и есть, но блокировки обычные Monitor.Enter

S>>Кстати, именно эксклюзивным GrowTable можно объяснить увеличение времени работы на числе потоков > 2.
IB>Можно поподробнее? Вот метод, который выполняется в начале GetRowTable:
Да, выполняется.

IB>Почему они просто не написали, Monitor.Enter(this) для эксклюзивной блокировки?
Monitor.Enter(this) — моветон. Во всем остальном я не берусь отвечать, почему они вызывают именно тот метод. Может быть потому что используют специальную таблицу объектов для блокировки, а не this.
И метод Monitor.Enter(object, bool) получает точно такую же эксклюзивную блокировку, как и Monitor.Enter(object).

S>>И так как он использует те же самые Monitor.Enter для синхронизации, он по определению не сможет обогнать словарь без синхронизации на одном потоке. (если бы обогнал, то зачем бы нужен был Dictionary?).
IB>Обгонял бы на 8 потоках, было бы с него больше толку.
Напишите такой что бы обгонял, предложите свою реализацию команде дотнета. Возможно скажут спасибо.

S>Напишите такой что бы обгонял, предложите свою реализацию команде дотнета. Возможно скажут спасибо.
Здесь нужна будет более тонкая синхронизация (например с MemoryBarrier).
Даже если я напишу мне не поверят, что реализация надежная.
Мне кажется здесь нужно будет математически это будет доказывать.
А это уже сложная для меня задача.
А есть подобные реализации от сторонних производителей?

Здравствуйте, igor-booch, Вы писали:

S>>Напишите такой что бы обгонял, предложите свою реализацию команде дотнета. Возможно скажут спасибо.
IB>Здесь нужна будет более тонкая синхронизация (например с MemoryBarrier).
Lock free что ли? memory barrier сам по себе не есть средство синхронизации.
IB>Даже если я напишу мне не поверят, что реализация надежная.
IB>Мне кажется здесь нужно будет математически это будет доказывать.
IB>А это уже сложная для меня задача.
Сомневаюсь что есть какое-то доказательство для текущего кода из BCL.

IB>А есть подобные реализации от сторонних производителей?
Подобные чему? По поводу lock-free — не знаю, есть ли что-то стабильное, но вообще подобные ConcurrentDictionary должны быть.

S>Сомневаюсь что есть какое-то доказательство для текущего кода из BCL.
Я думаю нужно не сначала писать код, а потом доказывать его стабильность,
а наоборот, сначала, создать алгоритм, доказать его стабильность,
и уж потом реализовать его, возможно при этом понадобится расширение BCL

S>Подобные чему? По поводу lock-free — не знаю, есть ли что-то стабильное, но вообще подобные ConcurrentDictionary должны быть.
Не обязательно lock-free, главное чтобы обгонял на 4 или 8 потоках однопоточную реализацию
Я не встречал нигде

Здравствуйте, igor-booch, Вы писали:

IB>Почему они просто не написали, Monitor.Enter(this) для эксклюзивной блокировки?

Хотя бы потому, что lock(this) — зло. Так же как lock(typeof(this)) и любые публично доступные экземпляры.

Здравствуйте, igor-booch, Вы писали:

S>>Сомневаюсь что есть какое-то доказательство для текущего кода из BCL.
IB>Я думаю нужно не сначала писать код, а потом доказывать его стабильность,
IB>а наоборот, сначала, создать алгоритм, доказать его стабильность,
IB>и уж потом реализовать его, возможно при этом понадобится расширение BCL
Расширение BCL для своего алгоритма? Интересно. А что такого может понадобиться от BCL, чего нельзя написать самому?

S>>Подобные чему? По поводу lock-free — не знаю, есть ли что-то стабильное, но вообще подобные ConcurrentDictionary должны быть.
IB>Не обязательно lock-free, главное чтобы обгонял на 4 или 8 потоках однопоточную реализацию
На чтении стабильно обгоняет ConcurrentDictionary. Добавление — да, медленнее. Но оно и понятно. Попробуйте уменьшить GrowTable с помощью задания размера в конструкторе — и время приблизится к обычному словарю.
IB>Я не встречал нигде
А я не искал.

IB>>Почему они просто не написали, Monitor.Enter(this) для эксклюзивной блокировки?
P>Хотя бы потому, что lock(this) — зло. Так же как lock(typeof(this)) и любые публично доступные экземпляры.
Это все понятно, не об этом топик.
Можно конечно:

private object _syncObject = new object();

Monitor.Enter(_syncObject)

Это что меняет суть вопроса? Зачем метод AcquireLocks для эксклюзивной блокировки (если она действительно эксклюзивная, как утверждает samius), если эксклюзивную блокировку можно написать как Monitor.Enter(_syncObject)?