Компания Facebook объявила об открытии исходных текстов реализации хэш-таблиц F14, оптимизированной для эффективного потребления памяти. F14 используется в инфраструктуре Facebook в качестве замены большинства типов хэш-таблиц и позволяет снизить потребление памяти без потери производительности. F14 заметно превосходит по производительности хэш-таблицы google::sparse_hash_map, до сих пор считавшиеся наиболее эффективными по потреблению памяти. Код проекта написан на языке C++ и включен в состав библиотеки Folly.
F14 относится к алгоритмам с системой разрешения коллизий на основе двойного хэширования с 14 последовательностями проб (в одной ячейке хэш-таблицы хранится цепочка из 14 слотов, а интервал между ячейками вычисляется при помощи вспомогательной хеш-функции). Для ускорения операций фильтрации ячеек в реализации используются векторные инструкции SSE2 для систем x86_64 и NEON для Aarch64, которые позволяют распараллелить выполнение операций выбора слотов с цепочками ключей и отсеивания ключей внутри цепочки. За раз обрабатываются блоки в 14 слотов, что является оптимальным балансом между эффективностью использования процессорного кэша и числом коллизий.
Особенностью F14 является возможности выбора различных стратегий хранения данных:
- F14NodeMap - потребляет меньше всего памяти для ключей большого и среднего размера. Обеспечивает косвенное сохранение элементов с вызовом при каждой вставке функции malloc;
- F14ValueMap - обеспечивает минимальное потребление памяти для небольших ключей. Элементы хранятся в самих ячейках (inline). Для средних и больших ключей подобных подход приводит к заметным накладным расходам памяти;
- F14VectorMap - работает быстрее для больших таблиц и сложных ключей, но медленее для простых ключей и небольших таблиц. Элементы упаковываются в непрерывно заполняемом массиве и адресуются 32-разрядным индексным указателем;
- F14FastMap - комбинированная стратегия. Если ключ меньше 24 байтов, то выбирается F14ValueMap, а если больше - F14VectorMap.
Дополнение: Проведено масштабное тестирование производительности и потребления памяти около 100 вариантов хэш-таблиц (20 реализаций unordered_map, каждая с 5 разными методами хэширования). Судя по тестам folly::F14ValueMap и folly::F14NodeMap демонстрируют весьма средние показатели по производительности и хорошие, но не лидирующие, по потреблению памяти. Наиболее оптимальное сочетание показателей производительности и потребления памяти показали robin_hood::unordered_flat_map для числовых ключей и robin_hood::unordered_node_map для строковых значений ключей.
В тестах на создание по потреблению памяти лучшими оказались tsl::sparse_map и phmap::parallel_flat_hash_map, причём последний в некоторых тестах обгоняет F14 по производительности).
В тестах на заполнение методы robin_hood::unordered_flat_map и ska::bytell_hash_map потребляют примерно на 10% больше памяти, но в 2 раза быстрее.
В тестах на выборку показатели F14 оказались весьма посредственными, в том числе и по потреблению памяти.
В тесте по полному перебору всех элементов лидером оказался tsl::sparse_map, которые в других тестах обгонял F14 и по потреблению памяти.
Поддержать публикацию: Coinbase, Yandex.Money