Начало тут 👆

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.