» » » Интересные сюрпризы ConcurrentDictionary (+разбор задачи с DotNext 2017 Moscow)

 

Интересные сюрпризы ConcurrentDictionary (+разбор задачи с DotNext 2017 Moscow)

Автор: admin от 8-02-2018, 09:35, посмотрело: 91

Привет всем, кто пишет код для .NET, особенно многопоточный. Редко встретишь потокобезопасный код без потокобезопасных коллекций, а значит, нужно уметь ими пользоваться. Я расскажу о самой популярной из них — ConcurrentDictionary. В ней спрятано на удивление много интересных сюрпризов: как приятных, так и не очень.



Сначала разберём устройство ConcurrentDictionary и вычислительную сложность операций с ним, а затем поговорим об удобных трюках и подводных камнях, связанных с memory traffic и сборкой мусора.



Интересные сюрпризы ConcurrentDictionary (+разбор задачи с DotNext 2017 Moscow)striped locking. Имеется небольшой массив обычных локов, и каждый из них отвечает за целый диапазон bucket-ов (отсюда и stripe в названии). Для того, чтобы записать что-то в произвольный bucket, необходимо захватить соответствующий ему лок. Обычно локов намного меньше, чем bucket-ов.



Интересные сюрпризы ConcurrentDictionary (+разбор задачи с DotNext 2017 Moscow)

А вот как эти понятия соотносятся с параметрами конструктора ConcurrentDictionary(int concurrencyLevel, int capacity):




  • capacity — количество bucket-ов. По умолчанию — 31.

  • concurrencyLevel — количество локов. По умолчанию — 4 x количество ядер.



Реализация старается поддерживать размер bucket-ов небольшим, увеличивая по мере необходимости их количество. При расширении происходит следующее:




  • Емкость увеличивается примерно вдвое. Примерно, потому что величина выбирается так, чтобы она не делилась на 2, 3, 5 и 7 (емкость полезно делать простым или плохо факторизуемым числом).

  • Количество локов увеличивается вдвое, если concurrencyLevel не был задан явно. В противном случае оно остается прежним.



Сложность операций



Сводная табличка для словаря с N элементов и K локов:



Интересные сюрпризы ConcurrentDictionary (+разбор задачи с DotNext 2017 Moscow)

Остальные операции являются производными от этих:




  • GetOrAdd = TryGetValue + TryAdd

  • AddOrUpdate = TryGetValue + TryAdd + TryUpdate

  • Indexer(get) = TryGetValue

  • Indexer(set) = TryAdd с перезаписью



Плохие новости



Свойства Count и IsEmpty коварно захватывают все локи в словаре. Лучше воздержаться от частого вызова этих свойств из нескольких потоков.



Свойства Keys и Values еще более коварны: они не только берут все локи, но и целиком копируют в отдельный List все ключи и значения. В отличие от традиционного Dictionary, одноимённые свойства которого возвращают «тонкие» обертки, здесь нужно быть готовым к крупным аллокациям памяти.



Такая вопиющая неэффективность вызвана желанием обеспечить семантику снепшота: возвращать некоторое консистентное состояние, существовавшее в определенный момент времени.



Хорошие новости



Не всё так плохо. Первая: самое обычное перечисление (работающее через GetEnumerator) является неблокирующим и работает без лишнего копирования данных. За это приходится платить отсутствием семантики снепшота: по мере перечисления на результате могут отражаться производимые параллельно операции записи.



Вторая хорошая новость: чаще всего такое поведение является либо допустимым, либо вовсе желаемым, и этим можно пользоваться. Например, эффективно перечислять ключи или значения:



var keys = dictionary.Select(pair => pair.Key);
var values = dictionary.Select(pair => pair.Value);


Tips and tricks



В отличие от обычного Dictionary, можно производить вставку в ConcurrentDictionary или удаление из него прямо во время перечисления! Это, например, позволяет удобно вычищать устаревшие элементы из словарика-кэша с временем жизни:



