Spoločnosť Facebook o open source implementácii hašovacích tabuliek , optimalizované pre efektívnu spotrebu pamäte. F14 sa používa v infraštruktúre Facebooku ako náhrada väčšiny typov hash tabuliek a dokáže znížiť spotrebu pamäte bez obetovania výkonu. F14 výrazne prekonáva hašovacie tabuľky google::sparse_hash_map, ktoré boli doteraz považované za najefektívnejšie z hľadiska spotreby pamäte. Kód projektu je napísaný v C++ a je súčasťou knižnice .
F14 označuje algoritmy so systémom riešenia kolízií založeným na dvojitom hashovaní so 14 (reťazec 14 slotov je uložený v jednej bunke hašovacej tabuľky a interval medzi bunkami sa vypočíta pomocou pomocnej hašovacej funkcie). Na urýchlenie operácií filtrovania buniek implementácia využíva vektorové inštrukcie SSE2 pre systémy x86_64 a NEON pre Aarch64, ktoré umožňujú paralelné vykonávanie operácií na výber slotov s kľúčovými reťazcami a preosievanie kľúčov v reťazci. Naraz sa spracúvajú bloky 14 slotov, čo je optimálna rovnováha medzi efektivitou využitia vyrovnávacej pamäte procesora a počtom kolízií.
Špeciálnou funkciou F14 je možnosť výberu rôznych stratégií ukladania údajov:
- F14NodeMap - spotrebuje najmenej pamäte pre veľké a stredne veľké kľúče. Zabezpečuje, že prvky sú uložené nepriamo s volaním malloc pri každom vložení;
- F14ValueMap - poskytuje minimálnu spotrebu pamäte pre malé kľúče. Prvky sú uložené v samotných bunkách (inline). Pre stredné a veľké kľúče tento prístup vedie k značnej réžii pamäte;
- F14VectorMap - pracuje rýchlejšie pre veľké tabuľky a zložité klávesy, ale pomalšie pre jednoduché klávesy a malé tabuľky. Prvky sú zabalené do nepretržite vyplneného poľa a adresované 32-bitovým ukazovateľom indexu;
- F14FastMap je kombinovaná stratégia. Ak je kľúč menší ako 24 bajtov, vyberie sa F14ValueMap a ak viac, vyberie sa F14VectorMap.
Zdroj: opennet.ru