Под капотом у Dictionary и ConcurrentDictionary

Некоторое время назад, я решил, что хочу знать больше подробностей о работе многопоточности в .NET и что я уделял этому незаслуженно мало внимания в прошлом. Информации на эту тему великое множество (отправной точкой я для себя выбрал этот раздел книги «C# in a nutshell»), но, как оказалось, только малая часть ресурсов пытаются объяснить что-то в деталях.

Каждый мастер должен знать свои инструменты, а что может использоваться чаще коллекций? Поэтому я решил сделать небольшой обзор многопоточных коллекций и начать с ConcurrentDictionary (беглый обзор уже встречался здесь, но его там совсем мало). Вообще, я несколько удивился, что такой статьи для .NET еще нет (зато хватает по Java).

Итак, поехали.

Если вы уже знакомы с самим Dictionary, то можете пропустить следующий раздел.

Что такое Dictionary<TKey, TValue>?


Dictionary представляет собой реализацию стандартной Hashtable.
Здесь интересны следующие функции:

Инициализация

Инициализация происходит либо при создании (если передана начальный размер коллекции), либо при добавлении первого элемента, причем в качестве размера будет выбрано ближайшее простое число (3). При этом создаются 2 внутренние коллекции — int[] buckets и Entry[] entries. Первая будет содержать индексы элементов во второй коллекции, а она, в свою очередь, — сами элементы в таком виде:

private struct Entry
{
    public int hashCode;
    public int next;
    public TKey key;
    public TValue value;
}

Добавление элементов

При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции:

int bucketNum = (hashcode & 0x7fffffff) % capacity;

Выглядеть это будет примерно так:

Затем проверяется нет ли уже такого ключа в коллекции, если есть — то операция Add выбросит исключение, а присваивание по индексу просто заменит элемент на новый. Если достигнут максимальный размер словаря, то происходит расширение (выбирается новый размер ближайшим простым числом).
Сложность оперции соответственно — O(n).

Если происходит коллизия (то есть в корзине с индексов bucketNum уже есть элемент), то новый элемент добавляется в коллекцию, его индекс сохраняется в корзине, а индекс старого элемента — в его поле next.

Таким образом получаем однонаправленный связный список. Данный механизм разрешения коллизий называется chaining. Если при добавлении элемента число коллизий велико (больше 100 в текущей версии), то при расширении коллекции происходит операция перехэширования, перед выполнением которой случайным образом выбирается новый генератор хэшкодов.
Сложность добавления O(1) или O(n) в случае коллизии.

Удаление элементов

При удалении элементов мы затираем его содержимое значениями по умолчанию, меняем указатели next других элементов при неоходимости и сохраняем индекс этого элемента во внутреннее поле freeList, а старое значение — в поле next. Таким образом, при добавлении нового элемента мы можем повторно использовать такие свободные ячейки:


Сложность снова O(1) или O(n) в случае коллизии.

Другое

Так же стоит отметить 2 момента:
1) При очистке словаря, его внутренний размер не изменяется. То есть, потенциально, вы просто тратите место.
2) GetEnumerator просто возвращает итератор по коллекции entires (сложность O(1)). Если вы только добавляли элементы — они вернутся в том же порядке. Однако если вы удаляли элементы и добавляли новые — порядок соответственно изменится, поэтому на него полагаться не стоит (тем более, что в будущих версиях фреймворка это может измениться).

Так и что же с ConcurrentDictionary?


Казалось бы, есть 2 решения в лоб для обеспечения потокобезопасности — обернуть все обращения к словарю в блокировки или обернуть все его методы в них же. Однако, по понятным причинам, такое решение будет медленным — задержки, добавляемые lock, да и ограничение на 1 поток, который мог бы работать с коллекцией не добавляют быстродействия.

В Microsoft пошли более оптимальным путем и Dictionary притерпел некоторые изменения. Так, благодаря внутренней структуре словаря и его корзин, блокировка осуществляется по ним, с помощью метода

private void GetBucketAndLockNo(int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount)
{
    bucketNo = (hashcode & 0x7fffffff) % bucketCount;
    lockNo = bucketNo % lockCount;
}

В то же время обычный словарь не смог бы работать с этой схемой, потому что все корзины используют один и тот же массив entries, поэтому корзины стали представлять собой обычный single linked list: volatile Entry[] m_buckets (поле объявлено как volitale, чтобы обеспечить неблокирующую синхронизацию в ситуации когда один поток пытается выполнить какую-то операцию, а другой в этот момент изменяет размер коллекции).