foreach (var pair in cache)
{
    if (IsStale(pair.Value))
    {
        cache.TryRemove(pair.Key, out _);
    }
}


Удалять элементы можно не только по ключу, но и по точному совпадению key + value, причем атомарно! Это недокументированная возможность, скрытая за explicit-реализацией интерфейса ICollection. Она позволяет безопасно очищать такой кэш даже в условиях гонки с обновлением значения:



var collection = cache as ICollection<KeyValuePair<MyKey, MyValue

foreach (var pair in cache)
{
    if (IsStale(pair.Value))
    {
        // Remove() will return false in case of race with value update
        var removed = collection.Remove(pair); 
    }
}


Это и так все знают, но напомню: в условиях конкурентного доступа GetOrAdd может вызвать делегат-фабрику для одного ключа сильно больше одного раза. Если так делать нельзя или дорого, достаточно обернуть значение в Lazy:



var dictionary = new ConcurrentDictionary<MyKey, Lazy<MyValue();

var lazyMode = LazyThreadSafetyMode.ExecutionAndPublication;

var value = dictionary
    .GetOrAdd(key, _ => new Lazy<MyValue>(() => new MyValue(), lazyMode))
    .Value;


GC overhead



При использовании больших словарей (начиная от десятков тысяч элементов), нужно помнить, что, в отличие от обычного Dictionary, в ConcurrentDictionary на каждый элемент создается дополнительный объект на куче. Резидентный ConcurrentDictionary с десятками миллионов элементов легко может обеспечить секундные паузы при сборке мусора второго поколения.



// Only a handful of objects in final dictionary.
// Value types dominate in its internals.
Dictionary<int, int> ordinary = Enumerable
    .Range(0, 10 * 1000 * 1000)
    .ToDictionary(i => i, i => i);

// ~10kk objects in concurrent version (due to linked lists).
var concurrent = new ConcurrentDictionary<int, int>(ordinary);


При перезаписи существующего значения также может выделяться новый объект, порождая memory traffic. Это происходит в случае, если стандарт языка не гарантирует атомарность записи типа значения. Например:




  • Если значение — int или reference type, его запись атомарна. Тогда перезапись производится in-place, без выделения нового объекта.

  • Если значение — Guid или другой «широкий» value type, его запись не является атомарной. Здесь реализация вынуждена создавать новый внутренний объект.



Задача на DotNext 2017 Moscow



Я впервые опубликовал эту статью осенью 2017 года во внутренней соцсети. А коллеги, которые были в прошлом ноябре на конференции DotNext в Москве, сделали по мотивам статьи задачку, которую можно было решить на стенде Контура.



Там был фрагмент кода:



public void TestIteration(ConcurrentDictionary<int, int> dictionary)
{
    Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, (i) =>
    {
        foreach (var keyValuePair in dictionary)
        {
            dictionary.AddOrUpdate(keyValuePair.Key, (key) => i, (key, value) => i);
        }
    });
}

public void TestKeysProperty(ConcurrentDictionary<int, int> dictionary)
{
    Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, (i) =>
    {
        foreach (var key in dictionary.Keys)
        {
            dictionary.AddOrUpdate(key, (k) => i, (k, value) => i);
        }
    });
}


И три вопроса — нужно было сравнить эффективность методов TestIteration и TestKeysProperty по количеству операций, по памяти и по времени выполнения. Если вы внимательно читали статью, то должно быть понятно, что во всех трёх случаях TestIteration эффективнее.



Выводы



Инструменты параллельного программирования бывают полны неочевидных тонкостей, когда речь заходит о производительности: при неосторожном использовании ConcurrentDictionary, например, можно столкнуться с глобальными блокировками и линейной стоимостью в памяти. Надеюсь, эта шпаргалка поможет не наступить на грабли при написании очередного кэша или индекса в своем приложении.



Всем добра и эффективного кода!



Источник: Хабрахабр

Категория: Операционные системы » Linux

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *