- Теоретическая справка
- Цель работы
- Сравнительный анализ хеш-функций
- Оптимизации хеш-таблицы
- Описание эксперимента
- Программа без оптимизаций (v.0)
- Простейшая оптимизация без ассемблера (v.1)
- Первая оптимизация с помощью intrinsic'ов (v.2)
- Вторая оптимизация с помощью встроенного ассемблера (v.3.1 и v.3.2)
- Третья оптимизация с помощью функции, написанной на ассемблере (v.4)
- Расчет коэффициента полезного действия
- Вывод
- Благодарности
- Литература
- Интернет ресурсы
Хеш-таблица - структура данных, которая хранит некоторые элементы и предоставляет возможность их быстрого добавления, удаления и поиска. Элементы хеш-таблицы называются ключами.
Хеш-функция - это функция, которая отображает множество ключей
Коллизией назовем ситуацию, когда значения хеш-функций двух разных ключей совпадают.
Общий принцип работы хеш-таблиц следующий: перед каждым запросом некоторая хеш-функция сопоставляет ключу натуральное число - хеш, по которому определяется дальнейшая обработка запроса. При хорошо подобранной хеш-функции и некоторых допущениях можно добиться того, что все запросы работают за
Для решения коллизий было решено реализовать хеш-таблицу методом цепочек, который состоит в том, что мы храним не пару (ключ, значение), а храним цепочку из ключей. В качестве цепочки было решено использовать двусвязный список. Однако, стоит отметить, что в данной работе односвязный список так же можно использовать.
Чтобы данная структура данных обрабатывала запросы за
- хеш-функция должна равномерно распределять элементы по таблице, чтобы списки получались примерно одинаковой длины
- алгоритм пересчета хеша должен для одного и того же ключа всегда выдавать один и тот же хеш
- алгоритм пересчета хеша должен работать быстро
Найти хэш-функцию с равномерным распределением, оптимизировать производительность функций хеш-таблицы и попробовать достичь большей производительности, чем -О3.
В данном разделе моей работы я искал хеш-функцию с равномерным распределением.
В моей реализации хеш-таблицы ключами являются английские слова. В хеш-таблицу загружаются английские слова из базы данных, после печатаются размеры каждого списка из хеш-таблицы. Рассчитывается средний размер каждого списка и среднеквадратичное отклонение. Так как для каждой дальнейшей хеш-функции размер хеш-таблицы и базы данных будет постоянен, то выбор функции с лучшим распределением будет зависеть от среднеквадратичного отклонения.
В качестве базы данных слов для хеш-таблицы был взят рассказ Джека Лондона "Мартин Иден". В этом рассказе 142049 слов, из которых 12258 уникальных. Так же длина слов не превышает 31. Это пригодится далее. Перед использованием текст обрабатывается следующим образом:
- Удаляются все знаки препинания и числа из текста.
- Все слова выравниваются до длины в 32 символа.
Выравнивание происходит с помощью добавления к словам '\0'. На картинке показано, как выглядит готовый датасет Data/CleanFile.txt.
За решением обратимся к книге "Введение в алгоритмы" под авторством Кормена и других [2]. В главе 11 можно найти следующую цитату:
«Хорошие результаты обычно получаются, если выбрать в качестве m простое число, далеко стоящее от степеней двойки».
m - число возможных хеш-значений, в моей реализацией m - это количество списков в хеш-таблице.
Почему Кормен и другие авторы рекомендует брать именно такое число? Для начала разберемся, почему m должно быть простым.
Пусть
Предположим, что
Теперь ответим на вопрос: "Почему число должно далеко стоять от степеней двоек?"
Рассмотрим,
Так же хотелось бы, чтобы load factor > 7. load factor - это среднее количество элементов, приходящихся на каждую ячейку таблицы. Зачем его делать таким большим, если его стараются уменьшать? Это делается для лучшей демонстративности, поэтому и мы подбирали оптимальный размер хеш-таблицы и load factor.
Отсюда можно сделать вывод, что размер хеш-таблицы должен быть равен 1531 (
uint32_t HashReturnConst(const char* key, size_t len)
{
return 0;
}Данная хеш-функция, всегда возвращает 0, и будет заполнена лишь 1 ячейка, это влияет на время работы, оно увеличится.
График:
Среднее квадратичное отклонение
uint32_t HashReturnFirstASCIICode(const char* key, size_t len)
{
return key[0];
}График:
Среднее квадратичное отклонение
uint32_t HashReturnStrlen(const char* key, size_t len)
{
return len;
}График:
Среднее квадратичное отклонение
uint32_t HashReturnSumCodes(const char* key, size_t len)
{
uint32_t control_sum = 0;
for (int i = 0; i < len; i++)
{
control_sum += key[i];
}
return control_sum;
}Рассмотрим, распределение данной хеш-функции на маленьком размере, который равен
График:
Как видно из графика, средний размер списка
График:
По графику видно, что распределение данной хеш-функции не равномерно и хуже, чем при размере 193. Так же относительное отклонение увеличилось и стало равным
Моя гипотеза, почему она не эффективна при большом размере хеш-таблицы::
Распределение вышло таким из-за того, что английские слова имеют определенную зависимость в последовательности символов в слове, то из-за этого какие-то суммы кодов встречаются часто, а другие нет, из-за этого на графике видны подобные возвышенности.
Так же данная хеш-функция имеет ограничение на диапазон возможных значений. Так как в английском слове длина слова не превышает 45 букв, то максимально возможное значение = 45 * 'z' = 45 * 122 = 5490. То есть при количестве оригинальных слов > 5490, то по индексам от 5491 и т.д. будут пустые списки. То есть данная хеш-функция плохо расширяема.
Алгоритм вычисления вычисления функции:
ror() - циклический сдвиг вправо
inline static uint32_t RORCalculate(uint32_t hash)
{
return hash >> 1 | hash << 31;
}
uint32_t HashRorFunction(const char* key, size_t len)
{
uint32_t hash = 0;
for (int i = 0; i < len; i++)
{
//Make cyclic shift right
hash = RORCalculate(hash);
hash ^= key[i];
}
return hash;
}График:
Среднее квадратичное отклонение
Рассмотрим, как godbolt транслирует код в ассемблер:
Прогонка кода через godbolt при флаге -O0:
Прогонка кода через godbolt при флаге -O1:
Компилятор g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 распознает при -O0, что
(x >> 1) | (x << 31)можно заменить на
ror eaxОднако, при -O1 программа упрощается и не вызывает функцию для подсчёта ror отдельно, в отличие от -O0. При -O2 и -O3 не происходит ничего интересного, так же стоит отметить, что при флаге -O0 и версии компилятора gcc < 7, компилятор не заменяет на ror.
Алгоритм вычисления вычисления функции:
rol() - циклический сдвиг влево
inline static uint32_t ROLCalculate(uint32_t hash)
{
return hash << 1 | hash >> 31;
}
uint32_t HashRolFunction(const char* key, size_t len)
{
uint32_t hash = 0;
for (int i = 0; i < len; i++)
{
//Make cyclic shift left
hash = ROLCalculate(hash);
hash ^= key[i];
}
return hash;
}График:
Среднее квадратичное отклонение
Про алгоритм CRC32 можно прочитать подробнее по ссылке
uint32_t HashCrc32(const char* key, size_t len)
{
uint_least32_t crc = 0xFFFFFFFF;
while (len--)
crc = (crc >> 8) ^ Crc32Table[(crc ^ *key++) & 0xFF];
return crc ^ 0xFFFFFFFF;
return 0;
}График:
Среднее квадратичное отклонение
| Хеш-функция | Среднее квадратичное отклонение |
|---|---|
| CRC32 | 2.92 |
| RolHash | 3.46 |
| RorHash | 5.85 |
| Sum of codes(size = 193) | 8.62 |
| Sum of codes(size = 1531) | 10.10 |
| First code | 68.24 |
| Strlen | 104.68 |
| ConstHash | 313.28 |
Из таблицы видно, что лучшим распределением обладает хеш-функция CRC32. В дальнейшем, будем оптимизировать хеш-таблицу с использованием CRC32.
Хорошим распределением обладает RolHash. Стоит отметить, что и SumCodes при маленьком объеме данных обладает неплохим распределением.
В данном разделе моей целью была оптимизация хеш-таблицы и попытаться обогнать компилятор.
- Создание хеш-таблицы
- Загрузка базы данных в хеш-таблицу
- Начало измерения времени в тактах
- Поиск слов из базы данных
- Конец измерения времени в тактах
- Вывод времени поиска
- Удаление хеш-таблицы
Поиск слов из базы данных проводился следующим образом: Ниже приведен псевдокод
for (i = 0; i < 3000; i++)
for (word in data_base)
Поиск слова word в хеш-таблице
В дальнейшем, каждой оптимизации присвоим номер версии программы.
Ниже приведена таблица, содержащая результаты измерений работы хеш-таблицы с ключом оптимизаций -O0.
| Номер замера | Время в тактах |
|---|---|
Среднее время работы:
Следующая оптимизация выполнит вместо нас компилятор, наша задача лишь указать ему ключ оптимизации -O3 и отключить функции дебага, такие как assert и прочее.
| Номер замера | Время в тактах |
|---|---|
| Среднее время работы в тактах | Ускорение относительно O0 (v.0) | Ускорение относительно O3 (v.1) | Ускорение относительно предыдущей реализации | |
|---|---|---|---|---|
| Наивная реализация (v.0) | 1,00 | 0,67 | 1 | |
| Реализация с O3 (v.1) | 1,49 | 1,00 | 1,49 |
В среднем, программа работает около
Далее наступает самая интересная часть работы. Будем пытаться обогнать компилятор.
Запустим программу valgrind с утилитой callgrind. Далее запустим программу KCacheGrind для просмотра полученного результата.
Из картинки видно, что большая часть нагрузок приходится на функцию strncmp. Попробуем её оптимизировать.
Заметим, что длина слов не превышает 31 символа. Значит, наши слова вмещаются в YMM-регистр. Воспользуемся этим и напишем свою strcmp:
my_strcmp
int my_strcmp(const char* string1, size_t len1, const char* string2, size_t len2)
{
if (len1 != len2) //Проверка на совпадение длин слов
{
return 0;
}
__m256i reg1 = _mm256_loadu_si256((__m256i*)string1); //Копируем string1 в YMM-регистр
__m256i reg2 = _mm256_loadu_si256((__m256i*)string2); //Копируем string2 в YMM-регистр
__m256i cmp = _mm256_cmpeq_epi8(reg1, reg2); //Сравниваем регистры
unsigned int mask = (unsigned int)_mm256_movemask_epi8(cmp);
return (mask == (unsigned int)-1); //Возвращаем результат сравнений
}Таблица измерений:
| Номер замера | Время в тактах |
|---|---|
Таблица сравнений с другими реализациями:
| Среднее время работы в тактах | Ускорение относительно O0 (v.0) | Ускорение относительно O3 (v.1) | Ускорение относительно предыдущей реализации | |
|---|---|---|---|---|
| Наивная реализация (v.0) | 1,00 | 0,67 | 1 | |
| Реализация с O3 (v.1) | 1,49 | 1,00 | 1,49 | |
| Ускорение strcmp (v.2) | 1,97 | 1,32 | 1,32 |
Мы смогли обогнать компилятор на 32%. Так же программа в среднем работает около 13 секунд.
Запускаем valgrind и наблюдаем следующее:
Видно, что теперь нужно оптимизировать функцию подсчёта хеша CRC32. Оказывается в ассемблере есть уже команда crc32. Воспользуемся встроенным ассемблером для написания функции хеширования:
HashFastCrc32(v.3.1)
uint32_t HashFastCrc32(const char* key, size_t len)
{
uint32_t crc = 0xFFFFFFFF;
asm (
".intel_syntax noprefix\n\t"
"movzx edx, BYTE PTR [%1]\n\t" //Загружаем символ в регистр edx
"test dl, dl\n\t" //Проверка на равенство символа с '\0'
"je .end_of_cycle\n\t" //Если равен, то выходим из цикла
"add %1, 1\n\t" //Иначе key += 1 и crc = (uint32_t)-1
"mov %0, -1\n\t"
".next_char:\n\t"
"add %1, 1\n\t"
"crc32 %0, dl\n\t" //Операция хеширования CRC32
"movzx edx, BYTE PTR [%1-1]\n\t" //<-+ Смотрим на следующий символ и проверяем его на равенство с '\0'
"test dl, dl\n\t" //</
"jne .next_char\n\t"
".end_of_cycle:\n\t"
"not %0\n\t" //crc = crc ^ 0xFFFFFFFF
".att_syntax\n\t"
: "=r"(crc)
: "r"(key)
: "edx"
);
return crc;
}Таблица измерений:
| Номер замера | Время в тактах |
|---|---|
Таблица сравнений с другими реализациями:
| Среднее время работы в тактах | Ускорение относительно O0 (v.0) | Ускорение относительно O3 (v.1) | Ускорение относительно предыдущей реализации | |
|---|---|---|---|---|
| Наивная реализация (v.0) | 1,00 | 0,67 | 1 | |
| Реализация с O3 (v.1) | 1,49 | 1,00 | 1,49 | |
| Ускорение strcmp (v.2) | 1,97 | 1,32 | 1,32 | |
| Ускорение strcmp и CRC32 (v.3.1) | 2,13 | 1,43 | 1,08 |
Время работы
Новый код функции(v.3.2):
global FastHashCRC32
section .text
;===============================================
;Fast assembler implementation of HashCRC32
;Entry: RDI = address of string 'key'
; RSI = len of string 'key'
;Exit: EAX = value of hash
;Dstr: No
;===============================================
FastHashCRC32:
mov eax, -1
crc32 rax, QWORD [rdi]
crc32 rax, QWORD [rdi+8]
crc32 rax, QWORD [rdi+16]
crc32 rax, QWORD [rdi+24]
not eax
ret
;===============================================
Таблица измерений:
| Номер замера | Время в тактах |
|---|---|
Таблица сравнений с другими реализациями:
| Среднее время работы в тактах | Ускорение относительно O0 (v.0) | Ускорение относительно O3 (v.1) | Ускорение относительно предыдущей реализации | |
|---|---|---|---|---|
| Наивная реализация (v.0) | 1,00 | 0,67 | 1 | |
| Реализация с O3 (v.1) | 1,49 | 1,00 | 1,49 | |
| Ускорение strcmp (v.2) | 1,97 | 1,32 | 1,32 | |
| Ускорение strcmp и CRC32 (v.3.2) | 2,38 | 1,59 | 1,21 |
Среднее время
Запустим снова valgrind и наблюдаем следующее:
Видно, что в оптимизации нуждается функция поиска в хеш-таблице. Так как мы уже используем оптимизации в виде strcmp и CRC32, а так же наш код потерял читаемость, то решено было использовать эти 3 факта и написать продвинутую функцию поиска в хеш-таблице!
Было:
int HashTableSearch(const HashTable* const hash_table, const char* key, size_t len, error_t* error)
{
assert((hash_table != nullptr) && "Pointer to \'hash_table\' is NULL!!!\n");
assert((key != nullptr) && "Pointer to \'key\' is NULL!!!\n");
assert((error != nullptr) && "Pointer to \'error\' is NULL!!!\n");
uint32_t hash = (hash_table->hash_func(key,len)) % hash_table->size;
*error = LIST_ERR_NO;
int is_found = ListSearch(hash_table->data + hash, key, len, error);
if (*error != LIST_ERR_NO)
{
ListPrintErrors(*error);
*error = HASH_ERR_LIST_INVALID;
return 0;
}
return is_found;
}Стало:
global FastHashTableSearch
section .text
;===============================================
;Fast assembler implementation of HashTableSearch
;Entry: RDI = address of hash table
; RSI = address of string 'key'
; RDX = len of string 'key'
;Exit: RAX = 1, if elem is in hash table, else 0
;Dstr: No
;===============================================
FastHashTableSearch:
;v~~~~~~~~~~Save values of registers~~~~~~~~~v
push rcx
push r8
;^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
;v~~~~~~~~~Prepare data for calculate~~~~~~~~~~v
mov r8, rsi ; R8 = address of string key
mov rcx, rdx ; RCX = len of cycle
mov eax, 0xFFFFFFFF ; EAX = (uint32_t)-1
cld
;^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
;v~~~~~~~~~~~Calculate FastHashCrc32~~~~~~~~~~~v
mov eax, -1
crc32 rax, qword [rdi] ; Hash key[0:7]
crc32 rax, qword [rdi+8] ; Hash key[8:15]
crc32 rax, qword [rdi+16] ; Hash key[16:23]
crc32 rax, qword [rdi+24] ; Hash key[24:31]
not eax ; EAX = CRC32(key)
;^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
xor edx, edx
div qword [rdi+8] ; EDX = index of list in array
lea rax, [rdx+rdx*2] ;<\
sal rax, 4 ;<-+ RAX = address of list in which the word will be searched
add rax, qword [rdi] ;</
;v~~~~~~~~~~~Search in List the key~~~~~~~~~~~~v
vmovdqu ymm0, [r8] ; Load key to YMM0
mov rsi, QWORD [rax+32] ; RSI = size of list
test rsi, rsi ;
je .IndexIsNotFound ; if (RSI == 0) go to .IndexIsNotFound
mov rdx, QWORD [rax]
xor eax, eax
.BeginOfCycle: ;<---- Begin of search cycle
cmp rсx, QWORD [rdx+32]
jne .GoToNextNode ; if (RСX != list->data[i].size) i = list->next[i]
vmovdqu ymm1, [rdx] ; Load the list->data[i].key to YMM1
vpcmpeqb ymm1, ymm1, ymm0 ; Compare YMM1 and YMM0
vpmovmskb edi, ymm1 ; EDI = mask(YMM1)
cmp edi, -1
je .EndOfFunction ; if (key == list->data[i].key) return eax
.GoToNextNode:
add rax, 1 ;<-+ i = list->next[i]
add rdx, 40 ;</
cmp rsi, rax ; if (RSI != RAX) go to next node in list
jne .BeginOfCycle ;----> End of search cycle
.IndexIsNotFound:
mov eax, -666 ; EAX = LIST_INVALID_INDEX
;^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
;v~~~~~~~~Return old values of registers~~~~~~~v
.EndOfFunction:
pop r8
pop rcx
;^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
vzeroupper
ret
;===============================================
Таблица измерений:
| Номер замера | Время в тактах |
|---|---|
Таблица сравнений с другими реализациями:
| Среднее время работы в тактах | Ускорение относительно O0 (v.0) | Ускорение относительно O3 (v.1) | Ускорение относительно предыдущей реализации | |
|---|---|---|---|---|
| Наивная реализация (v.0) | 1.00 | 0.67 | 1 | |
| Реализация с O3 (v.1) | 1,49 | 1,00 | 1,49 | |
| Ускорение strcmp (v.2) | 1,97 | 1,32 | 1,32 | |
| Ускорение strcmp и CRC32 (v.3.2) | 2,38 | 1,60 | 1,21 | |
| Ускорение HashTableSearch (v.4) | 2.92 | 1.96 | 1.23 |
Среднее время работы
КПД - это такой коэффициент, равный
| Версия | Ускорение относительно предыдущей версии | Количество ассемблерных строк | КПД |
|---|---|---|---|
| V.2 | 1,32 | 4 | 330.00 |
| V.3.2 | 1.21 | 6 | 201.67 |
| V.4 | 1.23 | 36 | 33.61 |
Из данной таблицы видно, что при росте количества ассемблерных строк, уменьшается КПД. КПД служит напоминанием для программиста, что важно смотреть не только на сколько процентов программа стала работать быстрее, но и сколько усилий было затрачено. Так же поможет послужить сигналом, что стоит остановиться в ассемблерных оптимизациях, и лучше пересмотреть алгоритмическую часть программы для ускорения.
Оптимизации с помощью ассемблера - это сильный инструмент, который может значительно ускорить программу, но в то же время ухудшает читаемость кода и переносимость его на другие устройства. К ассемблерным оптимизациям стоит подходить осторожнее, так как в погоне за скоростью можно написать много кода и получит незначительную эффективность. В таких случаях, когда ассемблерные оптимизации не дают хорошего КПД, стоит пересмотреть алгоритмическую часть программы.
Выражаю благодарность своему ментору Мухорину Матвею за ценные советы при написания программы и рекомендации по оформлению README.md. Так же выражаю отдельную благодарность моему преподавателю Дединскому Илье Рудольфовичу за оказанную помощь и знания для написания программы и README.md.
- Рэндел Э. Брайант, Дэвид Р. О'Халларон Компьютерные системы: архитектура и программирование = Computer Systems: A Programmer's Perspective / под ред. А. Н. Киселева — 2-е изд. — Москва: ДМК Пресс, 2022. - 994 с.
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн Алгоритмы: Построение и анализ = Introduction to algorithms / под ред. И. В. Красикова — 3-е изд. — Москва: Вильямс, 2013. — 1328 с.
- Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с.
- Compiler explorer - godbolt.com
- Mirror of Intel Intrinsics Guide - laurence.com/sse
- Лекции к.ф.-м.н., доц. МФТИ Северова Д.С. - ссылка