společnost Facebook o open source implementaci hash tabulek , optimalizované pro efektivní spotřebu paměti. F14 se používá v infrastruktuře Facebooku jako náhrada většiny typů hash tabulek a dokáže snížit spotřebu paměti bez obětování výkonu. F14 znatelně překonává hashovací tabulky google::sparse_hash_map, které byly dosud považovány za nejefektivnější z hlediska spotřeby paměti. Kód projektu je napsán v C++ a je součástí knihovny .
F14 označuje algoritmy se systémem řešení kolizí založeným na dvojitém hašování se 14 (řetězec 14 slotů je uložen v jedné buňce hašovací tabulky a interval mezi buňkami je vypočítán pomocí pomocné hašovací funkce). Pro urychlení operací filtrování buněk implementace využívá vektorové instrukce SSE2 pro systémy x86_64 a NEON pro Aarch64, které umožňují paralelizaci provádění operací pro výběr slotů s řetězci klíčů a prosévání klíčů v řetězci. Najednou jsou zpracovávány bloky 14 slotů, což je optimální rovnováha mezi efektivitou využití cache procesoru a počtem kolizí.
Speciální funkcí F14 je možnost výběru různých strategií ukládání dat:
- F14NodeMap – spotřebovává nejméně paměti pro velké a středně velké klíče. Zajišťuje, že prvky jsou uloženy nepřímo s voláním malloc při každém vložení;
- F14ValueMap - poskytuje minimální spotřebu paměti pro malé klíče. Prvky jsou uloženy v samotných buňkách (inline). U středních a velkých klíčů tento přístup vede ke značné paměti;
- F14VectorMap - pracuje rychleji pro velké tabulky a složité klávesy, ale pomaleji pro jednoduché klávesy a malé tabulky. Prvky jsou zabaleny do spojitě zaplňovaného pole a adresovány 32bitovým ukazatelem indexu;
- F14FastMap je kombinovaná strategie. Je-li klíč menší než 24 bajtů, je vybrána F14ValueMap, a pokud více, je vybrána F14VectorMap.
Zdroj: opennet.ru