Ассоциативный хеш массив это
В PHP есть только один тип данных для массивов — Array. Его уникальность состоит в том, что с одной стороны он работает как обычный массив, а с другой — как ассоциативный. Зависит от того, как его используют.
Поначалу такой подход может подкупить своей кажущейся простотой, особенно тех, кто не имел дела с другими языками. Но чем дальше в код, тем больше проблем он приносит.
Самый простой пример — JSON. В JSON массив и ассоциативный массив — разные сущности:
Ассоциативный массив
Массив
Если преобразовать JSON в структуру на PHP, то эта информация теряется:
Если мы не знаем структуру JSON, то у нас нет простого способа понять, что перед нами — массив или ассоциативный массив. В интернете с подобным сталкиваются постоянно и предлагают такой способ, как анализ ключей. Если они все числовые, то считаем, что массив, иначе — ассоциативный массив.
Конвертация из массива в JSON сопряжена с такими же проблемами. Как понять, во что конвертировать переданный массив?
Другая проблема заключается в том, что достаточно легко ошибиться с типом массива и начать его использовать не по назначению:
Первое удивление — код работает! Теперь попробуйте догадаться, что находится внутри $data .
Из этого вывода должно быть понятно, что индексированных массивов в PHP нет. Есть упорядоченные ассоциативные массивы, с операцией [] = : добавить элемент с автоматическим присвоением ключа.
Но самое неудобное — функции которые могут сохранять, а могут не сохранять ключи. Обычно в таких функциях есть дополнительный параметр флаг preserve_keys , который меняет описанное поведение.
array array_reverse ( array $array [, bool $preserve_keys = FALSE ] )
Если preserve_keys установлен в TRUE, то числовые ключи будут сохранены. Нечисловые ключи не подвержены этой опции и всегда сохраняются.
array_unique ( array $array [, int $sort_flags = SORT_STRING ] )
Коллизии
Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей — бесконечно. В свою очередь, результат работы хеш-функции — строка фиксированной длины, а значит множество всех выходных значений — конечно.
Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (когда для разных значений получается один и тот же хеш). Такую ситуацию принято называть коллизией. Способов разрешения коллизий несколько, и каждому из них соответствует свой тип хеш-таблицы.
Участники исследования
Judy (или Judy Array) – структура, придуманная Дугласом Баскинсом, реализующая упорядоченный ассоциативный массив. Реализация написана на C и крайне сложна. Автор попытался учесть современную архитектуру и использовать кеши процессора по максимуму.
Judy представляет из себя дерево, а не хеш-таблицу. И не просто дерево, а так называемое префиксное дерево. Для нас, потребителей, это означает, что, используя Judy, мы получаем сжатие ключей и возможность бежать по элементам в порядке возрастания или убывания ключа.
Judy предоставляет несколько вариаций «ключ/значение»:
Вариация | Ключ | Значение |
---|---|---|
Judy1 | uint64_t | bit |
JudyL | uint64_t | uint64_t |
JudySL | null-terminated string | uint64_t |
JudyHS | array of bytes | uint64_t |
Judy1 удобно использовать для больших разреженных bitmap‘ов. JudyL является базовым типом, который мы в C-сервисах Badoo чаще всего и используем. JudySL, как видно, удобно использовать для строк, а JudyHL – просто для какого-то набора байт.
std::unordered_map
unordered_map реализован на C++ в виде шаблона, так что в качестве ключа и значения может выступать всё что угодно. В случае использования нестандартных типов вам придётся определить функцию для хеширования этих типов.
Это именно хеш-таблица, так что обход ключей по возрастанию или убыванию недоступен.
google::sparse_hash_map
Как видно из названия, sparse hash был разработан в Google и заявляет минимальный оверхед в размере всего два бита на значение. Он также реализован на C++ и сделан в виде шаблона (и это, на мой взгляд, несомненное преимущество реализаций на C++).
Кроме всего прочего, sparse hash умеет сохранять своё состояние на диск и загружаться с него.
google::dense_hash_map
Кроме sparse hash, Google сделала вариант под названием dense hash. Скорость у него (а особенно скорость get‘а) заметно выше, но за это приходится платить большим расходом памяти. Также, из-за того, что внутри у dense_hash_map плоские массивы, периодически требуется дорогое перестроение. Кстати, о таких проблемах и нюансах хеш-таблиц отлично рассказал Константин Осипов в своём докладе на HighLoad++. Рекомендую к изучению.
В случае если количество данных, которые вы храните в ассоциативном массиве невелико и его размер не будет сильно меняться, dense hash должен подойти вам лучше всего.
Аналогично sparse hash dense hash является хеш-таблицей и шаблоном. То есть, повторюсь, никакого прохождения по ключам в порядке возрастания, но при этом возможность использовать любые типы в качестве ключей и значений.
Также аналогично своему собрату sparse_hash_map dense_hash_map умеет сохранять своё состояние на диск.
spp::sparse_hash_map
И, наконец, последний претендент от одного из разработчиков google sparse hash. Автор взял за основу sparse hash и переосмыслил его, добившись минимального оверхеда в один бит на запись.
Всё то же самое: хеш-таблица и шаблон. Реализация на C++.
Претенденты представлены – пришло время проверить, на что они способны.
За кулисами
Рассмотрим процесс добавления нового значения в ассоциативный массив. Программист пишет:
Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:
Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже — там, где мы поговорим про коллизии.
Теперь посмотрим на чтение:
- Интерпретатор хеширует ключ. Результатом хеширования становится число.
- Это число используется как индекс внутреннего массива для поиска значения.
- Если индекс существует, то извлекается значение, которое находилось внутри, и возвращается наружу.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. В JavaScript — это Object, в других языках:
- Ruby — Hash
- Lua — Table
- Python — Dictionary
- Elixir/Java — Map
Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров. Фактически все предыдущие уроки по объектам в JavaScript были посвящены тому, как использовать объекты в качестве ассоциативных массивов.
Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память "как есть". У него нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные в памяти, она включает в себя логику.
Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри. Эта информация крайне важна для разработчиков, которые хотят по настоящему разбираться в том, что они делают. Она снимает "магичность" с происходящего внутри языка и дает понимание цены, которую приходится платить за удобство использования объектов.
Итак, что примерно происходит, когда мы выполняем код:
За кулисами
Рассмотрим процесс добавления нового значения в ассоциативный массив (напомню, в JavaScript представлен типом данных Object). Программист пишет:
Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:
Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже, там где мы поговорим про коллизии.
Теперь посмотрим на чтение:
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
Краткие выводы и заключительные слова
Наши тесты показали хороший потенциал spp в качестве замены Judy. spp оказался быстрее на рандомных get‘ах, а его оверхед по памяти не слишком велик.
Мы сделали простенькую обёртку над C++ для C и в ближайшее время попробуем spp в одном из своих высоконагруженных сервисов.
Ну, и в качестве совсем философского заключения скажу, что у каждой из рассмотренных нами реализаций есть свои плюсы и минусы и выбирать следует, основываясь на решаемой задаче. Понимание их внутреннего устройства поможет вам сопоставить задачу и решение, и это понимание зачастую отличает простого инженера от продвинутого.
Некоторое время назад я сходил на собеседование в одну довольно большую и уважаемую компанию. Собеседование прошло хорошо и понравилось как мне, так и, надеюсь, людям его проводившим. Но на следующий день, в процессе разбора полетов, я обнаружил, что в ходе собеседования ответ на как минимум один вопрос был неверен.
Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?
Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!
На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.
Причиной неверного ответа было то, что я не удосужился досконально изучить те структуры, которые лежат в основе работы с коллекциями моего любимого языка. Правда, по результатам опроса нескольких знакомых разработчиков, оказалось что это не только моя проблема, очень многие вообще не задумываются, как работают коллекции в их любимых ЯП. А ведь используем мы их каждый день и не по разу. Так родилась идея этой статьи.
1. Array — он же индексированный массив.
Array — это коллекция фиксированного размера, состоящая из элементов одинакового типа.
- get_element_at(i): сложность O(1)
- set_element_at(i, value): сложность O(1)
Почему время доступа к элементу по индексу постоянно? Массив состоит из элементов одного типа, имеет фиксированный размер и располагается в непрерывной области памяти => чтобы получить j-й элемент массива, нам достаточно взять указатель на начало массива и прибавить к нему размер элемента умноженный на его индекс. Результат этого несложного вычисления будет указывать как раз на искомый элемент массива.
*aj = beginPointer + elementSize*j-1
2. List (список).
List — это список элементов произвольного типа переменной длины (то есть мы можем в любой момент добавить элемент в список или удалить его). Список позволяет перебирать элементы, получать элементы по индексу, а так же добавлять и удалять элементы. Реализации у List возможны разные, основные — это (Single/Bidirectional) Linked List и Vector. Классический List предоставляет возможность работы с ним напрямую и через итератор, интерфейсы обоих классов рассмотрим ниже.
- prepend(item): Добавить элемент в начало списка.
- append(item): Добавить элемент в конец списка.
- insert_after(List Iterator, item): Добавить элемент после текущего.
- remove_firts(): Удалить первый элемент.
- remove_after(List Iterator): Удалить элемент после текущего.
- is_empty(): Пуст ли List.
- get_size(): Возвращает размер списка.
- get_nth(n): Вернуть n-й элемент.
- set_nth(n, value): Задать значение n-му элементу.
- get_value(): получить значение текущего элемента.
- set_value(): задать значение текущему элементу.
- move_next(): переместиться к следующему элементу.
- equal(List Iterator): проверяет — ссылается ли другой итератор на тот же элемент списка.
Перейдем к реализациям списка.
2.1 Single Linked List
Однонаправленный связный список (односвязный список) представляет из себя цепочку контейнеров. Каждый контейнер содержит внутри себя ссылку на элемент и ссылку на следующий контейнер, таким образом, мы всегда можем переместиться по односвязному списку вперед и всегда можем получить значение текущего элемента. Контейнеры могут располагаться в памяти как им угодно => добавление в односвязный список нового элемента тривиально.
- prepend: O(1)
- insert_after: O(1)
- remove_first/remove_after: O(1)
- get_nth/set_nth: O(N)
Bidirectional Linked List мы подробно рассматривать не будем, вся разница между ним и Single Linked List заключается в том, что в контейнерах есть ссылка не только на следующий, но и на предыдущий контейнер, что позволяет перемещаться по списку не только вперед, но и назад.
2.2 Vector
Vector — это реализация List через расширение индексированного массива.
- prepend: O(N)
- append: Amort.O(1)
- insert_after: O(N)
- remove_first/remove_after: O(1)
- get_nth/set_nth: O(1)
Очевидно, что главное преимущество Vector'а — быстрый доступ к элементам по индексу, унаследовано им от обычного индексированного массива. Итерировать Vector так же достаточно просто, достаточно увеличивать некий счетчик на единицу и осуществлять доступ по индексу. Но за скорость доступа к элементам приходиться платить временем их добавления. Для того чтобы вставить элемент в середину Vector'a (insert-after) необходимо скопировать все элементы между текущим положением итератора и концом массива, как следствие время доступа в среднем O(N). То же и с удалением элемента в середине массива, и с добавлением элемента в начало массива. Добавление элемента в конец массива при этом может быть выполнено за O(1), но может и не быть — если опять таки потребуется копирование массива в новый, потому говорится, что добавление элемента в конец Vector'а происходит за Amort. O(1).
3. Ассоциативный массив(Словарь/Map)
Коллекция пар ключ=>значение. Элементы (значения) могут быть любого типа, ключи обычно только строки/целые числа, но в некоторых реализация диапазон объектов, которые могут быть использованы в качестве ключа, может быть шире. Размер ассоциативного массива можно изменять путем добавления/удаления элементов.
- add(key, value) — добавить элемент
- reassign(key, value) — заменить элемент
- delete(key) — удалить элемент
- lookup(key) — найти элемент
3.1 Hash Table
Как можно догадаться из названия, тут используются хэши. Механика работы Hash Table следующая: в основе лежит все тот же индексированный массив, в котором индексом работает значение хэша от ключа, а значением — ссылка на объект, содержащий ключ и хранимый элемент (bucket). При добавлении элемента — хэш функция вычисляет хэш от ключа и сохраняет ссылку на добавляемый элемент в ячейку массива с соответствующим индексом. Для получения доступа к элементу мы опять таки берем хэш от ключа и, работая так же как с обычным массивом получаем ссылку на элемент.
- Если хэш от ключа равен например 1928132371827612 — это ведь будет означать, что нам надо иметь массив соответствующего размера? А если у нас в нем всего 2 элемента?
- А если у нас хэши от двух разных ключей совпадут?
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда. Обратная сторона такого поведения хэш функции — возможность коллизий. Коллизии на самом деле характерны для Hash Table, и существует два метода их разрешения:
Chaining:
Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
Open addressing:
В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.
- add: Amort.O(1)/O(N)
- reasign: Amort.O(1)/O(N)
- delete: Amort.O(1)/O(N)
- lookup: Amort.O(1)/O(N)
3.2 Binary Tree
На самом деле не просто Binary Tree, а Self-balancing Binary Tree. Причем следует отметить, что существует несколько различных деревьев, которые могут быть использованы для реализации Ассоциативного массива: red-black tree, AVL-tree и т.д. Мы не будем рассматривать каждое из этих деревьев в деталях, так как это возможно тема еще одной, отдельной статьи, а может и нескольких (если изучать деревья особо тщательно). Опишем только общие принципы.
Определение: двоичное дерево — древовидная структура данных в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. В случае, если у узла нет наследников — он называется листовым узлом.
- add: Amort.O(lgN)
- reasign: Amort.O(lgN)
- delete: Amort.O(lgN)
- lookup: Amort.O(lgN)
4. Множество (Set).
Сравнительные характеристики структур данных:
Структуры данных в различных языках программирования:
Ссылки:
Так же автор заглянул в исходники PHP и почитал доку по STL.
Upd. Да, в питоне есть обычный индексированный массив (array.array). Спасибо enchantner. С поправкой, тип не обязательно числовой, тип можно указывать.
Upd. Сделано много исправлений по тексту. idemura, zibada, tzlom, SiGMan, freeOne, Slaffko, korvindest, Laplace, enchantner спасибо за правки!
Upd.
Из комментариев zibada:
Да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).
Нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
— в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках);
— в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках);
— в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне.
А вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
Что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
Ассоциативный массив — абстрактный тип данных (АТД), с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. Например, в других языках это:
- Ruby — Hash
- Lua — Table
- Python — Dictionary
- JavaScript — Object
- Elixir/Java — Map
Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров.
Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память "как есть". У него нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные в памяти, она включает в себя логику.
Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри, будет много терминов. Эта информация крайне важна для любых разработчиков. Она снимает магичность с происходящего, даёт понимание эффективности, ценой которой приходится платить за удобства.
Исходный код и железо
Исходный код бенчмарков я выложил на github. При желании вы можете повторить мои тесты или расширить их.
Я же проводил тестирование на своём домашнем десктопе:
- Ubuntu 17.04
- Linux 4.10.0
- Intel® Core(TM) i7-6700K CPU @ 4.00GHz
- 32 GiB DDR4 memory
- GCC 6.3.0
- Флаги компилятора: -std=c++11 -O3 -ffast-math
Хеширование
Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).
Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).
С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 не что иное, как хеш, полученный в результате хеширования данных коммита.
После того, как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:
Хеширование
Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).
Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).
Самый простой способ хешировать данные на PHP — использовать функцию crc32 :
С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 не что иное, как хеш, полученный в результате хеширования данных коммита.
После того как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:
Результаты
Ниже представлены результаты теста по рандомному поиску среди десяти миллионов элементов. Два параметра, которые меня больше всего интересуют, – время выполнения теста и максимальная потреблённая память (RSS процесса в пике).
В качестве ключа я использовал 32-битное целое, а в качестве значения – указатель (64 бита). Именно такие размеры ключей и значений мы чаще всего используем.
Я не стал показывать результаты других тестов, которые представлены в репозитории, так как меня больше всего интересовали именно рандомный get и потребляемая память.
Самым быстрым ассоциативным массивом оказался dense hash от Google. Следом идёт spp, и затем – std::unordered_map.
Однако если посмотреть на память, видно, что dense_hash_map потребляет её больше всех других реализаций. Собственно, именно это сказано в документации. Более того, если бы у нас в тесте были конкурирующие чтение и запись, мы бы, скорее всего, столкнулись со stop-the-world-перестроением. Таким образом, в приложениях, где важна отзывчивость и много записей, dense hash использовать нельзя.
Также я посмотрел на альтернативные реализации хеш-функций. Но, как оказалось, стандартная std::hash быстрее.
Коллега случайно заметил, что в случае 32- или 64-битных ключей std::hash по сути просто identity. То есть на входе и выходе – одно и то же число, или, другими словами, функция ничего не делает. хxhash и t1ha же честно считают хеш.
В плане производительности jemalloc полезен. Практически все реализации становятся быстрее.
Однако по потреблению памяти jemalloc не настолько хорош.
Коллизии
Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей — бесконечно. В свою очередь, результат любой хеш-функции — строка фиксированной длины, а значит множество всех выходных значений — конечно.
Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (когда для разных значений получается один и тот же хеш). Такую ситуацию принято называть коллизией. Способов разрешения коллизий несколько, и каждому из них соответствует свой тип хеш-таблицы.
На что смотрим?
Мир ассоциативных массивов, конечно, не чёрно-белый: у каждой реализации есть как преимущества, так и недостатки.
Разные реализации могут отличаться не только производительностью, но и набором предоставляемых функций. К примеру, какие-то реализации позволяют обходить элементы в порядке возрастания или убывания ключа, а какие-то – нет. И это ограничение связано с внутренней архитектурой, а не прихотями автора.
Да и банальная производительность может сильно отличаться в зависимости от того, каким образом вы используете ассоциативный массив: в основном пишете в него или читаете, читаете ключи в произвольном порядке или последовательно.
Прошли времена, когда О-нотации Кнута было достаточно для сравнения двух алгоритмов. Реальный мир гораздо сложнее. Современное железо, на котором работают наши программы, имеет многоуровневую память, доступ к разным уровням которой сильно отличается, и учёт этого может ускорить алгоритм в разы или на столько же его замедлить.
Немаловажным критерием является и вопрос потребления памяти: какой оверхед у выбранной реализации по сравнению с теоретическим минимумом (размер ключа + размер значения, умноженные на количество элементов) и допустим ли такой оверхед в нашей программе?
Паузы, максимальная задержка (latency) и отзывчивость тоже играют важную роль. Некоторые реализации ассоциативных массивов требуют одномоментного дорогостоящего перестроения своих внутренних структур при добавлении элемента, которому не повезло, а другие – «размазывают» эти задержки во времени.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
Кадр из Top Gear: USA (серия 2)
В своих самых высоконагруженных сервисах мы в Badoo используем язык C и иногда C++. Зачастую эти сервисы хранят в памяти сотни гигабайт данных и обрабатывают сотни тысяч запросов в секунду. И нам важно использовать не только подходящие алгоритмы и структуры данных, но и производительные их реализации.
Практически с самого начала в качестве реализации ассоциативных массивов мы использовали Judy. У неё есть C-интерфейс и множество преимуществ. Мы даже используем обёртку для PHP, так как в версиях PHP до 7.0 Judy сильно выигрывает по количеству потребляемой памяти по сравнению со встроенными мапами.
Однако время идёт, и с момента последнего релиза Judy прошло немало лет – самое время посмотреть на альтернативы.
Меня зовут Марко, я – системный программист Badoo в команде «Платформа». Мы с коллегами провели небольшое исследование в поисках альтернатив Judy, сделали выводы и решили поделиться ими с вами.
Ещё два фактора
Но сначала замечу, что на производительность и потребление памяти будут влиять ещё две вещи.
Хеш-функция
Все участники нашего исследования, являющиеся хеш-таблицами, используют хеш-функции.
У хеш-функций довольно много свойств, каждое из которых может быть более или менее важно в зависимости от области. Например, в криптографии важно, чтобы минимальное изменение входящих данных приводило к как можно большему изменению в результате.
Но нас больше всего интересует скорость. Производительность хеш-функций может сильно отличаться, и скорость часто зависит от того количества данных, которое им «скармливается». Когда на вход в хеш-функцию подаётся длинная цепочка байт, может быть целесообразно применение SIMD-инструкций для более эффективного использования возможностей современных процессоров.
В дополнение к стандартной хеш-функции из C++ я посмотрю, как справятся xxhash и t1ha.
Аллокация памяти
Второй фактор, который обязательно повлияет на наши результаты, — аллокатор памяти. От него напрямую зависят и скорость работы, и количество потребляемой памяти. Стандартный аллокатор из libc – это jack of all trades. Он хорош для всего, но ни для чего не идеален.
В качестве альтернативы я рассмотрю jemalloc. Несмотря на то, что в тесте мы не воспользуемся одним из его основных преимуществ – работой с многопоточностью – я ожидаю более быструю работу с этим аллокатором.
Ассоциативный массив
Если вы знаете, что такое ассоциативный массив, дерево и хеш-таблица, этот раздел можете смело пропускать. Для остальных – небольшое введение в тему.
Ассоциативный массив – это абстрактный тип данных, который позволяет по ключу получать или сохранять значение. Абстрактный он, потому что ничего не говорит о том, как этот тип данных должен быть реализован. И правда, если немного пофантазировать, можно придумать десятки разных реализаций разного уровня адекватности.
Для примера можем взять банальный связный список. На put мы обойдём его весь от начала до конца, чтобы убедиться, что у нас ещё нет такого элемента, а если нет, то добавим его в конец списка; на get – просто обойдём список от начала до конца в поисках нужного элемента. Алгоритмическая сложность поиска и добавления элемента в такой ассоциативный массив – O(n), что не очень хорошо.
Из простых, но чуть более адекватных реализаций можно рассмотреть простой массив, элементы которого мы всегда будем держать отсортированными по ключу. Поиск в таком массиве можно осуществлять бинарным поиском, получив O(log(n)), но вот добавление в него элементов может потребовать копирования больших кусков памяти из-за необходимости освободить место под элемент в строго определённой позиции.
Если же посмотреть на то, как реализуются ассоциативные массивы на практике, то вероятнее всего мы увидим какое-либо дерево или хеш-таблицу.
Хеш-таблица
Хеш-таблица – это структура данных, реализующая ассоциативный массив, устройство которой представляет собой двухэтапный процесс.
На первом этапе наш ключ прогоняется через хеш-функцию. Это функция, которая на вход принимает набор байт (наш ключ), а на выходе обычно даёт какое-то число. Это число на втором этапе мы используем для поиска значения.
Как? Вариантов множество. Первое, что приходит в голову, — использовать это число в качестве индекса в обычном массиве. Массиве, в котором лежат наши значения. Но этот вариант не будет работать как минимум по двум причинам:
Область значений хеш-функции, скорее всего, больше, чем размер массива, который бы нам хотелось хранить выделенным в памяти.
Обе эти проблемы обычно решаются выделением массива ограниченного размера, каждый элемент которого является указателем на другой массив (bucket). Область значений нашей хеш-функции мы затем отображаем на размер первого массива.
Как? Вариантов, опять же, много. Например, взять остаток от деления на размер массива или просто взять нужное количество младших бит числа, если размер массива у нас является степенью двойки (остаток от деления – значительно более медленная операция для процессора по сравнению со сдвигом, так что обычно предпочтение отдаётся именно массивам с размером, являющимся степенью двойки).
Я привёл в пример один из распространённых способов реализации хеш-таблицы, но вообще их великое множество. И в зависимости от выбранного способа борьбы с коллизиями мы получим разную производительность. Если же говорить об алгоритмической сложности для хеш-таблиц, то в среднем у нас будет O(1), а в вырожденных случаях (worst case) может получиться и O(n).
Деревья
С деревьями всё довольно просто. Для реализации ассоциативных массивов используются различные бинарные деревья – такие, как, например, красно-чёрное дерево. В случае если дерево сбалансировано, мы получим O(log n) на операцию.
Некоторые реализации деревьев, такие как google btree, учитывают современную иерархию памяти и хранят ключи пачками для более эффективного использования процессорных кешей.
Деревья позволяют реализовать обход элементов по возрастанию или убыванию ключей, что зачастую является очень важным условием при выборе реализации. Хеш-таблицы этого не умеют.
Читайте также: