Исходное сообщение
"Facebook открыл реализацию хэш-таблиц F14" Отправлено opennews, 01-Май-19 22:03
Компания Facebook объявила (https://code.fb.com/developer-tools/f14/) об открытии исходных текстов реализации хэш-таблиц F14 (https://github.com/facebook/folly/blob/master/folly/containe... оптимизированной для эффективного потребления памяти. F14 используется в инфраструктуре Facebook в качестве замены большинства типов хэш-таблиц и позволяет снизить потребление памяти без потери производительности. F14 заметно превосходит по производительности хэш-таблицы google::sparse_hash_map, до сих пор считавшиеся наиболее эффективными по потреблению памяти. Код проекта написан на языке C++ и включен в состав библиотеки Folly (https://github.com/facebook/folly/). F14 относится к алгоритмам с системой разрешения коллизий на основе двойного хэширования с 14 последовательностями проб (https://ru.wikipedia.org/wiki/%D0%A5%D0%... (в одной ячейке хэш-таблицы хранится цепочка из 14 слотов, а интервал между ячейками вычисляется при помощи вспомогательной хеш-функции). Для ускорения операций фильтрации ячеек в реализации используются векторные инструкции SSE2 для систем x86_64 и NEON для Aarch64, которые позволяют распараллелить выполнение операций выбора слотов с цепочками ключей и отсеивания ключей внутри цепочки. За раз обрабатываются блоки в 14 слотов, что является оптимальным балансом между эффективностью использования процессорного кэша  и числом коллизий. Особенностью F14 является возможности выбора различных стратегий хранения данных: -  F14NodeMap - потребляет меньше всего памяти для ключей большого и среднего размера. Обеспечивает косвенное сохранение элементов с вызовом при каждой вставке функции malloc; -  F14ValueMap  - обеспечивает минимальное потребление памяти для небольших ключей. Элементы хранятся в самих ячейках (inline). Для средних и больших ключей подобных подход приводит к заметным накладным расходам памяти; -  F14VectorMap - работает быстрее для больших таблиц и сложных ключей, но медленее для простых ключей и небольших таблиц. Элементы упаковываются в непрерывно заполняемом массиве и адресуются 32-разрядным индексным указателем; -  F14FastMap - комбинированная стратегия. Если ключ меньше 24 байтов, то  выбирается F14ValueMap, а если больше - F14VectorMap. URL: https://code.fb.com/developer-tools/f14/ Новость: https://www.opennet.ru/opennews/art.shtml?num=50611