Facebook kompanija apie atvirojo kodo maišos lentelių įgyvendinimą , optimizuotas efektyviam atminties naudojimui. F14 naudojamas Facebook infrastruktūroje kaip daugelio tipų maišos lentelių pakaitalas ir gali sumažinti atminties suvartojimą neprarandant našumo. F14 pastebimai lenkia google::sparse_hash_map maišos lenteles, kurios iki šiol buvo laikomos efektyviausiomis atminties suvartojimo prasme. Projekto kodas parašytas C++ ir įtrauktas į biblioteką .
F14 reiškia algoritmus su susidūrimo sprendimo sistema, pagrįsta dviguba maiša su 14 (14 lizdų grandinė saugoma viename maišos lentelės langelyje, o intervalas tarp langelių apskaičiuojamas naudojant pagalbinę maišos funkciją). Siekiant pagreitinti langelių filtravimo operacijas, įgyvendinimas naudoja vektorines instrukcijas SSE2 x86_64 sistemoms ir NEON, skirtas Aarch64, kurios leidžia lygiagrečiai atlikti tarpsnių su raktų grandinėmis pasirinkimo ir raktų išsijojimo iš grandinės operacijų vykdymą. Vienu metu apdorojami 14 lizdų blokai, o tai yra optimali pusiausvyra tarp procesoriaus talpyklos naudojimo efektyvumo ir susidūrimų skaičiaus.
Ypatinga F14 savybė yra galimybė pasirinkti skirtingas duomenų saugojimo strategijas:
- F14NodeMap – sunaudoja mažiausiai atminties dideliems ir vidutinio dydžio klavišams. Užtikrina, kad elementai būtų saugomi netiesiogiai su iškvietimu į malloc kiekvieno įterpimo metu;
- F14ValueMap – užtikrina minimalų atminties suvartojimą mažiems klavišams. Elementai saugomi pačiose ląstelėse (inline). Naudojant vidutinius ir didelius klavišus, šis metodas žymiai padidina atminties sąnaudas;
- F14VectorMap – veikia greičiau didelėms lentelėms ir sudėtingiems klavišams, bet lėčiau – paprastiems klavišams ir mažoms lentelėms. Elementai supakuoti į nuolat pildomą masyvą ir adresuojami 32 bitų indekso žymekliu;
- F14FastMap yra kombinuota strategija. Jei raktas yra mažesnis nei 24 baitai, pasirenkamas F14ValueMap, o jei daugiau, pasirenkamas F14VectorMap.
Šaltinis: opennet.ru