В итоге корзины стали выглядеть вот так:


lockNo — это индекс в новом массиве, который содержит объекты синхронизации — object[] m_locks. Его использование позволяет разным потокам изменять разные корзины в одно и то же время. Размер этой коллекции зависит от параметра ConcurrencyLevel который можно задать через конструктор. Он определяет примерное число потоков которые будут одновременное работать с коллекцией (по умолчанию это число_процессоров * 4). Чем выше это значение, тем проще будут происходить операции записи, но так же станут гораздо дороже операции, которые требуют полной блокировки всей коллекции (Resize, ToArray, Count, IsEmpty, Keys, Values, CopyTo, Clear). Также этот параметр определяет сколько элементов коллекции приходится на один lock (как отношение числа корзин к размеру этой коллекции) и когда элементов становится больше, чем надо — коллекция расширяется, потому что в противном случае поиск элемента требует не O(1), а уже O(n) за счет обхода связных списков. Чтобы немного снизить число первоначальных расширений коллекции, начальный размер словаря уже не 3, а 31.

Все операции приобрели вид:

void ChangeBacket(TKey key)
{
    while (true)
    {
        Node[] buckets = m_buckets;
        int bucketNo, lockNo;
        GetBucketAndLockNo(m_comparer.GetHashCode(key), out bucketNo, out lockNo, buckets.Length);
        lock (m_locks[lockNo])
        {
            if (buckets != m_buckets)
            {
                // Race condition. Пока мы ждали блокировки, другой поток расширил коллекцию.
                continue;
            }
            Node node = m_buckets[bucketNo];
            // Вносим изменения в нод.
        }
    }
}

При добавлении нового элемента приходится обойти весь связанный список просто чтобы определить есть ли уже такой ключ и если нет — добавить. Аналогично при удалении — сперва надо найти узел который удалить.

Впрочем, для некоторых операций блокировка не нужна в принципе — это TryGetValue, GetEnumerator, ContainsKey и индексация. Почему? Потому что все изменения размера корзин видны за счет того что поле volatile, любые добавления или изменения элементов происходят путем создания нового элемента и замены им старого, а удаления происходят просто заменой указателя на следующий узел.

Другое

1) В отличие от обычного Dictionary, вызов метода Clear, сбрасывает размер коллекции на значение по умолчанию.
2) GetEnumerator — может возвращать старые значения в случае, если изменения были сделаны другим потоком после вызова метода и того как итератор прошел этот элемент. В упомянутой в начале статье было отмечено, что
лучше использовать dictionary.Select(x => x.Value).ToArray(), чем dictionary.Values.ToArray()
И это не совсем верно — вместо «лучше» тут должно быть «быстрее» — за счет отсутствия блокировок, но надо принять во внимание, что данные подходы могут вернуть разные данные.

Спасибо за внимание.

В статье использованы:
1. The .NET Dictionary
2. Inside the Concurrent Collections: ConcurrentDictionary
3. Concurrent Collections
4. .NET Reflector

Комментарии 31

    +8
    Благодарю за статью. Планируется ли обзор других многопоточных коллекций из .NET 4?
      +7
      Если эта тема кому-то интересно — конечно.
        +4
        Безусловно интересна.

        Пишите, подобный материал всегда найдет своего читателя. Тем более, полноцееное описание каких-либо классов среды CLR найти очень трудно.
          0
          да
            0
            Интересна. Пишите еще :)
            +2
            Так вроде когда все это выпускалось, уже была статья или даже серия про многопоточные коллекции. Советую поискать.
          +1
          Вот как раз вчера засел за поиск потообезопасной очереди объектов и нашёл ConcurrentQueue. Насколько я понимаю — это одного поля ягоды и хотелось бы побольше узнать об очередях и о подводных камнях при работе с ними.
            0
            После прочтения промелькнула мысль: «Чувак, я нихрена не понял, но твои слова запали мне в душу».

            А по делу, статья, конечно, достойная в плане расширения знаний.
            Правда, у меня возникло недопонимание таких моментов…

            «Затем проверяется нет ли уже такого в коллекции», такого индекса или хеша? Вроде по тексту дальше, подразумевается индекс. Но все-равно запутанно.

            «Если происходит коллизия (то есть элемент с таким же хэшкодом уже есть в коллекции)». А как она может возникнуть? У наc же «операция Add выбросит исключение»?
              +1
              Ответ на 1 вопрос — ключа и его хэша на самом деле. Я не уверен зачем так сделано, учитывая, что хэш генерится по ключу, но проверка там выглядит так:

              if ((this.entries[i].hashCode == hashcode) && this.comparer.Equals(this.entries[i].key, key))
              

              По 2 вопросу — отредактировал пост. Вы правы, там не хэш, там индекс корзины который получился по формуле:

              int bucketNum = (hashcode & 0x7fffffff) % capacity;
              

              Тут, как вы понимаете результат может быть одинаковый для разных хэшей.
                +4
                Кстати, hashcode & 0x7fffffff — интересный приём. 0x7fffffff — это значение int.MaxValue.
                Делается эта операция для того, чтобы транслировать отрицательную часть диапазона Int32 в положительную. Логически это то же самое, что:

                hashcode >= 0 ? hashcode : int.MaxValue + hashcode + 1
                
                  +1
                  Ответ на 1 вопрос — ключа и его хэша на самом деле. Я не уверен зачем так сделано, учитывая, что хэш генерится по ключу, но проверка там выглядит так
                  if ((this.entries[i].hashCode == hashcode) && this.comparer.Equals(this.entries[i].key, key))

                  Если я правильно понял и речь идёт о добавлении элемента, то смысл самый прямой. Хеши ключей могу совпадать при разных значениях ключей. GetHash() гарантирует только то, что одинаковые объекты вернут одинаковые хеши, но не гарантирует что разные объекты будут иметь разный хешь.
                +2
                Не пишу на C#, но с удовольствием прочитал статью.
                Спасибо!
                  0
                  На сколько я помню, стандартная реализация Dictionary перестраивает списки в деревья, если на одном хэше висит много элементов, а не делает перехэширование.
                    +1
                    Тут я могу предложить вам поверить мне на слово, либо взять в руки рефлектор и убедиться самому.
                      0
                      Взял в руки и убедился. Перехеширование действительно происходит, но только для компараторов, которые это поддерживают. В их число входят только стандартные компараторы строк, а сам интерфейс для перехеширования — internal.
                        +1
                        Ещё вспомнилась DoS атака на ASP.NET, основанная на вставке в Dictionary специально подобранных строк из запроса с одинаковым хешем. Механизм перехеширования должен давать от неё защиту, даже когда случайные хеши глобально выключены (по умолчанию).
                      +1
                      Деревья для защиты от коллизий используются в джаве, IIRC.
                      +2
                      При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции (именно для этого размер выбирается простым числом, чтобы обеспечить более равномерное распределение и уменьшить число возможных коллизий):
                      Я, наверное, что-то недопонял. Можете пояснить, как деление по модулю простого числа обеспечивает «более равномерное» распределение, чем деление по модулю обычного числа (например, на единицу большего, чем простое)?
                        +2
                        При вычислении хэша необходимо, чтоб распределение было как можно более равномерным, и чтоб хеширующая функция учитывала максимальное кол-во информации из хешируемого значения. Допустим делитель будет не простым числом, а степенью двойки 2^p, тогда остатком от деления на такое число любого другого (L) будет p нижних битов L, что само по себе нехорошо, потому что верхние биты не принимают «участие» в результирующем хеше.
                        По этому поводу есть глава в «Introduction To Algorithms» Кормена.
                          +1
                          А, кажется, я начинаю понимать. Но думаю, что дело не в том, что какие-то биты «не работают». Ведь биты — всего лишь одно из бесонечности возможных представлений числа. Если представить то же самое число в троичной системе, то «не будут работать» биты при делении на 3. Если представить число в системе по основанию 59, то не будут работать биты при делении на 59.

                          Думаю, идея в оптимизации перехэширования. Ведь алгоритмы хеширования, хотя и могут быть основаны на разных принципах, наверное могут иногда вести себя схожим образом при, например, делении их хэщей на степень двойки, или тройки, или ещё какого-то числа. В общем, мне кажется, что простые числа нужны, чтобы свести к минимуму необходимость повторного перехеширования. Например, по какому-то конкретному хэшу накопилось 100 значений, а после смены хэш-алгоритма снова наблюдается та же ситуация из-за того, что в обоих алгоритмах «не работают биты» при взятии остатка деления на какое-то число. Так вот, чем больше размер массива buckets, тем меньше вероятность, что мы с этим стокнёмся — ведь простые числа растут, и всё меньше остаётся чисел, которые на них без остатка делятся.
                          0
                          Давайте я приведу пример. У вас есть словарик на 10 элементов (capacity = 10). При вычислении индекса корзины, в которую попадет элемент, мы берем остаток от деления на 10. Логично, что элемент, в зависимости от его хэша, попадет в 0..9 корзину. А теперь представьте что у хэша и размера словаря есть общие делители — например 2 (или 5). Тогда, элемент уже может попасть только в 0..4 (либо 0..1). А это значит что бОльшая часть корзин останется неиспользованными. А теперь возьмите простые числа — они делятся только на 1 и самих себя. Т.е. при емкости 11, элементы будут случайным образом всегда занимать 0..10 корзины.

                          Упрощенно, процент использования всех корзин можно представить как (GCD — наибольший общий делитель)
                          x% = capacity / GCD (capacity, hashcode)
                          
                            +1
                            capacity = 10
                            hashcode = 18
                            GCD = 2
                            bucketNumber = 18 % 10 = 8
                            

                            Не сходится это с тем, что вы написали.
                            Вообще, если хэш равномерно распределён по всему диапазону своих возможных значений, то уже на что его не дели, всё равно остаток будет распределён равномерно в диапазоне значений [0; capacity). Общие делители на это абсолютно никак не влияют — влияет только распределение хэшей.
                              0
                              Да, действительно, не подходит такой вариант. Тогда так — предположим, что у нас хорошая хэш функция, которая возвращает не связанные хэшкоды — тут разницы простое число или нет скорее всего не будет. А теперь представим, что хэшкоды связаны, например х, 2х, 3х, 4х и т.д. Например если ваши хэши — 2,4,6,8,10,12,14,16,18,20, то и корзины в которые они попадут будут одними и теми же.
                              2 % 10 = 12 % 10 = 2 и т.д.
                              


                              И простое чило, выбранное в качестве делителя здесь просто помогает компенсировать плохую работу хэш функции.
                                0
                                Возьмём простое число P. На него без остатка делится N чисел из диапазона значений Int32.
                                Возьмём число P+1. На него без остатка будут делится N' чисел из того же диапазона, причём N' <= N.
                                Компенсировать плохую работу хэш-функции можно не тем фактом, что число простое, а тем фактом, что число большое. Чем больше число, тем меньше других чисел на него нацело делится. В том контексте, о котором вы говорите, абсолютно не имеет значения, простое ли значение capacity, или нет.
                                  0
                                  Ну, тогда у меня больше нет идей из каких соображений в хэштаблицах предпочтение отдается простым числам.
                          –3
                          А что удивительного? Все ждут пока кнонибудь напишет статью по канкаренси, я например, ждал точно. Еще бы чуть чуть и написал бы кто нибудь другой, может быть и я, это как игра в слабака, кто первый струсит. За статью спасибо!
                            0
                            Такс, всё круто, но остались белые ( или черные пятна ).
                            Dictionary умеет ведь искать элементы, так? А также выбрасывать исключения, если такой элемент уже есть в коллекции?
                            Так вот что будет если:
                            1) добавляем элемент, скажем, 25 (тип int, поэтому его значение и хешкод совпадают). Количество корзин было 23. значит элемент добавился в корзину № 25 % 23 = 2, в корзину 2 значит. Так?
                            2) Добавилось в коллекцию кучу других элементов так, что словарь увеличился до 29. Так? Значит количество корзин стало 29. (просто создался массив из 29 элементов и 23 элемента скопировалось в 29), так?
                            3) В коллекцию приходит снова элемент 25, только теперь он распределяется не в корзину 2, а в корзину 25.
                            25 % 29 = 25 Правильно?

                            При этом коллекция не выбрасывает исключение, в коллекции оказывается два одинаковых значения, только расположены они в разных местах.

                            Если после расширения словаря, попробовать найти какой либо из раннее добавленных элементов, то он найден не будет.

                            Что, получается, что при расширении словаря меняется не только структура с корзинами, но и вообще вся структура? это же очень дорого, все равно что взять и передобавить все существующие элементы в коллекцию только с новым размером словаря. Или как?
                              0
                              2) Добавилось в коллекцию кучу других элементов так, что словарь увеличился до 29. Так? Значит количество корзин стало 29. (просто создался массив из 29 элементов и 23 элемента скопировалось в 29), так?

                              Не так. При перехэшировании (только при нем увеличивается размер корзины) хэш каждого элемента вычисляется заново. Сложность этой операции указана в статье — O(n). Происходить перехэширование будет не часто, т.к. размер корзины выбирается простым числом.
                              0
                              Печально. Я думал Concurrent* коллекции — неблокирующие.
                                0
                                Обновите ссылку пожалуйста, она перестала работать

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

                                Самое читаемое