FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 1. Значимые типы.

С релизом .NET 8 в арсенале C# разработчиков появился новый тип коллекций – FrozenDictionary. В серии статей рассмотрим, что представляет собой этот словарь и насколько он быстрее.

FrozenDictionary<TKey, TValue> – это абстрактный класс. У этого класса есть множество реализаций, зависящих от типа ключа, размера коллекции, компаратора. Создаются они при помощи extension-метода ToFrozenDictionary. Стратегия выбора подходящей реализации реализована в статическом классе FrozenDictionary, а именно в методе CreateFromDictionary.

В этой части рассмотрим реализации с ключом значимого типа и с компаратором по умолчанию. Для таких словарей предусмотрены 4 реализации FrozenDictionary:

1. Int32FrozenDictionary.
2. ValueTypeDefaultComparerFrozenDictionary.
3. SmallValueTypeComparableFrozenDictionary.
4. SmallValueTypeDefaultComparerFrozenDictionary.

Int32FrozenDictionary

Для словарей, с количеством элементов больше 10 и ключом типа Int32 используется класс Int32FrozenDictionary. Эта, как и большинство других реализаций FrozenDictionary, основаны на структуре FrozenHashTable. Это основа «замороженных» словарей. Подробнее о ней я расскажу в последней статье о FrozenDictionary. Пока же достаточно знать, что эта структура содержит в себе множество оптимизаций, которые позволяют быстро производить чтение.

Особенность Int32FrozenDictionary в том, что когда тип ключа – целое число, то его хэш равен его значению и коллизии в таком словаре не возможны в принципе. Нельзя, например, добавить 2 элемента с ключом 123 – будет выброшено исключение. Значит при чтении можно пропустить расчёт хэша и использовать значение ключа напрямую. А при создании словаря, например, пропустить удаление дублирующихся хэшей.

Благодаря этому, чтение из Int32FrozenDictionary быстрее на 36% – 42% (рис. 1).

ValueTypeDefaultComparerFrozenDictionary

Для словарей, с количеством элементов больше 10 и ключом любого другого значимого типа, кроме Int32 используется ValueTypeDefaultComparerFrozenDictionary. В этом случае коллизии могут быть, поэтому при чтении необходим расчёт хэша ключа. Но реализация всё так же основана на FrozenHashTable.

Чтение из ValueTypeDefaultComparerFrozenDictionary может быть до 80% быстрее (рис. 2).

Продолжение тут 👇

Начало тут 👆

SmallValueTypeComparableFrozenDictionary и SmallValueTypeDefaultComparerFrozenDictionary

Строго говоря, два этих класса и не хэш-таблицы вовсе. Поиск значения в них осуществляется не через FrozenHashTable, а простым сравнением элементов в цикле for. Поэтому эти реализации используются, когда в исходном словаре не более 10 элементов.

При этом, SmallValueTypeComparableFrozenDictionary применяется, если тип ключа – это встроенный примитивный значимый тип: int, long, double, enum и т.д. Если же тип ключа, к примеру, record struct, то будет использован тип SmallValueTypeDefaultComparerFrozenDictionary.

Такое разделение разработчики .NET объясняют тем, что у встроенных типов 100% реализован интерфейс IComparable и поэтому можно немного оптимизировать поиск, отсортировав массивы ключей и значений при инициализации словаря:

// ctor
_keys = source.Keys.ToArray();
_values = source.Values.ToArray();

Array.Sort(_keys, _values);
_max = _keys[_keys.Length - 1];

К примеру, если бы нам нужно было найти значение для ключа 10 в словаре как на рисунке 3, то без сортировки пришлось бы обойти весь массив _keys и убедиться, что такого значения в словаре нет. При наличии сортировки достаточно же сравнить с максимальным значением. В данном случае – 9.

Кроме того, поскольку массив ключей _keys отсортирован, можно осуществлять поиск пока искомое значение ключа больше текущего значения _keys[i].

// GetValueRefOrNullRefCore method
if (Comparer<TKey>.Default
  .Compare(key, _max) <= 0)
{
  TKey[] keys = _keys;
  for (int i = 0; i < keys.Length; i++)
  {
    int c = Comparer<TKey>
        .Default.Compare(key, keys[i]);
    if (c <= 0)
    {
      if (c == 0)
      {
        return ref _values[i];
      }
      break;
    }
  }
}
return ref Unsafe.NullRef<TValue>();

Реализация SmallValueTypeDefaultComparerFrozenDictionary похожа на предыдущую, с тем лишь отличием, что в ней не используется сортировка. Соответственно, линейный поиск по массиву ключей _keys будет осуществлён всегда.

Несмотря на все оптимизации в этих двух классах, результаты бенчмарка не выглядят впечатляющими (рис. 4). Даже то небольшое ускорение, которое может дать SmallValueTypeDefaultComparerFrozenDictionary – это всего лишь несколько наносекунд.

На сегодня всё. Код и результаты бенчмарка лежит тут. В следующей части рассмотрим ссылочные типы. Самое интересное там связано со ключами типа string.

– Бобрята, а что это у вас?
– Плотина…
– логи

Год назад я рассказывал о налогах, которые платит работник в России и Сербии. Время обновить информацию, так как с 2025 года айтишникам-мажорам в России придётся платить больше налогов из-за прогрессивной шкалы НДФЛ (рис. 1). Сравним зарплаты условных айтишников трёх уровней:

1. 150 тыс. ₽/мес или 1,8 млн ₽/год.
2. 300 тыс. ₽/мес или 3,6 млн ₽/год.
3. 450 тыс. ₽/мес или 5,4 млн ₽/год.

Ставки 20% и 22% не рассматриваются, так как среднестатистический айтишник не зарабатывает больше 20 млн ₽ в год.

Налог на годовой доход

Сперва работа над ошибками. В прошлый раз забыл рассказать о налоге на годовой доход (рис. 2). В Сербии этим налогом облагается доход, превышающий 3 средние годовые зарплаты. В прошлом году средняя годовая зарплата составляла 1 423 188 динаров или примерно 12 112 €. Следовательно, с доходов свыше 36 337 € нужно было уплатить дополнительный налог.

Особенности этого налога:

1. Если вы моложе 40 лет, планка необлагаемого дохода повышается ещё на 3 средние годовые зарплаты.

2. За каждого несовершеннолетнего члена семьи можно получить 15% вычет, но не более 50% суммарно.

Пока ты молод и с доходом выше среднего, то государство не будет дополнительно обременять налогами – зарабатывай. Но к 40 годам будь добр заведи детей. Тогда налогов будешь платить меньше. Видимо тут такая логика? 🤷

Сравнение NET дохода в России и Сербии

Вернёмся к нашим айтишникам. Повторяться с расчётами не будем, а воспользуемся калькуляторами для расчётов налогов в Сербии и РФ. Подробная математика есть в предыдущем посте. Результаты расчётов на рис. 3.

Разработчику в Сербии с зарплатой эквивалентной 450 тыс. ₽/мес также пришлось бы уплатить налог на годовой доход, при условии, что ему минимум 40 лет. При средней ежемесячной зарплате за 1 квартал 2024 года (131 893 динар), 3 средние годовые зарплаты составят 4 748 148 динар или 40 410 €. Значит, ему придётся заплатить ещё почти 1 700 € налогов.

Таким образом, с точки зрения налогов, быть работником в России всё ещё выгоднее – налоги одни из самых низких.