Викиновости

Facebook открыл реализацию хэш-таблиц F14

1 мая 2019 года

Компания 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 и по потреблению памяти.

Источники

править


 
 
Creative Commons
Эта статья содержит материалы из статьи «Facebook открыл реализацию хэш-таблиц F14», опубликованной OpenNET и распространяющейся на условиях лицензии Creative Commons Attribution (CC BY) — указание автора, источник и лицензию.
 
Эта статья загружена автоматически ботом NewsBots в архив и ещё не проверялась редакторами Викиновостей.
Любой участник может оформить статью: добавить иллюстрации, викифицировать, заполнить шаблоны и добавить категории.
Любой редактор может снять этот шаблон после оформления и проверки.

Комментарии

Викиновости и Wikimedia Foundation не несут ответственности за любые материалы и точки зрения, находящиеся на странице и в разделе комментариев.



Источник — https://ru.wikinews.org/w/index.php?title=Facebook_открыл_реализацию_хэш-таблиц_F14&oldid=8728416