Podjetje Facebook o odprtokodnih implementacijah zgoščenih tabel optimiziran za učinkovito porabo pomnilnika. F14 se uporablja v Facebook infrastrukturi kot zamenjava za večino vrst zgoščenih tabel in vam omogoča zmanjšanje porabe pomnilnika brez žrtvovanja zmogljivosti. F14 opazno prekaša zgoščevalne tabele google::sparse_hash_map, ki so doslej veljale za najbolj pomnilniško učinkovite. Koda projekta je napisana v C++ in vključena v knjižnico .
F14 se nanaša na algoritme s sistemom reševanja trkov, ki temelji na dvojnem zgoščevanju s 14 (ena celica zgoščevalne tabele hrani verigo 14 rež, interval med celicami pa se izračuna s pomočjo pomožne zgoščevalne funkcije). Za pospešitev operacij filtriranja celic implementacija uporablja vektorska navodila SSE2 za sisteme x86_64 in NEON za sisteme Aarch64, ki vam omogočajo, da vzporedite operacije izbire rež z verigami ključev in ključev za pregledovanje znotraj verige. Naenkrat se obdelujejo bloki po 14 rež, kar je optimalno razmerje med učinkovitostjo uporabe predpomnilnika procesorja in številom kolizij.
Značilnost F14 je možnost izbire različnih strategij shranjevanja podatkov:
- F14NodeMap - porabi najmanj pomnilnika za velike in srednje velike ključe. Zagotavlja posredno shranjevanje elementov s klicem vsakič, ko je vstavljena funkcija malloc;
- F14ValueMap - Zagotavlja minimalno porabo pomnilnika za majhne ključe. Elementi so shranjeni v samih celicah (inline). Pri srednjih in velikih ključih ta pristop povzroči opazno porabo pomnilnika;
- F14VectorMap je hitrejši za velike tabele in zapletene ključe, vendar počasnejši za preproste ključe in majhne tabele. Elementi so zapakirani v sosednjo matriko in naslovljeni z 32-bitnim indeksnim kazalcem;
- F14FastMap je kombinirana strategija. Če je ključ manjši od 24 bajtov, je izbran F14ValueMap, če pa več, je izbran F14VectorMap.
Vir: opennet.ru