ConcurrentDictionary: правильная небольшая начальная емкость - PullRequest
Новая
       34

ConcurrentDictionary: правильная небольшая начальная емкость

1 голос
/ 31 января 2020

Я все время сталкиваюсь с отсутствием рекомендаций по выбору правильных начальных мощностей для ConcurrentDictionary<TKey, TValue>.

Мой общий случай использования - это ситуации, когда вы действительно хотите, чтобы сделал что-то вроде следующего, но не может: 

public static class StaticCache<T>
{
    public static readonly Action CompiledExpression = ...;
}

Этот обобщенный c подход избегает поиска в словаре, но может использоваться, только если мы всегда знаем требуемый тип во время компиляции. Если у нас есть только Type, известный во время выполнения, мы больше не можем использовать этот подход. Следующим претендентом является ConcurrentDictionary<TKey, TValue>.

Документация гласит:

Емкость по умолчанию (DEFAULT_CAPACITY), которая представляет начальное количество сегментов, компромисс между размером очень маленького словаря и количеством размеров при создании большого словаря. Кроме того, емкость не должна делиться на небольшое простое число. Емкость по умолчанию - 31.

Количество ожидаемых элементов, как правило, относительно мало. Иногда всего 3 или 5, иногда, возможно, 15. Таким образом:

  • Количество вставок за время жизни приложения будет чрезвычайно минимальным, гарантируя [запись] уровень параллелизма 1, таким образом, оптимизирующий для компактности и для операций чтения.
  • Желательно иметь минимально возможный объем памяти для оптимизации поведения кэша.

Так как начальная емкость по умолчанию значение 31, мы можем потенциально уменьшить наше влияние на кеш (а также повысить вероятность того, что наш словарь останется в кеше), используя меньшую начальную емкость.

Это поднимает следующие вопросы:

  1. Что на самом деле означает емкость?

    • (A) Что словарь не должен расти, чтобы вместить до такого количества элементов ?
    • (B) Фиксированный процент от A, в зависимости от максимальной «полноты» словаря, например, 75%?
    • (C) Приближение A или B, в зависимости от h а как же их содержит фактическое содержание кодов sh?

  2. Что составляет и не составляет "маленькое простое число"? Видимо, 31 нет. 11? 17? Неужели 23?

  3. Если нам действительно понадобится емкость рядом с небольшим праймом, какую емкость мы можем выбрать вместо этого? Мы просто выбираем ближайшее не простое число, или простые числа лучше для мощностей, и мы должны вместо этого действительно выбрать большее простое число?

1 Ответ

2 голосов
/ 31 января 2020

В справочном источнике для ConcurrentDictionary<TKey, TValue> вы можете увидеть: 

Node[] buckets = new Node[capacity];

Таким образом, емкость - это эффективный размер таблицы ha sh. Никакая "полнота" не рассматривается. Единственная предварительная обработка этого числа: 

if (capacity < concurrencyLevel)
{
    capacity = concurrencyLevel;
}

, где concurrencyLevel либо определяется вами через параметр конструктора, либо является уровнем параллелизма по умолчанию, определенным как PlatformHelper.ProcessorCount.

Емкость трактуется по-разному в Dictionary<TKey,TValue>. Здесь он инициализируется с помощью 

private void Initialize(int capacity) {
    int size = HashHelpers.GetPrime(capacity);
    buckets = new int[size];
    ...
}

, а HashHelpers.GetPrime получает наименьшее простое число, которое больше или равно указанной емкости. Простые числа до 7199369 взяты из предварительно рассчитанного массива. Лагерные рассчитываются "трудным путем". Интересно отметить, что наименьшее из рассмотренных простых чисел - 3.

К сожалению, HashHelpers является внутренним классом.

Если я правильно понимаю, обе реализации изменяют размер ha * 1042. * таблица, основанная на количестве столкновений и не основанная на заданном c коэффициент заполнения ("заполненность").

Если вы хотите

  • оптимизировать скорость: возьмите начальная емкость, которая на 30% больше ожидаемого максимального размера словаря. Это позволяет избежать изменения размера.
  • оптимизировать объем памяти: взять простое число, которое примерно на 30% больше ожидаемого размера минимум .
  • баланс между скоростью и объемом памяти: Возьмите число между двумя сверху. Но в любом случае взять прайм.
...