Компанія Facebook про відкриття вихідних текстів реалізації хеш-таблиць , оптимізована для ефективного споживання пам'яті. F14 використовується в інфраструктурі Facebook як заміна більшості типів хеш-таблиць і дозволяє знизити споживання пам'яті без втрати продуктивності. F14 помітно перевершує за продуктивністю хеш-таблиці google::sparse_hash_map, які досі вважалися найбільш ефективними по споживанню пам'яті. Код проекту написаний мовою C++ та включений до складу бібліотеки .
F14 відноситься до алгоритмів із системою дозволу колізій на основі подвійного хешування з 14 (в одному осередку хеш-таблиці зберігається ланцюжок з 14 слотів, а інтервал між осередками обчислюється за допомогою допоміжної хеш-функції). Для прискорення операцій фільтрації осередків у реалізації використовуються векторні інструкції SSE2 для систем x86_64 та NEON для Aarch64, які дозволяють розпаралелити виконання операцій вибору слотів з ланцюжками ключів та відсіювання ключів усередині ланцюжка. За раз обробляються блоки 14 слотів, що є оптимальним балансом між ефективністю використання процесорного кешу і числом колізій.
Особливістю F14 є можливості вибору різних стратегій зберігання даних:
- F14NodeMap – споживає найменше пам'яті для ключів великого та середнього розміру. Забезпечує опосередковане збереження елементів з викликом при кожній вставці функції malloc;
- F14ValueMap – забезпечує мінімальне споживання пам'яті для невеликих ключів. Елементи зберігаються у самих осередках (inline). Для середніх та великих ключів подібних підхід призводить до помітних накладних витрат пам'яті;
- F14VectorMap працює швидше для великих таблиць і складних ключів, але повільніше для простих ключів і невеликих таблиць. Елементи упаковуються в масиві, що безперервно заповнюється, і адресуються 32-розрядним індексним покажчиком;
- F14FastMap – комбінована стратегія. Якщо ключ менше 24 байтів, то вибирається F14ValueMap, а якщо більше - F14VectorMap.
Джерело: opennet.ru