Тесты своей реализации ассоциативных массивов vs хеш-таблица

Приветствую, читатель. Я являюсь автором языка программирования Shar. В стандартном модуле Shar есть несколько реализаций ассоциативных массивов и при написании данного модуля я подумал: "А какую структуру данных для реализации ассоциативных массивов мне выбрать?". Являясь любителем слушать различные конференции по программированию, я периодически натыкаюсь на выступления людей, принимающих участие в разработке популярных языков программирования. На основании таких выступлений, у меня сложилось субъективное восприятие того, что в большинстве случаев для реализации ассоциативных массивов используется хеш-таблица. Хеш таблица действительно является очень хорошим выбором, но тогда почему я начал задумываться о выборе подходящей структуры данных? А причина в том, что в Shar изменение одного объекта не может изменить другой объект. Поясню на примере, вот код на Python:

a = [1, 2, 3, 4, 5]
b = a
c = b
a[1] = 1
print(a, '\n', b, '\n', c, '\n', sep='')

результат:
[1, 1, 3, 4, 5]
[1, 1, 3, 4, 5]
[1, 1, 3, 4, 5]

а вот похожий код на Shar:

def main()
    var a Array = [1, 2, 3, 4, 5]
    var b Array = a
    var c Array = b
    a.setItem(1, 1)
    a.println()
    b.println()
    c.println()

результат:
[1, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

До момента записи в a, a b c указывают на один и тот же объект, но в момент записи, из-за того, что на объект указывает не только a, то для a создаётся копия объекта. Такое поведение достигается за счёт того, что в Shar для управления памятью используется подсчёт ссылок (reference counting) и если счётчик равен единице, то при попытке записи в объект - запись происходит, иначе создаётся полная, либо частичная копия объекта, и запись происходит в копию. Поясню что значит “частичная копия”, если объект, копия которого создаётся, содержит в себе другие объекты содержащие в себе счётчик ссылок (не у всех он есть, например у строк - есть, а у чисел - нет), то эти “внутренние” объекты не копируются, а их счётчик ссылок просто увеличивается на единицу. Такой подход позволяет нескольким объектам иметь общие данные не копируя их (до момента изменения данных одним из объектов). Но такой подход плохо подходит для хеш-таблицы,так как в ней все данные, кроме ключей и значений, будут полностью скопированы. Так же бывают ситуации, когда нужно создать ассоциативный массив на основе другого массива, но при этом нельзя менять исходный массив. В такой ситуации также придётся полностью копировать структуру хеш-таблицы. Очень часто я размышляю о различных алгоритмах и структурах данных, и в период написания стандартного модуля у меня в голове сидела идея одной структуры данных, которая хорошо поддавалась частичному копированию.

Есть такая структура данных под названием “префиксное дерево” (trie), скорость поиска в такой структуре не зависит от количества элементов в ней, а лишь от размера ключа, что делает её эффективной на большом количестве данных, но у неё есть и недостатки – большое количество потребляемой памяти, а так же сильная фрагментация данных. На малом же количестве данных, большинство структур данных и алгоритмов по скорости не особо сильно отличаются, поэтому можно совместить префиксное дерево с какой либо структурой данных, чтобы нивелировать недостатки префиксного дерева. В какой структуре данных нет сильной фрагментации, а потребление памяти минимально? В массиве! Если отсортировать массив, то в нём для поиска данных можно использовать алгоритм бинарного поиска. Я решил совместить префиксное дерево и массив с бинарным поиском и вот как я придумал это сделать: для каждого ключа высчитывается 24-битный хеш, структура же представляет собой дерево, в корне которого находится отсортированный массив из первых 8-ми бит хеша каждого ключа (без повторов), а так же указатель на ветвь в которой лежат данные ключей, у которых хеш имеет соответствующие 8 бит, а в ветвях находится отсортированный массив из оставшихся 16-ти бит хеша каждого ключа, а так же указатель на массив в котором лежат ключи и значения с соответствующим хешем. Поиск происходит следующим образом:

• вычисляется хеш ключа

• если в массиве корня менее 256-ти элементов, то первые 8-бит хеша ключа ищутся с помощью бинарного поиска

• если в массиве корня 256 элементов, то искать ничего ненужно, а нужная ветвь имеет в массиве индекс равный числу хранящемуся в первых 8-ми битах хеша

• переход на ветвь которая соответствует найденной части хэша

• если в массиве ветви менее 65536-ти элементов, то последние 16-бит хеша ключа ищутся с помощью бинарного поиска

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

• переход на массив который соответствует найденной части хэша

• линейный поиск по массиву из ключей и значений

Я решил добавить данную структуру в стандартный модуль, но в заметках себе пометил, чтобы я в будущем реализовал хеш-таблицу и сравнил её со своей структурой по различным критериям. Прошло немного времени и я начал думать о том, что бинарный поиск – это цикл, а использование циклов негативно сказывается на производительности, так же в случае с большим количеством данных, массив в ветке может иметь приличное количество частей хеша ключей, а бинарный поиск по большому массиву – плохая идея. Бинарный поиск можно заменить на линейный поиск с использованием SIMD инструкций процессора, с одной стороны это избавит алгоритм поиска от циклов, но с другой стороны придётся выделять память частями по 256-бит, что приведёт к увеличенному потреблению памяти, а так же к увеличению количества промахов кеша, что негативно скажется на производительности. Что бы не искать по большим массивам в ветках, можно увеличить количество ветвей и разбивать хеш не на 8 и 16 бит, а трижды по 8 бит, что опять же приведёт и к увеличенному потреблению памяти, и к увеличению количества промахов кеша. И вот не понятно, это улучшение или ухудшение? Так же когда в корне и ветвях, массивы заполняются полностью, хранить части хешей больше незачем. Поэтому я решил, что раз я всё равно буду реализовывать хеш-таблицу, и делать сравнение с мои алгоритмом, то реализую я и структуру данных с указанным улучшениями (ухудшениями) и протестирую её.

И вот пришло время заняться данным вопросом, все структуры реализованы, тесты написаны, результаты тестов получены. Тесты написаны в виде интерактивного shell`а в котором пользователь вводит команды, такой способ, а так же некоторый код, нужны лишь для того, чтобы компилятор не мог понять, что по факту, данный код ничего нужного не делает. Для каждого теста программа запускалась заново. Каждый тест производился трижды и если все три теста давали близкий результат, то брался средний из них, если хотя бы один результат сильно отличался, то тест запускался ещё несколько раз и вычислялось средне арифметическое значение всех результатов. Также тесты были написаны на Go, это не в коем случае не сравнение Go и Shar, а только лишь любопытство. Ссылка на исходники тестов будет в конце статьи, но сразу скажу что поскольку в данный момент в Shar нет способа получить время с точностью до микросекунд, для этого использовался “костыль”. Для сокращения я буду помечать свой алгоритм как MO (my old), свой изменённый алгоритм MN (my new), хеш-таблицу (HT). Перед результатами каждого теста, будет находится небольшое описание и список команд которые передавались тесту. Данные для тестов загружались из файла (~600 Мб) который был создан с помощью генератора, исходники которого будут лежать вместе с исходниками тестов. Характеристики ПК на котором производились тесты: CPU - AMD Ryzen 2200G (не разогнанный), память – двухканальная 2933 Mhz 16 Gb. Результаты тестов (от наименее интересных к наиболее):

Добавление и удаление:
В командах указывается количество пар ключ/значение в ассоциативном массиве, а тест создаёт несколько ассоциативных массивов с указанным количеством пар. Суммарное количество пар во всех массивах всегда идентично, меняется лишь количество ассоциативных массивов. Затем происходило удаление каждой пары из каждого ассоциативного массива. Один из тестов длился более 20-ти минут, поэтому его я запускал лишь один раз. MN на небольших количествах пар имеет оверхэд по памяти, и не вмещается в мои 16 Gb, поэтому указаны значения только для большого количества пар.

Результаты добавления:

Результаты удаления:

Потребление памяти:
Тест аналогичен предыдущему, но данные из ассоциативных массивов не удаляются. Как и в предыдущем тесте MN на малом количестве пар не умещается в память. Замер производился утилитой htop. Во время замера ненужные данные были освобождены, а в Go реализации был явным образом запущен сборщик мусора и замер производился после окончания его работы.

Результаты:

Скорость поиска отсутствующих в массиве данных:
Это как раз тот тест, данные различных запусков которого сильно отличались (например один запуск длится 2.1 сек., а повторный 3.4), поэтому здесь в основ усреднённые данные. Тест создаёт один ассоциативный массив с указанным количеством пар, а в нём происходит поиск данных, количество данных не зависит от размера ассоциативного массива.

Результаты:

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

Результаты:

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

Ссылки:
исходники тестов и генератора данных
репозитории связанные с Shar