Оптимизация хэш таблицы

1. Аннотация

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

Будут предложены следующие хэш функции:

1. Константный хэш
2. Хэш, равный длине слова
3. Хэш, возвращающий ASCII код 1-го символа
4. Контрольное сумма (сумма ASCII кодов)
5. ROR-Hash
6. ROL-Hash
7. CRC32

Работа хэш функций проверяется с помощью англо-русского словаря. Для анализа наиболее медленных функций используется Callgrind profile with KCacheGrind.

2. Исследование хэш функций

Алгоритм работы хэш таблицы:

1. Читаем слово из словаря
2. Для каждого слова вычисляем хэш
3. Добавляем по вычисленному хэшу наш элемент в хэш таблицу
4. Если по данному хэшу уже есть элемент, то привязываем наш элемент к последнему в данном bucket'е

Для лучшего понимания можно посмотреть сюда:

Рисунок 1.

2.1. Константный хэш

Хэш всегда возвращает 1.

Рисунок 2.1.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Масштаб по оси x увеличен в 30 раз, чтобы лучше было видно пик.

Рисунок 2.1.2. Распределение.

2.2. Хэш, равный длине слова

Хэш функция возвращает длину элемента (слова).

Рисунок 2.2.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Масштаб по оси x увеличен в 30 раз, чтобы лучше было видно пик.

Рисунок 2.2.2. Распределение.

2.3. Хэш, возвращающий ASCII код 1-го символа

Хэш функция возвращает ASCII код 1-го символа.

Рисунок 2.3.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Масштаб по оси x увеличен в 30 раз, чтобы лучше было видно пик.

Рисунок 2.3.2. Распределение.

2.4. Контрольное сумма

Хэш функция возвращает сумму ASCII кодов всех символов слова.

Рисунок 2.4.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Рисунок 2.4.2. Распределение.

2.5. ROR хэш

Hash[0] = 0

Hash[i + 1] = ror Hash[i] xor String[i]

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

Рисунок 2.5.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Рисунок 2.5.2. Распределение.

Для наглядности размер хэш таблицы уменьшин в 10 раз (для более плотного заполнения bucket'ов).

2.6. ROL хэш

Hash[0] = 0

Hash[i + 1] = rol Hash[i] xor String[i]

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

Рисунок 2.6.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Рисунок 2.6.2. Распределение.

Для наглядности размер хэш таблицы уменьшин в 10 раз (для более плотного заполнения bucket'ов).

2.7. CRC32

Рисунок 2.7.1. Зависимость количества элементов в bucket'е от номера buсket'а.

Рисунок 2.7.2. Распределение.

Для наглядности размер хэш таблицы уменьшин в 10 раз (для более плотного заполнения bucket'ов).

2.8. Выбор наиболее оптимальной хэш функции

Как видно из графиков, CRC32 является наиболее эффективной хэш функцией. В ней наименьшее количество пустых bucket'ов, наиболее равномерное распределение элементов по bucket'ам и размер bucket'а составляет не больше 9-ти элементов. Гистограмма наиболее похожа на Гауссову кривую.

Если же смотреть на остальные хэш функции, то можно сказать, что первые четыре хэш функции имеют множество пустых bucket'ов, к тому же у них много высоких пиков, они совсем не подходят для эффективного поиска в хэш таблице. 5-я и 6-я хэш функции уже получше, в них значительно меньше пустых bucket'ов, однако в ROL хэше имееются bucket'ы размера больше 9, а распределение элеметов не такое равномерное как у CRC32 (у ROR хэша такие же проблемы, только более усугбленные).

3. Анализ времени работы функций

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

Рисунок 3. Время работы функций.

Теперь видно, что наиболее долгие по времени работы функции - это ListSearch(который содержит в себе __strcmp_avx2) и HashFunction. Их мы и будем оптимизировать.

4. Оптимизация

Измерим время работы программы без оптимизаций c -O1 и с -O3 для дальнейших сравнений.

-O1, с	-O3, c
4.501829	4.136374

Таблица 1.

4.1. __strcmp_avx2

В первую очередь нам надо соптимизировать сравнение строк. Для этого есть хорошее решение - мы можем использовать AVX инструкции!

А теперь поподробнее. Заметим, что наши слова не превышают в размере 32-х байт. Тогда мы можем хранить ключевые слова в переменных типа __m256i. Теперь сравнение двух строк превращается в сравнение двух переменных __m256i, которое выполняется всего лишь одной инструкцией _mm256_cmpeq_epi8.

  __m256i key = _mm256_loadu_si256((const __m256i*)pair->key);
  __m256i data_key = _mm256_setzero_si256();

  for (size_t i = 0; i < list->size; ++i) {
    data_key = _mm256_loadu_si256((const __m256i*)list->data[i].key);
    int result = _mm256_movemask_epi8(_mm256_cmpeq_epi8(data_key, key));

    if (result == -1) {
      pair->value = list->data[i].value;
      return true;
    }
  }
}

Измерим время работы после данной оптимизации.

-O1, с	-O3, c
4.501829	4.136374
3.899324	3.763011

Таблица 2.

Таким образом, мы получили ускорение при -O1 на 15% и при -O3 на 10%.

4.2. ListSearch

Давайте поймем, как работает функция ListSearch. Она получает на вход bucket и элемент, который в этом bucket'е нужно найти. Далее она проходится по всем элементам и сравнивает их с помощью встроенного strcmp, пока не найдет запрашиваемый элемент. Таким образом, чтобы оптимизировать ListSearch, мы можем переписать ее на ассемблере, используя векторные инструкции.

_ListSearch:  mov rax, [rdi]     
              mov rcx, [rdi + 8] 

              vmovdqu ymm0, [rsi]

loop_start:   or rcx, rcx
              jz exit_false

              vmovdqu ymm1, [rax]
              vpcmpeqb ymm2, ymm1, ymm0
              vpmovmskb rdx, ymm2

              cmp rdx, -1
              je exit_true

              add rax, 16
              dec rcx
              jmp loop_start

exit_false:   xor rax, rax
              ret

exit_true:    mov rdx, [rsi + 8]
              mov [rax + 8], rdx
              mov rax, 1
              ret

Измерим время работы после данной оптимизации.

-O1, с	-O3, c
3.899324	3.763011
3.695025	3.585601

Таблица 3.

Таким образом, мы получили замедление при -O1 на 6% и при -O3 на 5%.

4.3. HashFunction

Теперь нам нужно оптимизировать CRC32. Для этого в ассемблере существует встроенная инструкция по вычислению CRC32.

size_t HashFunction(Pair* pair) {
  size_t result = 0;

  __asm__ (
    ".intel_syntax noprefix \n\t"
    "xor rax, rax           \n\t"
    "mov rdx, [rdi]         \n\t"
    "loop_start:            \n\t"
    "mov cl, [rdx]          \n\t"
    "or cl, cl              \n\t"
    "jz loop_end            \n\t"
    "crc32 rax, cl          \n\t"
    "inc rdx                \n\t"
    "jmp loop_start         \n\t"
    "loop_end:              \n\t"
    ".att_syntax            \n\t"
    : "=a"(result)
    :
    : "rcx", "rdx", "rdi"
  );

  return result;
}

Измерим время работы после данной оптимизации.

-O1, с	-O3, c
3.695025	3.585601
3.311672	3.273021

Таблица 4.

Таким образом, мы получили ускорение при -O1 на 12% и при -O3 на 10%.

5. Заключение

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

	-O1, с	-O3, c
Без оптимизаций	4.501829	4.036374
AVX инструкции	3.899324	3.673011
ListSearch + AVX инструкции	3.695025	3.585601
ListSearch + AVX инструкции + СRC32 оптимизированный	3.311672	3.273021

Таблица 5.

В итоге мне удалось повысить производительность хэш таблицы на 36% (с -O1) и на 23% (с -O3).

Осталось посчитать коэффициент ded32 🙀🙀🙀:

boost_coefficient / #asm_lines * 1000($ в квартал) = 1,96 / 37 * 1000 = 53,1 (-O0)

boost_coefficient / #asm_lines * 1000($ в квартал) = 1,21 / 37 * 1000 = 32,7 (-O3)