Facebook cég a hash táblák nyílt forráskódú megvalósításáról , hatékony memóriafelhasználásra optimalizálva. Az F14-et a Facebook infrastruktúrájában használják a legtöbb hash-tábla helyettesítésére, és a teljesítmény feláldozása nélkül csökkentheti a memóriafogyasztást. Az F14 érezhetően felülmúlja a google::sparse_hash_map hash táblákat, amelyeket eddig a leghatékonyabbnak tartottak a memóriafelhasználás szempontjából. A projekt kódja C++ nyelven íródott, és benne van a könyvtárban .
Az F14 azokra az algoritmusokra vonatkozik, amelyek ütközésfeloldó rendszere a 14-es kettős hashelésen alapul (14 résből álló lánc egy hash-tábla cellában van tárolva, és a cellák közötti intervallumot egy kiegészítő hash-függvény segítségével számítjuk ki). A cellaszűrési műveletek felgyorsítása érdekében a megvalósítás az SSE2 vektorutasításokat használja az x86_64 rendszerekhez és a NEON-t az Aarch64-hez, amelyek lehetővé teszik a kulcsláncokkal történő réskiválasztási műveletek végrehajtásának párhuzamosítását és a kulcsok kiszűrését a láncon belül. Egyszerre 14 slotból álló blokkok kerülnek feldolgozásra, ami az optimális egyensúly a processzor gyorsítótárának használatának hatékonysága és az ütközések száma között.
Az F14 különlegessége a különböző adattárolási stratégiák kiválasztásának lehetősége:
- F14NodeMap – a legkevesebb memóriát fogyasztja a nagy és közepes méretű kulcsokhoz. Gondoskodik arról, hogy az elemek közvetett módon, a malloc hívásával minden beszúráskor kerüljenek tárolásra;
- F14ValueMap – minimális memóriafelhasználást biztosít a kis kulcsokhoz. Az elemek magukban a cellákban tárolódnak (inline). Közepes és nagy billentyűk esetén ez a megközelítés észrevehető memóriatöbblethez vezet;
- F14VectorMap – gyorsabban működik nagy táblák és összetett kulcsok esetén, de lassabban egyszerű kulcsok és kis táblázatok esetén. Az elemek egy folyamatosan feltöltött tömbbe vannak csomagolva, és egy 32 bites indexmutató címezi őket;
- Az F14FastMap egy kombinált stratégia. Ha a kulcs 24 bájtnál kisebb, akkor az F14ValueMap van kiválasztva, és ha több, az F14VectorMap van kiválasztva.
Forrás: opennet.ru