Facebook deschide implementarea tabelelor hash F14

Compania Facebook a anunțat despre implementarea open source a tabelelor hash F14, optimizat pentru un consum eficient de memorie. F14 este folosit în infrastructura Facebook ca înlocuitor pentru majoritatea tipurilor de tabele hash și poate reduce consumul de memorie fără a sacrifica performanța. F14 depășește vizibil tabelele hash google::sparse_hash_map, care până acum au fost considerate cele mai eficiente din punct de vedere al consumului de memorie. Codul proiectului este scris în C++ și este inclus în bibliotecă Nebunie.

F14 se referă la algoritmi cu un sistem de rezoluție a coliziunilor bazat pe hashing dublu cu 14 secvențe de mostre (un lanț de 14 sloturi este stocat într-o celulă de tabel hash, iar intervalul dintre celule este calculat folosind o funcție hash auxiliară). Pentru a accelera operațiunile de filtrare a celulelor, implementarea folosește instrucțiuni vectoriale SSE2 pentru sistemele x86_64 și NEON pentru Aarch64, care permit paralelizarea execuției operațiunilor de selectare a sloturilor cu brelocuri și cernerea cheilor din lanț. Blocurile de 14 sloturi sunt procesate simultan, ceea ce reprezintă echilibrul optim între eficiența utilizării cache-ului procesorului și numărul de coliziuni.

O caracteristică specială a F14 este capacitatea de a selecta diferite strategii de stocare a datelor:

• F14NodeMap - consumă cea mai mică memorie pentru cheile mari și medii. Se asigură că elementele sunt stocate indirect cu un apel la malloc la fiecare inserare;
• F14ValueMap - oferă un consum minim de memorie pentru cheile mici. Elementele sunt stocate în celulele în sine (inline). Pentru tastele medii și mari, această abordare duce la o suprasarcină de memorie vizibilă;
• F14VectorMap - funcționează mai rapid pentru tabelele mari și cheile complexe, dar mai lent pentru cheile simple și mesele mici. Elementele sunt împachetate într-o matrice populată continuu și adresate de un pointer index pe 32 de biți;
• F14FastMap este o strategie combinată. Dacă cheia este mai mică de 24 de octeți, atunci este selectat F14ValueMap, iar dacă este mai mare, este selectat F14VectorMap.

Sursa: opennet.ru