Данная работа была выполнена как учебная в ходе курса МФТИ «Введение в эмуляцию вычислительных систем, компиляторные технологии и промышленное программирование».

Цель

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

В работе используются

Язык программирования C\C++; набор компиляторов GCC; инструмент callgrind утилиты valgrind; инструмент визуализации KCachegring.

Экспериментальная установка

Ноутбук фирмы "Honor" на процессоре "AMD Ryzen 5 5500U with Radeon Graphics" с OS "GNU/Linux 22.04.1-Ubuntu x86_64".

Теоретическая справка

Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку определенной длины(также называемую ключем). Возвращаемые хеш-функцией значения менее разнообразны, чем входные значения. Случай, при котором хеш-функция преобразует более чем одно значение входных данных в одинаковые ключи, называется "коллизией". Вероятность возникновения коллизий используется для оценки качества хеш-функций.

Ассоциативный массив — абстрактный тип данных, позволяющий хранить пары вида (ключ, значение). Реализация ассоциативного массива может быть представлена хеш-таблицей с разрешением коллизий путем цепочек(каждая ячейка - односвязанный список).

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

Глава первая. Исследование дисперсии хеш-функций

Так как вычисляемая дисперсия распределения хеш-функций зависит от размеров хеш-таблицы, то выберем ее размеры оптимальным путем для текущей задачи: заселенность таблицы будет 10-15 элементов.

Далее будет приведены разные реализации хеш-функции с их описанием и дисперсией в случае близкого к равномерному распределения(тогда дисперсия будет наименьшей).
Все реализации имеют следующую сигнатуру.

typedef uint32_t Hash;
Hash GetHash(const char *value);

Хеш-функция №1: Эквивалентная константе

Hash GetHash(const char *value)
{
    return CONSTANT_VALUE;
}

Хеш-функция возвращает константу для каждого полученного значения.
Самая легкая реализация, но функция обладает крайней неэффективностью.
Неприменима.

Распределение хеш-функции

Хеш-функция №2: Длина значения

Hash GetHash(const char *value)
{
    return strlen(value);
}

Хеш-функция возвращает длину полученного значения. Очевидно, для задач с похожей длиной ключей неэффективна(например: хранение пар имя-фамилия).
Неприменима.

Распределение хеш-функции

Хеш-функция №3: Сумма элементов значения

Hash GetHash(const char *value)
{
    Hash hash = 0;
    size_t size = strlen(value);
    for (size_t i = 0; i < size)
        hash += value[i];
    return hash;
}

Хеш-функция возвращает сумму элементов полученного значения. Распределение данной реализации будет зависеть от диапазона значений элемента значения и средней длины значений.

Имеет лучшее распределение, чем все предыдущие реализации, но качество распределения сильно зависит от набора данных.

Неприменима.

Распределение хеш-функции

Хеш-функция №4: Среднее значение элемента

Hash GetHash(const char *value)
{
    Hash hash = 0;
    size_t size = strlen(value);
    for (size_t i = 0; i < size)
        hash += value[i];
    return hash/size;
}

Хеш-функция возвращает среднее значение элемента полученного значения. Распределение данной реализации пиками будет совпадать с частотностью элементов.

Распределение будет зависеть от частотности элементов значений.

Неприменима.

Распределение хеш-функции

Хеш-функция №5: Сумма элементов значения при циклическом сдвиге вправо

Hash GetHash(const char *value)
{
    Hash hash = 0;
    size_t size = strlen(value)
    for (size_t i = 0; i < size)
        hash = ROR(hash) + value[i];
    return hash;
}

Хеш-функция возвращает сумму элементов полученного во время циклического сдвига вправо. Данная реализация имеет хорошее распределение.
Приемлема для использования.

Распределение хеш-функции

Хеш-функция №6: Сумма элементов значения при циклическом сдвиге влево

Hash GetHash(const char *value)
{
    Hash hash = 0;
    size_t size = strlen(value);
    for (size_t i = 0; i < size)
        hash = ROL(hash) + value[i];
    return hash;
}

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

Распределение хеш-функции

Хеш-функция №7: CRC

Hash GetHash(const char *value)
{
    Hash hash = 0;
    size_t size = strlen(value);
    for (size_t i = 0; i < size)
    {
        for (bit bitValue : value[i])
            hash = ROR(hash) + bitValue;
        if (NeedXor(hash))
            hash ^= POLINOM;
    }
    return hash;
}

Алгоритм данной хеш-функции можно описать как полиномиального деления(вместо деления - исключающее или) в столбик.

Приемлема для использования.

Распределение хеш-функции

Хеш-функция №8: GNU

Hash GetHash(const char *value)
{
    Hash hash = START_VALUE;
    size_t size = strlen(value);
    for (size_t i = 0; i < size)
        hash = (hash >> 5 + hash) + value[i];
    return hash;
}

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

Распределение хеш-функции

Итоги главы

Так как только у последних четырех реализаций хорошие(малые) дисперсии, то только они и будут отражены в гистограммах.

Как видно из гистограмм, GNU - обладает наилучшей дисперсией.

Глава вторая. Оптимизация работы хеш-таблицы

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

Для тестирования модели была выбрана GNU реализация хеш-функции из-за наилучшего(наименьшего) показателя дисперсии.

Размер модели базы данных - 163 900 уникальных пар (строка:строка).

Размер модели хеш-таблицы - 13 441 ячеек. Заселенность - 12.2.

Тестирование будет проходить следующим образом:

• Загрузка базы данных в хеш-таблицу

• Поиск заранее предопределённого набора данных в хеш-таблице(общее количество вызова функции поиска - 1 000 000)

• Очистка хеш-таблицы

Оптимизация №0: Изначальная реализация.

Замерим изначальные характеристики модели для последующего сравнения.

Результаты замеров

Оптимизация №1: Увеличение размеров таблицы

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

Оптимизировать данную функцию можно двумя способами:

• Написать свою реализацию на языке ассемблера

• Понизить нагрузку на функцию, уменьшив количество вызовов

Так как любая ассемблерная оптимизация нежелательна из-за понижения ясности и переносимости кода, то первый вариант мы оставим на потом.

Значит будем рассматривать второй вариант. Проанализировав все вызовы __strcmp_avx2, было замечено, что большинство вызовов данной функции происходит в следствии малого размера хеш-таблицы. Для каждого поиска элемента в таблице надо вызвать от 1 до 15 раз __strcmp_avx2. Если увеличить размер таблицы до рекомендуемой заселенности(1-2 элемента на ячейку), то количество вызовов должно сократится.

В данной оптимизации размер таблицы был увеличен с 13 441 до 112 111, а заселенность с 12.2 до 1.5.

Результаты замеров

- прирост производительности относительно начального измерения)
- прирост производительности относительно предыдущего измерения)
. Больше - лучше)

Оптимизация №2: Замена реализации хеш-функции

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

Как видно, в среднем на один вызов функции приходится 90 инструкций. Можно предположить, что реализация не является достаточно эффективной. Для решения данной проблемы можно либо написать свою реализацию на языке ассемблера, либо использовать ассемблерную вставку. Так как данная функция не будет inline(в следствии времени ее выполнения и количества мест ее вызова), при полностью ассемблерной реализации, мы не получим никаких оптимизаций компилятора, когда при ассемблерной вставке какие-то оптимизации да и останутся. Так что, было принято решение использовать ассемблерную вставку.

Результаты замеров

Оптимизация №3: Оптимизация функции поиска элемента

Проанализируем таблицу из предыдущей главы. Так как GetHash уже была оптимизирована, то ее пропустим. Видно, что лимитирующим фактором является Get.

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

Результаты замеров

Так как изначально данная оптимизация - ассемблерная(то есть трудно читаемая и переносимая), то использовать ее при малом приросте(~1%) нежелательно. Из возможных вариантов можно либо:

• Откатить все изменения данной оптимизации

• реализовать больший фрагмент кода на языке ассемблера

Так как наша задача - учебная, то был принят второй вариант.

Результаты замеров

В данной реализации прирост уже более значим, хоть и пришлось увеличить количество ассемблерных строк с 12 до 30. Если бы задача не была учебной, то предпочтительней было бы отказаться от данной оптимизации.

Далее будет использоваться вторая версия данной оптимизации.

Оптимизация №4: Замена стандартных функций работы с динамической памятью

Проанализируем таблицу из предыдущей главы. Так как GetHash и Get уже были оптимизированы, то их пропустим. Видно, что лимитирующим фактором является библиотечный аллокатор динамической памяти. Также видно, что в таблице функции работы с динамической памятью занимают весомый процент инструкций.

Текущее представление использования динамической памяти - малые разобщенные области памяти, объединенные в односвязные списки. Так как скорость работы аллокатора линейно зависит от количества вызовов(и то, что эти вызовы могут происходить и в пользовательском коде), а также скорость работы DestroyHashTable линейно зависит от количества элементов в таблице, то можно заменить библиотечные функции работы с динамической памятью на свои. Они будут реализованы так же, как и библиотечные, но будут работать в заранее выделенной области памяти. Наша реализация будет работать быстрей так как все области памяти будут иметь один и тот же размер. Так выделение памяти не будет зависеть от количества вызовов malloc/calloc/realloc в пользовательском коде, а также очистка базы данных будет сводиться к одному вызову free.

Но у данного решения есть важный недостаток - заполнение буфера.

При наступлении данного события можно:

• Увеличить размер таблицы, что влечет пересчитывание адресов для каждого элемента

• Выдавать ошибку переполнения буфера

Был принят второй вариант, и добавлен дисклеймер, что максимальное количество элементов, которые можно поместить в таблицу, равно table.size * LOAD_FACTOR. Так как рекомендую подбирать размер таблицы, чтобы в среднем на одну ячейку приходилось 1-2 элемента, то можно взять LOAD_FACTOR как 2 или 3.

Результаты замеров

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

Оптимизация №5: Подмена типов ключа и значения, нормирование базы данных

Проанализируем таблицу из предыдущей главы. Так как GetHash и Get уже были оптимизированы, то их пропустим. Видно, что лимитирующим фактором является ранее знакомая нам функция__strcmp_avx2.

Ранее мы оптимизировали код, снизив нагрузку на нее. Теперь используем ранее отложенную оптимизацию - замена реализации на ассемблерную. Наилучший способ использовать конкретную ассемблерную реализацию - встраиваемые функции(так как они не отключают оптимизацию). На x86_64 есть такая функция - _mm256_testc_si256. Но она накладывает ограничение на длину строк ровно в 32 символа. Так как средняя длина слова мала(менее 10 символов), то при использовании таблицы для слов, ограничение длины - не проблема. Но вот предложения скорее всего уже не поместятся в 32 символа. Так как _mm256_testc_si256 работает с типом __m256i, то заменим тип таблицы с <const char *, const char *> на <const __m256i *, const __m256i *>. Также данное улучшение позволит нам нормировать базу данных(все слова будут длиной 32 символа), что ускорит ее загрузку. Все строки короче будут дополнены до 32 нулями, а длинней - отсеканием.

Результаты замеров

Оптимизация №6: Повторная замена реализации хеш-функции

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

Заметим, что центральный процессор нашей установки предоставляет инструкции для получения хешей. Одна из них - ранее нам знакомый crc32. Так как зачастую аппаратная реализация быстрей программной, то используем ее, несмотря на худшую(большую) дисперсию. Также можно заметить что, теперь цикл по всем символам(вплоть до 32), можно заменить на 4 инструкции(которые обрабатываю по 8 символов за раз).

Для избежания добавления инструкции endbr64, функция будет реализована полностью на языке ассемблера.

Результаты замеров

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

Итоги главы

Из таблицы видно, что мы смогли обогнать опцию O3 в 7.26 раз.

Также стоит заметить, что некоторые наши оптимизации были невозможны для компилятора из-за строгих рамок.

Итоги

Выводы:

• У компилятора есть строгие рамки при оптимизации, за пределы которых он не выйдет

• Уход от более свободных рамок к более строгим может дать значимый прирост производительности

• Не все проблемы решаются ассемблерными оптимизациями

Но стоит заметить, что оптимизация может подразумевать разные факторы. И обычно минимизируя один из параметров оптимизации, мы увеличиваем другой. В данной работе после нормирования базы данных ее размер увеличился в 1.5 раза(с 7MB до 10MB). А напоминать, что память всегда дефицитный ресурс, не стоит.

Внешние ресурсы:

• GitHub