[Перевод] Я написал самую быструю хеш-таблицу06.03.2017 16:18

В конце концов я должен был к этому прийти. Когда-то я опубликовал статью «Я написал быструю хеш-таблицу», а потом ещё одну — «Я написал ещё более быструю хеш-таблицу». Теперь я завершил работу над самой быстрой хеш-таблицей. И под этим я подразумеваю, что реализовал самый быстрый поиск по сравнению со всеми хеш-таблицами, какие мне только удалось найти. При этом операции вставки и удаления также работают очень быстро (хотя и не быстрее конкурентов).

Я использовал хеширование по алгоритму Robin Hood с ограничением максимального количества наборов. Если элемент должен быть на расстоянии больше Х позиций от своей идеальной позиции, то увеличиваем таблицу и надеемся, что в этом случае каждый элемент сможет быть ближе к своей желаемой позиции. Похоже, такой подход действительно хорошо работает. Величина Х может быть относительно невелика, что позволяет реализовать некоторые оптимизации внутреннего цикла поиска по хеш-таблице.

Если вы хотите только попробовать её в работе, то можете скачать отсюда. Либо пролистайте вниз до раздела «Исходный код и использование». Хотите подробностей — читайте дальше.

Тип хеш-таблицы

Существует много типов хеш-таблиц. Для своей я выбрал:

Открытую адресацию.
Линейное размещение.
Хеширование Robin Hood.
Количество слотов — простое число (но я реализовал возможность использовать для этой цели числа, являющиеся степенями двойки).
Ограничение максимального количества наборов.

Я считаю, что последний пункт — новинка в сфере хеш-таблиц. Это главная причина высокой производительности моего решения. Но сначала я хотел бы рассказать о предыдущих пунктах.

Открытая адресация означает, что хеш-таблица использует в качестве хранилища данных непрерывный массив. Это не аналог std::unordered_map, когда каждый элемент находится в отдельной куче (heap).

Линейное размещение означает, что если вы пытаетесь вставить элемент в массив, а текущий слот уже заполнен, то вы просто переходите к следующему слоту. Если и он тоже заполнен, то берётся следующий слот, и так далее. У этого простого подхода есть известные недостатки, но я считаю, что они исправляются с помощью ограничения максимального количества наборов.

Хеширование Robin Hood означает, что при линейном размещении вы пытаетесь расположить каждый элемент как можно ближе к его идеальной позиции. Это делается с помощью перемещения окружающих элементов при вставке или удалении какого-то элемента. Принцип такой: берём из богатых элементов (rich elements) и передаём в бедные элементы (poor elements). Отсюда и взялось название Robin Hood. Богатым называется элемент, получивший слот поблизости от своей идеальной точки вставки (insertion point). Бедный элемент находится далеко от идеальной точки вставки. Вставляя новый элемент, вы отсчитываете, насколько далеко он находится от идеальной позиции. Если дальше, чем текущий элемент, то вы ставите новый на место текущего, а затем уже для него пытаетесь найти новое место.

Количество слотов — простое число: размер массива, лежащего в основе хеш-таблицы, равен простому числу. Это означает, что он может вырасти, например, с 5 слотов до 11, затем до 23, до 47 и так далее. Когда нужно найти точку вставки, то для присваивания слоту значения хеша элемента используется оператор по модулю (modulo operator). Другой вариант — делать размер массива равным степени двойки. Ниже мы поговорим о том, почему по умолчанию я использую простые числа и когда целесообразно применять оба варианта.

Ограничение максимального количества наборов

C основами разобрались, давайте теперь обсудим моё решение: ограничение максимального количества слотов, в которых таблица будет выполнять поиск, после чего плюнет и увеличит размер массива.

Сначала идея была в том, чтобы сделать это количество очень небольшим, например равным 4. То есть при вставке я сначала пробую идеальный слот, если не получается — то обращаюсь к следующему, затем к следующему, затем к следующему, и если все они оказываются заполнены, то я увеличиваю таблицу и снова пытаюсь вставить элемент. Это прекрасно работает на маленьких таблицах. Но при вставке случайного значения в большую таблицу я всё время буду терпеть неудачу с этими четырьмя наборами, мне придётся увеличивать размер таблицы, даже если она по большей части пустая.

В конце концов я обнаружил, что при верхней границе, равной log2(n), где n — количество слотов в таблице, перераспределение (reallocate) выполняется, только когда она заполнена примерно на 2/3. Это при вставке случайного значения. А если вставлять последовательные значения, то можно заполнить таблицу целиком, и только тогда она будет перераспределена.

Но несмотря на эмпирически найденный порог в 2/3, время от времени перераспределение запускалось при 60%-м заполнении таблицы. Изредка — даже при 55%-м. Поэтому я присвоил max_load_factor таблицы значение 0,5. Это означает, что таблица будет увеличиваться при заполнении в 50%, даже если не был достигнут предел по количеству наборов. Я сделал это для того, чтобы вы могли доверить таблице перераспределение, когда вы действительно увеличиваете её размер: если вы вставляете тысячу элементов, затем пару из них удаляете, а потом снова вставляете столько же, то можете быть почти полностью уверены, что таблица не будет перераспределена. У меня нет точной статистики, но я прогнал простой тест, в котором построил тысячи таблиц всевозможных размеров и заполнил их случайными числами. В сумме я выполнил вставку сотен миллиардов чисел, и лишь один раз было перераспределение при коэффициенте заполнения (load factor) меньше 0,5 (таблица увеличилась при заполнении 48%). Так что вы можете доверять такому механизму: он очень-очень-очень редко перераспределяет, когда вы этого не ждёте.

В общем, если вам не нужно контролировать увеличение таблицы, свободно присваивайте max_load_factor значение повыше. Без опаски ставьте вплоть до 0,9: высокая скорость выполнения всех операций обеспечивается комбинацией Robin Hood и ограничения на количество наборов. Но не присваивайте значение 1,0: может возникнуть ситуация, когда при вставке начнётся перемещение каждого элемента таблицы, чтобы заполнить последний оставшийся слот. Например, все слоты, в которых хочет быть последний элемент, уже заняты, за исключением последнего пустого. Тогда вы вставляете элемент в первый слот, в котором он хочет находиться, но тот уже занят. Вам придётся переместить существующий элемент во второй слот, оттуда выселить элемент в третий, и так по цепочке до конца таблицы. В результате вы получите таблицу, в которой все элементы, за исключением самого первого, находятся в одном слоте от своих идеальных позиций. Поиск всё ещё будет выполняться быстро, но последняя вставка займёт много времени. Если же у вас окажется несколько свободных слотов поблизости, то вставляемый элемент передвинет не так много соседей.

Если задать max_load_factor такое низкое значение, что предел по количеству наборов никогда не будет достигнут, то зачем вообще что-то ограничивать? Благодаря этому ограничению можно реализовать тонкую оптимизацию: допустим, вы перехешировали таблицу, чтобы получить 1000 слотов. В моём случае таблица вырастет до 1009, это ближайшее простое число. Двоичный логарифм 1009 округлённо равен 10, так что я ограничиваю количество наборов десятью. Теперь применим хитрость: вместо массива на 1009 слотов сделаем массив на 1019. Но все остальные операции хеширования будут считать, что у нас всего 1009 слотов. Теперь, если два элемента хешируются в индекс 1008, то я могу перейти в конец и вставить в индекс 1009. Мне не нужно проверять диапазон изменения индексов (bounds checking), потому что ограничение количества наборов не даст мне выйти за индекс 1018. Если же у меня будет 11 элементов, которые хотят попасть в последний слот, то таблица увеличится и все эти элементы захешируются в разные слоты. Благодаря отсутствию граничной проверки у меня получаются компактные внутренние циклы. Вот как выглядит функция поиска:

iterator find(const FindKey & key)
{
    size_t index = hash_policy.index_for_hash(hash_object(key));
    EntryPointer it = entries + index;
    for (int8_t distance = 0;; ++distance, ++it)
    {
        if (it->distance_from_desired < distance)
            return end();
        else if (compares_equal(key, it->value))
            return { it };
    }
}

По сути, это линейный поиск. Код прекрасно преобразуется в ассемблер. Такой подход лучше простого линейного размещения по двум причинам:

Нет проверки диапазона изменения индексов. Пустые слоты имеют значение distance_from_desired, равное –1, так что это аналогично поиску другого элемента.
В цикле выполняется не больше log2(n) итераций. Обычно при поиске в хеш-таблицах худшая временная сложность равна O (n). В моей таблице — O (log n). Это серьёзная разница. Особенно с учётом того, что при линейном размещении предпочтительнее худший вариант, поскольку элементы склонны к группированию.

Мои накладные расходы по памяти — 1 байт на элемент. Я храню distance_from_desired в int8_t. То есть при выравнивании типа (alignment of the type) вставляемого элемента будет плюсоваться (padded out) 1 байт. Так что если вы вставляете целочисленные значения, то 1 байт получит ещё 3 байта паддинга, в результате выйдет 4 байта накладных расходов на каждый элемент. Если вы вставляете указатели, то паддинг будет уже 7 байтов, получаем 8 байтов накладных расходов. Для решения этой проблемы я рассматриваю вариант с изменением схемы использования памяти, но опасаюсь, что тогда у меня на каждый поиск будет два промаха кеша (cache misses) вместо одного. Так что накладные расходы по памяти — 1 байт на элемент + паддинг. И при значении max_load_factor по умолчанию 0,5 ваша таблица будет заполняться только на 25—50%, так что общие накладные расходы ещё выше. Напомню, что ради экономии памяти можно без боязни увеличивать max_load_factor до 0,9, это приведёт лишь к незначительному снижению скорости.

Производительность поиска

Не так-то просто выяснить производительность хеш-таблиц. Как минимум нужно измерять скорость в таких ситуациях:

Поиск элемента, находящегося в таблице.
Поиск элемента, отсутствующего в таблице.
Вставка группы случайных чисел.
Вставка группы случайных чисел после вызова reserve().
Удаление элементов.

И каждую из этих ситуаций нужно прогонять с разными ключами и значениями разных размеров. В качестве ключа я использую целочисленное или строковое значение, а типы-значения размером 4, 32 и 1024. Предпочитаю целочисленные значения, потому что со строковыми вы по большей части измеряете накладные расходы хеш-функции и оператора сравнения, одинаковые для всех хеш-таблиц.

Нужно тестировать поиск как при наличии элемента в таблице, так и при его отсутствии, потому что в этих случаях производительность может кардинально различаться. Например, я столкнулся с непростой ситуацией, когда вставил все числа от 0 до 500 000 в google::dense_hash_map (не случайные числа), а потом выполнил поиск отсутствующего элемента. Неожиданно оказалось, что хеш-таблица работает в 500 раз медленнее, чем обычно. Это крайний случай — использование степени двойки для задания размера таблицы. Вероятно, нужно было проводить измерения со случайными числами и с последовательными, но тогда получилось бы слишком много графиков. Так что я ограничусь только случайными числами, они избавляют от возникновения неудачных ситуаций с производительностью из-за специфических паттернов.

Первый график — поиск элемента, присутствующего в таблице:

Графики расположены довольно плотно. flat_hash_map — это моя новая хеш-таблица. flat_hash_map_power_of_two — та же самая таблица, но размер массива определяется степенью двойки, а не простым числом. Как видите, второй вариант заметно быстрее, причину я объясню потом. dense_hash_map — это google::dense_hash_map, самая быстрая из найденных мной хеш-таблиц. sherwood_map — старая таблица из «Я написал более быструю хеш-таблицу». К моему конфузу, она показала посредственные результаты… std::unordered_map и boost::unordered_map — всё понятно из названий. multi_index — это boost::multi_index.

Немного обсудим этот график. Ось Y — количество наносекунд, затраченных на поиск одного элемента. Я использовал Google Benchmark, который за полсекунды раз за разом вызывает функцию table.find(), а потом подсчитывает, сколько раз он смог это сделать. Общая длительность итераций делится на их количество, получаются наносекунды. Все искомые ключи присутствуют в таблице. Для оси Х я взял логарифмическую шкалу, потому что она хорошо описывает изменение производительности. К тому же такая шкала позволяет оценить производительность для таблиц разных размеров: если вас интересуют маленькие таблицы, то смотрите на левую часть графика.

Сразу бросается в глаза зубчатость графиков. Дело в том, что все таблицы имеют разную производительность в зависимости от текущего коэффициента заполнения (load factor), то есть степени заполнения. При 25% поиск будет выполняться быстрее, чем при 50%: чем больше заполнена таблица, тем больше возникает коллизий хешей. Стоимость поиска растёт, и в какой-то момент таблица решает, что она заполнилась слишком сильно и пора перераспределяться, что снова приводит к ускорению поиска.

Это было бы очевидно, если бы я вывел графики коэффициента заполнения для каждой таблицы. Также вы бы сразу увидели, что нижние графики получены при max_load_factor, равном 0,5, а верхние — при 1,0. Сразу возникает вопрос: были бы таблицы из верхних графиков быстрее нижних при том же значении — 0,5? Были бы, но очень незначительно. Далее мы рассмотрим эту ситуацию более развёрнуто. На приведённом графике видно, что нижняя точка верхних графиков, когда таблицы только что перераспределились и имеют коэффициент заполнения чуть больше 0,5, расположена гораздо выше верхней точки нижних графиков прямо перед перераспределением, из-за того что их коэффициент заполнения приближается к 0,5.

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

Поэтому я попытался придумать тест, который показал бы скорость работы таблицы, не находящейся в кеше. Я создал столько таблиц, чтобы они не помещались в L3, и использовал разные таблицы для каждого искомого элемента. Допустим, я хочу измерить скорость работы таблицы, содержащей 32 элемента по 8 байтов. Размер моего кеша L3 — 6 Мб, так что в него помещается примерно 25 тыс. таких таблиц. Чтобы удостовериться, что таблицы в кеше отсутствуют, я создал их с запасом — 75 тыс. штук. И каждый поиск выполнялся в отдельной таблице.

Я убрал пару линий, потому что они были малоинформативны. boost::unordered_map и std::unordered_map обычно демонстрируют одинаковую производительность, и никому нет дела до моей старой медленной таблицы sherwood_map. Теперь у нас остались: std::unordered_map в качестве обычного контейнера на базе узлов (node based container), boost::multi_index в качестве быстрого контейнера на базе узлов (думаю, что std::unordered_map может быть не менее быстрым), google::dense_hash_map в качестве быстрого контейнера с открытой адресацией (open addressing container) и мой новый контейнер в двух версиях — на основе простых чисел и степеней двойки.

В новом бенчмарке графики сразу начали сильно различаться. Паттерн, который проявился на графике первого бенчмарка, на графике второго бенчмарка стал заметен очень рано, начиная с 10 элементов. Впечатляет: все таблицы демонстрируют стабильную производительность в очень большом диапазоне количества элементов.

Давайте посмотрим графики неудачного поиска — то есть поиска элемента, отсутствующего в таблице.

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

Эти графики убедили меня, что моя новая таблица — большой шаг вперёд. Красная линия показывает работу моей таблицы, сконфигурированной так же, как dense_hash_map: max_load_factor 0,5, а выбор для определения размера степени двойки позволяет помещать хеш в слот просто по младшим битам. Единственное большое отличие: моя таблица использует дополнительный байт для хранения (плюс паддинг) на каждый слот, то есть потребляет чуть больше памяти, чем dense_hash_map.

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

Простые числа или степень двойки

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

Хеширование ключа.
Размещение ключа в слоте.
Получение памяти для этого слота.

Этап 1 может быть дёшев, если ключ — целое число: просто бросьте его в size_t. Но при ключах других типов, например строковых, этап будет дороже.

Этап 2 — целое число по модулю (integer modulo).

Этап 3 — разыменование указателя. В случае с std::unordered_map это разыменование нескольких указателей.

Может показаться, что если у вас не слишком медленная хеш-функция, то этап 3 получается самым дорогим из всех. Но если у вас нет промахов кеша при каждом одиночном поиске, то, скорее всего, самым дорогим этапом окажется второй. Целое число по модулю обрабатывается медленно даже на мощном железе. Согласно данным Intel, это требует от 80 до 95 циклов.
Это главная причина, по которой действительно быстрые хеш-таблицы обычно используют степень двойки для определения размера массива. Потому что потом вам будет достаточно убирать старшие биты, что можно делать в один цикл.

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

Да, всё верно: google::dense_hash_map ушла в стратосферу. Для этого достаточно было дать ей набор чисел по порядку: [0, 1, 2, …, n — 2, n — 1]. Если сделать это и поискать ключ, которого нет в таблице, то поиск будет крайне медленным. Если ключ есть, то всё нормально, работает быстро. При этом разница в производительности между удачным и неудачным поиском может достигать тысячи крат.

Ещё один пример проблемы из-за степени двойки: стандартная хеш-таблица в Rust стала демонстрировать квадратичное поведение (quadratic) при вставке ключей из одной таблицы в другую. Так что использование степени двойки может привести к неприятным сюрпризам.

Так произошло, что моя таблица избежала всех этих проблем благодаря ограничению количества наборов. Не было даже ненужных перераспределений. Но это не означает, что моя таблица неуязвима для побочных эффектов использования степени двойки. Например, как-то я столкнулся с тем, что при вставке указателей в такую таблицу некоторые слоты постоянно пустовали. Причина в том, что в моей программе кучи были выделены с 16-байтным выравниванием, при этом я использовал хеш-функцию, которая по отношению к указателю просто выполняла reinterpret_casted в size_t. Из-за этого в таблице использовалась лишь одна шестнадцатая всех слотов. Вы можете столкнуться с той же проблемой при использовании степени двойки в моей хеш-таблице.

Все эти проблемы решаемы, если вы позаботитесь о выборе хеш-функции, которая подходит для вводимых вами данных. Но это не слишком удобно: приходится быть настороже при использовании хеш-таблицы. Иногда с этим нет проблем, но иногда не хочется заморачиваться. Хочется, чтобы просто работало, и без неожиданных тормозов. Поэтому я решил в своей таблице по умолчанию использовать размер на основе простых чисел (а степень двойки задаётся опционально).

Почему с простыми числами нет проблем? Не могу объяснить с точки зрения математики, но интуиция подсказывает, что у них нет общих делителей с другими числами, всегда будут разные остатки. Допустим, я использую степень двойки, в моей таблице 32 слота, и я пытаюсь вставить указатели с 16-байтным выравниванием (то есть все мои числа кратны 16). Теперь при поиске слота в таблице с помощью целого числа по модулю я получу только два возможных слота: 0 или 16. Поскольку 32 кратно 16, вы просто не можете получить других значений. Если же взять размер на основе простого числа, то этой проблемы не возникнет. Допустим, у меня 37 слотов, тогда при всех делениях с кратностью 16 я смогу использовать все 37 слотов.

Как можно решить проблему низкой производительности вычисления целого числа по модулю? Я позаимствовал трюк из boost::multi_index: заставил все числа по модулю использовать статическую константу (compile time constant). Я не разрешаю брать в качестве размера таблицы любые возможные простые числа. Я сделал специальную подборку чисел, которая и применяется при увеличении таблиц. Также я сохраняю индекс числа из вашей таблицы. Когда для присвоения слоту хеш-значения нужно вычислить целое число по модулю, выполняется вот что:

switch(prime_index)
{
case 0:
    return 0llu;
case 1:
    return hash % 2llu;
case 2:
    return hash % 3llu;
case 3:
    return hash % 5llu;
case 4:
    return hash % 7llu;
case 5:
    return hash % 11llu;
case 6:
    return hash % 13llu;
case 7:
    return hash % 17llu;
case 8:
    return hash % 23llu;
case 9:
    return hash % 29llu;
case 10:
    return hash % 37llu;
case 11:
    return hash % 47llu;
case 12:
    return hash % 59llu;
//
// ... ещё варианты
//
case 185:
    return hash % 14480561146010017169llu;
case 186:
    return hash % 18446744073709551557llu;
}

Каждый из вариантов — целое число по модулю на основе статической константы. Чем это хорошо? Если использовать константу, то компилятор применит кучу оптимизаций для ускорения вычисления. Для каждого из вариантов вы получаете кастомный ассемблерный код, который будет работать гораздо быстрее, чем целое число по модулю. Выглядит несколько безумно, но даёт огромный прирост скорости.

Вы можете наблюдать разницу на вышеприведённом графике: при использовании простых чисел скорость чуть ниже, но всё равно высокая по сравнению с другими хеш-таблицами, к тому же мы получаем защиту от большинства проблем. Конечно, это не панацея. Если вас сильно это беспокоит, то можете прибегнуть к std::map со строгим ограничением верхней границы. Однако дело в том, что при использовании степени двойки риск куда выше, и приходится проявлять осторожность. В случае же с простыми числами вы нарвётесь на проблему, только если специально создадите ключи с подвохом.

Это подводит нас к вопросу о безопасности. На хеш-таблицу можно провести умную атаку с помощью ключей, которые все конфликтуют друг с другом. Как это провернуть? Если вы знаете, что веб-сайт использует во внутренних кешах хеш-таблицу, то можете составить такие запросы к сайту, которые все будут конфликтовать в этой таблице. Таким образом можно сильно замедлить работу внутреннего кеша веб-сервера с вероятностью положить сайт. Например, если вы знаете, что использует dense_hash_map, у которой проблемы с последовательными числами, то можно просто последовательно запрашивать сайты в надежде, что это загадит их кеши.

Надо сказать, что настройка максимального количества наборов в моей таблице не даёт злоумышленникам заполнить её плохими ключами. Но тут возникает новый источник угрозы: если вы знаете, какой набор простых чисел используется в моей таблице, то вы можете вставить ключи в таком порядке, чтобы таблица постоянно упиралась в ограничение по наборам и постоянно перераспределялась. Это приведёт к исчерпанию памяти на сервере. Уязвимость закрывается с помощью кастомной хеш-функции, но я не буду советовать, что вам искать. Могу лишь сказать, что если используете хеш-таблицу в окружении, где пользователи могут вставлять ключи, то откажитесь от std::hash в качестве хеш-функции, поищите функцию с сохранением текущего состояния (stateful), поведение которой нельзя прогнозировать с течением времени. С другой стороны, если вы не думаете, что среди ваших пользователей будут злоумышленники, то спокойно используйте мою таблицу в версии с простыми числами.

Но, допустим, вы знаете, что ваша хеш-функция возвращает хорошо распределённые числа, и у вас редко могут возникать коллизии даже при использовании степени двойки. Тогда пускайте в дело вторую версию моей таблицы. Для этого достаточно с помощью typedef определить тип hash_policy в объекте хеш-функции. Я решил поместить эту настройку в объект, потому что именно здесь можно выяснить качество возвращаемых ключей.

Итак, вы поместили typedef в свой объект кастомной хеш-функции:

struct CustomHashFunction
{
    size_t operator()(const YourStruct & foo)
    {
        // ваша хеш-функция
    }
    typedef ska::power_of_two_hash_policy hash_policy;
};

// далее:
ska::flat_hash_map your_hash_map;

В вашей хеш-функции задаём для hash_policy тип ska::power_of_two_hash_policy. После этого flat_hash_map переключится на использование степени двойки. Если в данном случае вам подходит std::hash, то можете взять тип power_of_two_std_hash, который просто вызывает std::hash, но с применением power_of_two_hash_policy:

ska::flat_hash_map> your_hash_map;

В любом случае вы можете получить ещё более быструю хеш-таблицу, если знаете, что у вас будет мало коллизий.

Производительность вставки и удаления

После такого отвлечения на теорию давайте вернёмся обратно к производительности моей таблицы. Ниже приведён график, на котором отражена производительность при вставке элемента. Я измерял, сколько времени уходит на вставку N элементов, и делил время на их количество. График отражает скорость работы таблицы без вызова reserve() перед вставкой элемента:

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

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

В этом бенчмарке google::dense_hash_map обошла мою новую таблицу, но не сильно. Дело в том, что dense_hash_map не перемещает элементы при вставке. Она просто ищет пустой слот и вставляет туда элемент. Используемое мной хеширование Robin Hood требует перемещать уже существующие элементы при вставке нового, чтобы сохранить свойство «каждый узел должен быть как можно ближе к своей идеальной позиции». Это компромисс между стоимостью вставки и скоростью поиска. Но я рад, что у меня небольшое падение производительности.

Теперь измерим, как будет вставляться элемент, если сначала вызвать reserve():

Не знаю, что происходит в конце с контейнерами на базе узлов. Интересно было бы разобраться, но я этого не сделал. Подозреваю, что дело в вызове malloc в моей стандартной библиотеке (Linux gcc). Во время измерений для этого и других графиков я столкнулся с несколькими проблемами, потому что некоторые операции по непонятным причинам занимали много времени.

Но в целом график выглядит аналогичным предыдущему, за исключением меньшей зубчатости из-за того, что reserve избавляет от необходимости перераспределять. Моя таблица выполняет вставку быстро, но не так, как google::dense_hash_map.

Теперь посмотрим, сколько времени уходит на удаление элементов. Для этого я построил массив из N элементов и замерил длительность удаления каждого из них в случайном порядке. Затем поделил общее время на N:

Контейнеры на базе узлов снова показали плохие результаты, остальные идут ноздря в ноздрю. Моя таблица стирает примерно за 23 наносекунды, а dense_hash_map — за 20. В целом обе работают очень быстро.

Но между ними есть одно большое различие: когда dense_hash_map стирает элемент, то оставляет в таблице «надгробие» (tombstone). Оно будет убрано только в том случае, если вы вставили в слот новый элемент. «Надгробие» представляет собой требование квадратичного размещения (quadratic probing), которое google::dense_hash_map выполняет в ходе поиска: при стирании элемента очень трудно найти другой элемент, чтобы взять его слот. При хешировании Robin Hood с его линейным размещением нет никаких трудностей с поиском элемента, который может занять опустевший слот: просто перемещаем следующий элемент вперёд, если он ещё не находится на своей идеальной позиции. А при квадратичных наборах может потребоваться элемент, расположенный через четыре слота. И при его перемещении снова придётся решать проблему поиска узла для вставки в свежеосвободившийся слот. Так что вместо этого вставляются «надгробия», которые игнорируются таблицей при поиске. Они будут заменены при следующей операции вставки.

Всё это означает, что если в таблице есть «надгробия», то она будет работать чуть медленнее. Поэтому быстрое удаление в dense_hash_map оборачивается некоторым замедлением поиска после удаления. Оценить это влияние довольно трудно, но мне кажется, что я нашёл подходящий тест: я снова и снова вставляю и удаляю элементы:

Сначала генерирую миллион случайных целых чисел. Затем вставляю их в хеш-таблицу, стираю, снова вставляю. Причём делаю это в случайном порядке. Скажем, у меня есть только четыре числа: 1, 2, 3 и 4. Правильный порядок для «вставить, стереть, снова вставить» будет: вставить 1, вставить 3, стереть 1, вставить 2, вставить 4, стереть 4, вставить 4, вставить 1, стереть 2, стереть 3, вставить 3, вставить 2. Каждый элемент вставляется, стирается и снова вставляется, но в случайном порядке. На графике показана длительность вставки одного элемента в зависимости от общего количества вставок. Первая контрольная точка — просто вставка миллиона элементов. Вторая — вставка миллиона элементов, их удаление и снова вставка (в случайном порядке). Третья контрольная точка — вставка, удаление, вставка, удаление, вставка. То есть всего три вставки. И так далее.

Поначалу dense_hash_map работает быстрее за счёт того, что у неё процедура вставки выполняется быстрее. На второй контрольной точке моя таблица её догнала, а на третьей — обогнала. После 6 миллионов вставок версия моей таблицы с простыми числами даже вышла на второе место. Мои таблицы становились всё быстрее, потому что чем больше удалений, тем ниже должен быть коэффициент заполнения. Если достаточно часто вставлять и удалять миллион элементов, то в таблице постоянно будет одномоментно находиться около 500 тыс. элементов. И чем дольше прогонять цикл вставка-удаление-вставка, тем ниже будет средняя одномоментная заполненность. Моя таблица от этого выигрывает, а в dense_hash_map накапливаются «надгробия», мешающие увеличивать производительность. Хотя по сравнению с другими таблицами dense_hash_map остаётся очень быстрой:

Как показывает график, использование квадратичного размещения в dense_hash_map полностью оправданно, даже с учётом вставки «надгробий». Эта таблица работает гораздо быстрее любых других контейнеров на базе узлов. Но всё же линейное размещение Robin Hood обеспечивает более элегантный способ удаления элементов: не составляет труда найти элемент, который отправится в освободившийся слот. Это будет преимуществом для страниц, где часто приходится удалять и вставлять элементы.

Сравнение таблиц с разным max_load_factor ()

Давайте посмотрим, как можно решить проблему использования таблицами std::unordered_map и boost::multi_index коэффициента max_load_factor, равного 1,0, в то время как моя таблица и google::dense_hash_map используют 0,5. Станут ли другие таблицы работать быстрее при более низком max_load_factor? Чтобы выяснить это, я прибегнул к первому бенчмарку (удачный поиск), задал на каждой таблице max_load_factor 0,5. А затем провёл замеры перед самыми перераспределениями таблиц.

Итак, max_load_factor у всех равен 0,5, и я хотел измерить скорость работы, когда у них действительно будет такой коэффициент заполнения, так что я провёл измерения прямо перед перераспределениями. Если вернётесь к самому первому графику, то представьте, что я просто соединил прямыми линиями пики зубцов. Думаю, это правильный график, если вам нужно сравнить производительность хеш-таблиц напрямую, без влияния различных значений max_load_factor и стратегий перераспределения.

Здесь flat_hash_map работает быстрее dense_hash_map, как и в первом бенчмарке. Кстати, причина недолгого преимущества dense_hash_map в том, что эта таблица использует меньше памяти: она ещё помещается в кеш L3, а flat_hash_map уже нет.

Но всё же главной задачей этого бенчмарка было сравнение boost::multi_index и std::unordered_map, использующих max_load_fact