Производительность ConcurrentDictionary<> в одном потоке недоразумение?
Связанная краткая информация:
AFAIK, Параллельные классы стека, очереди и мешка реализованы внутри с помощью связанных списков.
И я знаю, что споров намного меньше, потому что каждый поток отвечает за свой собственный связанный список. В любом случае, мой вопрос о ConcurrentDictionary<,>
Но я тестировал этот код:(один поток)
Stopwatch sw = new Stopwatch();
sw.Start();
var d = new ConcurrentDictionary < int, int > ();
for(int i = 0; i < 1000000; i++) d[i] = 123;
for(int i = 1000000; i < 2000000; i++) d[i] = 123;
for(int i = 2000000; i < 3000000; i++) d[i] = 123;
Console.WriteLine("baseline = " + sw.Elapsed);
sw.Restart();
var d2 = new Dictionary < int, int > ();
for(int i = 0; i < 1000000; i++) lock (d2) d2[i] = 123;
for(int i = 1000000; i < 2000000; i++) lock (d2) d2[i] = 123;
for(int i = 2000000; i < 3000000; i++) lock (d2) d2[i] = 123;
Console.WriteLine("baseline = " + sw.Elapsed);
sw.Stop();
Результат: (проверено много раз, одинаковые значения (+/-)).
baseline = 00:00:01.2604656
baseline = 00:00:00.3229741
Вопрос:
Что делает ConcurrentDictionary<,> намного медленнее в однопоточной среде?
Мой первый инстинкт lock(){} всегда будет медленнее но, видимо, это не так.
9 ответов
Наиболее вероятная причина того, что ConcurrentDictionary просто имеет больше накладных расходов, чем Dictionary для той же операции. Это наглядно верно, если копаться в источниках
- Он использует блокировку для индексатора
- Использует изменчивые записи
- Он должен делать атомарные записи значений, которые не гарантированно будут атомарными в.Net
- У него есть дополнительные ветки в основной процедуре добавления (брать ли блокировку, делать атомарную запись)
Все эти затраты происходят независимо от количества потоков, в которых он используется. Эти расходы могут быть индивидуально небольшими, но не бесплатными и со временем увеличиваются.
Что ж, ConcurrentDictionary допускает возможность того, что он может быть использован несколькими потоками. Мне кажется совершенно разумным, что для этого требуется больше внутренней поддержки, чем то, что предполагает, что он может уйти, не беспокоясь о доступе из нескольких потоков. Я был бы очень удивлен, если бы все получилось наоборот - если бы более безопасная версия всегда была быстрее, почему бы вам использовать менее безопасную версию?
Я только что написал о моей безблокировочной поточно-безопасной реализации словаря для копирования при записи здесь:
http://www.singulink.com/CodeIndex/post/fastest-thread-safe-lock-free-dictionary
Это очень быстро для быстрых пакетов записей и поисков, как правило, на 100% стандартном Dictionary Скорость без блокировки. Если вы пишете время от времени и часто читаете, это самый быстрый вариант.
В настоящее время он только для добавления, так как я использовал его для кэширования, но если есть популярный спрос, я мог бы добавить к нему и методы удаления.
ConcurrentDictionary работает медленно, потому что снимает блокировки чтения / записи при каждой операции. Блокировки чтения / записи даже медленнее, чем обычные блокировки, но допускают несколько считывателей без блокировки.
Моя реализация обеспечивает максимальную производительность чтения, устраняя необходимость в каких-либо блокировках чтения при нормальных обстоятельствах, пока обновления словаря не производятся. Компромисс состоит в том, что словарь должен быть скопирован и заменен после применения обновлений (это делается в фоновом потоке), но если вы не пишете часто или пишете только один раз во время инициализации, то компромисс определенно стоит Это.
ConcurrentDictionary против словаря
В общем, используйте System.Collections.Concurrent.ConcurrentDictionary в любом сценарии, в котором вы добавляете и обновляете ключи или значения одновременно из нескольких потоков. В сценариях, которые включают частые обновления и сравнительно мало операций чтения, ConcurrentDictionary обычно предлагает скромные преимущества. В сценариях, которые включают много операций чтения и много обновлений, ConcurrentDictionary обычно значительно быстрее на компьютерах с любым количеством ядер.
В сценариях с частыми обновлениями вы можете увеличить степень параллелизма в ConcurrentDictionary и затем измерить, увеличивается ли производительность на компьютерах с большим количеством ядер. Если вы изменяете уровень параллелизма, по возможности избегайте глобальных операций.
Если вы только читаете ключ или значения, словарь работает быстрее, потому что синхронизация не требуется, если словарь не изменяется никакими потоками.
Ссылка: https://msdn.microsoft.com/en-us/library/dd997373%28v=vs.110%29.aspx
ConcurrentDictionary<> создает внутренний набор блокирующих объектов при создании (это определяется concurrencyLevelСреди прочих факторов) - этот набор блокирующих объектов используется для управления доступом к внутренним структурам ковша в серии мелкозернистых замков.
В однопотоковом сценарии не было бы необходимости в блокировках, поэтому дополнительные затраты на получение и разблокировку этих блокировок, вероятно, являются источником различий, которые вы видите.
Нет смысла использовать ConcurrentDictionary в одном потоке или синхронизировать доступ, если все выполняется в одном потоке. Конечно, словарь будет лучше ConcrurrentDictionary.
Многое зависит от схемы использования и количества потоков. Вот тест, который показывает, что ConcurrentDictionary превосходит словарь и блокировку с увеличением числа потоков.
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
namespace ConsoleApp
{
class Program
{
static void Main(string[] args)
{
Run(1, 100000, 10);
Run(10, 100000, 10);
Run(100, 100000, 10);
Run(1000, 100000, 10);
Console.ReadKey();
}
static void Run(int threads, int count, int cycles)
{
Console.WriteLine("");
Console.WriteLine($"Threads: {threads}, items: {count}, cycles:{cycles}");
var semaphore = new SemaphoreSlim(0, threads);
var concurrentDictionary = new ConcurrentDictionary<int, string>();
for (int i = 0; i < threads; i++)
{
Thread t = new Thread(() => Run(concurrentDictionary, count, cycles, semaphore));
t.Start();
}
Thread.Sleep(1000);
var w = Stopwatch.StartNew();
semaphore.Release(threads);
for (int i = 0; i < threads; i++)
semaphore.Wait();
Console.WriteLine($"ConcurrentDictionary: {w.Elapsed}");
var dictionary = new Dictionary<int, string>();
for (int i = 0; i < threads; i++)
{
Thread t = new Thread(() => Run(dictionary, count, cycles, semaphore));
t.Start();
}
Thread.Sleep(1000);
w.Restart();
semaphore.Release(threads);
for (int i = 0; i < threads; i++)
semaphore.Wait();
Console.WriteLine($"Dictionary: {w.Elapsed}");
}
static void Run(ConcurrentDictionary<int, string> dic, int elements, int cycles, SemaphoreSlim semaphore)
{
semaphore.Wait();
try
{
for (int i = 0; i < cycles; i++)
for (int j = 0; j < elements; j++)
{
var x = dic.GetOrAdd(i, x => x.ToString());
}
}
finally
{
semaphore.Release();
}
}
static void Run(Dictionary<int, string> dic, int elements, int cycles, SemaphoreSlim semaphore)
{
semaphore.Wait();
try
{
for (int i = 0; i < cycles; i++)
for (int j = 0; j < elements; j++)
lock (dic)
{
if (!dic.TryGetValue(i, out string value))
dic[i] = i.ToString();
}
}
finally
{
semaphore.Release();
}
}
}
}
Потоков: 1, элементов: 100000, циклов:10 ConcurrentDictionary: 00:00:00.0000499 Dictionary: 00:00:00.0000137
Темы: 10, элементы: 100000, циклы: 10 Параллельный словарь: 00:00:00.0497413 Словарь: 00:00:00.2638265
Потоков: 100, элементов: 100000, циклов:10 ConcurrentDictionary: 00:00:00.2408781 Словарь: 00:00:02.2257736
Потоки: 1000, элементы: 100000, циклы:10 ConcurrentDictionary: 00:00:01.8196668 Словарь: 00:00:25.5717232
Что делает
ConcurrentDictionary<,>намного медленнее в однопоточной среде?
Накладные расходы на оборудование, необходимые для того, чтобы сделать его намного быстрее в многопоточных средах.
Мой первый инстинкт в том, что
lock(){}всегда будет медленнее. но, видимо, это не так.
А lockочень дешево, когда неоспоримо. Вы можетеlockмиллион раз в секунду, и ваш процессор даже не заметит, если вы делаете это из одного потока. Что убивает производительность в многопоточных программах, так это борьба за блокировки. Когда несколько потоков яростно конкурируют за одно и то жеlock, почти всем им приходится ждать, пока тот, кто держит замок, освободит его. Вот гдеConcurrentDictionaryс его реализацией гранулярной блокировки. И чем больше у вас параллелизма (чем больше процессоров / ядер), тем больше он сияет.
В .Net 4 ConcurrentDictionary использовал очень плохое управление блокировками и разрешение конфликтов, что делало его чрезвычайно медленным. Словарь с настраиваемой блокировкой и/или даже с использованием TestAndSet для COW всего словаря был быстрее.
Ваш тест неверен: вы должны остановить секундомер раньше!
Stopwatch sw = new Stopwatch();
sw.Start();
var d = new ConcurrentDictionary<int, int>();
for (int i = 0; i < 1000000; i++) d[i] = 123;
for (int i = 1000000; i < 2000000; i++) d[i] = 123;
for (int i = 2000000; i < 3000000; i++) d[i] = 123;
sw.Stop();
Console.WriteLine("baseline = " + sw.Elapsed);
sw.Start();
var d2 = new Dictionary<int, int>();
for (int i = 0; i < 1000000; i++) lock (d2) d2[i] = 123;
for (int i = 1000000; i < 2000000; i++) lock (d2) d2[i] = 123;
for (int i = 2000000; i < 3000000; i++) lock (d2) d2[i] = 123;
sw.Stop();
Console.WriteLine("baseline = " + sw.Elapsed);
sw.Stop();
--Выход: