How caching affects hashing

Я как-то уже постил ссылку на статью How caching affects hashing -- но сейчас дошли руки как-то раскрыть тему. О чем там идет речь, и что там любопытного:

Есть у нас такая штука, как хэш-таблица с открытой адресацией. Довольно несложная в реализации штука (особенно если не реализовывать удаление:), и дает чуть ли не самую лучшую производительность поиска -- не асимптотическую, асимптотически-то все хэш-таблицы имеют "в достаточно хорошем мире" O(n), а реальную. Обусловлено это счастье высокой локальностью хранения данных, и, соответственно, высоким КПД использования кэша (cache-hit ratio).

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

1. линейное хэширование -- linear probing (H_i(KEY) = (H₀(KEY) + k*i) mod N, где k часто берут =1)
2. двойное хэширование -- linear double hashing (H_i(KEY) = (H₀(KEY) + H₁(KEY)*i) mod N)
3. экспоненциальное хэширование -- exponential double hashing (H_i(KEY) = (H₀(KEY) + H₁(KEY)*aⁱ) mod N, где a -- константа)

Если мы предположим, что цена доступа к ячейке памяти постоянна для всех ячеек (как это обычно и полагается при теоретическом анализе производительности алгоритмов), то производительность поиска (и вставки, и пометки на удаление) будет прямо пропорциональна среднему количеству попыток (проб). В свою очередь, неформально рассуждая, среднее количество попыток тем меньше, чем более "равномерно" ключи будут разбросаны по таблице. Можно сделать вывод, что (при фиксированном load factor-е) лучше всего будет работать экспоненциальное хэширование, чуть хуже -- двойное, и хуже всего -- линейное. Более формальные исследования вроде бы подтверждают этот вывод. Например, линейное хэширование определенно приводит к тому, что ключи в таблице стремятся "кучковаться" в кластеры, что как-то не похоже на равномерное распределение.

Интересный вопрос состоит в том, изменится ли результат этого анализа, если вспомнить, что стоимость доступа к ячейке памяти может отличаться на порядок и больше в зависимости от того, попали ли мы в кэш, и в какого уровня кэш мы попали? Очевидно, что линейное хэширование с шагом 1 (самый худший вариант с точки зрения среднего количества проб) -- самое идеальное с точки зрения кэш-локальности!

Мы получаем конфликт -- с одной стороны, чем более "случайна" последовательность проб, тем более равномерно ключи распределены по массиву, тем меньше в среднем придется сделать попыток, чтобы найти нужный нам ключ. С другой стороны, чем "случайнее" последовательность проб, тем получаемый алгоритм менее cache-friendly, тем меньше будет КПД использования кэша. Так ежели слон с китом подерутся -- кто кого заборет?

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

А именно: во-первых, при "хорошей" хэш функции и равномерно распределенных ключах разница в длине последовательности проб между линейным и остальными способами хэширования действительно не так велика. Но это при хорошей хэш-функции и равномерных ключах. А если хэш-функцию взять "на четыре с минусом", и ключи не равномерно распределенные, а какие-нибудь более-менее реалистичные, или load factor высокий... то картина становится гораздо более интересной -- линейное хэширование начинает весьма сильно буксовать. Т.е. квадратичное и экспоненциальное хэширование гораздо более толерантны ко всяким real world issues.

Во-вторых, если размер самой таблицы достаточно мал, чтобы она целиком влезла в кэш, то достаточно быстро она там и окажется, и все доступы к ней будут иметь 100% cache-hit, и тогда выигрывает тот алгорим хэширования, у которого меньшая средняя длина последовательности проб -- а это экспоненциальное хэширование. Двойное хэширование лишь чуть-чуть от него отстает, и обычно этим отставанием можно принебречь. Линейное хэширование тихо курит в уголке.

В-третьих, если таблица большая, и целиком в кэш сильно не влазит, то все будет зависеть от длины ключа. Скажем, если cache-line = 64 байта, и мы храним в таблице ссылки (64 бита), то в одну строку влезет 8 ссылок, и в среднем, в случае линейного хэширования с шагом 1 мы будем иметь 3.5 попытки с почти гарантированным кэш-попаданием. Дальше мы уже залезаем на следующую строку, и вероятность ее присутствия в кэше уже примерно такая же, как и любой другой строки. Т.е. выигрыш линейного хэширования не "100% cache-hit", а всего лишь "1 cache-miss на каждые 3.5 проб", что не так впечатляет. А если размер ключа увеличить, то выигрыш и того меньше. При ключе равном по размеру строке кэша линейное хэширование по cache-hit ratio уже мало чем отличается от остальных -- а по среднему количеству попыток, как известно, проигрывает...

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