Компания 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.me/opennews/art.shtml?num=50611
Круто, очень круто. FaceBook молодцы, очень большой вклад вносят в OpenSurce Community!
Два чая этому ГоспоДину.
https://en.wikipedia.org/wiki/Embrace,_extend_and_extinguish
- nuff said
https://ru.wikipedia.org/wiki/Аноним
- nuff said
https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o.../
>позволяет снизить потребление памятино зачем фейсбуку может понадобиться экономить память?
Чтобы соответствовать своей клиентуре.
Двухнедельная память, как у целевой аудитории, это ведь круто!
>>позволяет снизить потребление памяти
> но зачем фейсбуку может понадобиться экономить память?Деньги когда-нибудь кончаются даже если у тебя их миллиарды.
> но зачем фейсбуку может понадобиться экономить память?Ну так не на клиентских машинах запускаются, а на своих собственных. Свои машины жалко говнософтом увешивать.
Экономия памяти является приятным побочным эффект попытки экономии L1D кеша ЦПУ.
Я НИЧЕГО не понял. Если какие-то реализации оптимальнее по всем параметрам тех, что в стандартной библиотеке языка C++, то логично втянуть эту реализацию в стандартную библиотеку, а ту, что была - выкинуть. Ибо нафига нам ещё одна зависимость? Почему это не было сделано?
В стандартной библиотеки обычная хэш-таблица, которая более-менее подойдет для любой ситуации, а тут разреженная, которая экономит память для огромных разреженных таблиц, но существенно проигрывает в скорости для маленьких или неразреженных. А так-то и я не против, чтобы все популярные виды хэш-массивов и деревьев были в std, но комитет хочет чтобы была только одна структура данных каждого типа
Выглядит очень похоже на Swiss Table от Google:
https://youtu.be/ncHmEUmJZf4
интересно.
А почему F14, a не F13 ?