Facebook tvrtka o open source implementaciji hash tablica , optimiziran za učinkovitu potrošnju memorije. F14 se koristi u Facebook infrastrukturi kao zamjena za većinu tipova hash tablica i može smanjiti potrošnju memorije bez žrtvovanja performansi. F14 osjetno nadmašuje google::sparse_hash_map hash tablice, koje su do sada smatrane najučinkovitijima u pogledu potrošnje memorije. Kôd projekta napisan je u C++ i uključen je u biblioteku .
F14 se odnosi na algoritme sa sustavom rješavanja sudara koji se temelji na dvostrukom raspršivanju s 14 (lanac od 14 utora pohranjuje se u jednoj ćeliji hash tablice, a interval između ćelija izračunava se pomoću pomoćne hash funkcije). Kako bi se ubrzale operacije filtriranja ćelija, implementacija koristi vektorske instrukcije SSE2 za x86_64 sustave i NEON za Aarch64, koje omogućuju paralelno izvršavanje operacija za odabir utora s lancima ključeva i izdvajanje ključeva unutar lanca. Blokovi od 14 utora obrađuju se istovremeno, što je optimalna ravnoteža između učinkovitosti korištenja predmemorije procesora i broja kolizija.
Posebna značajka F14 je mogućnost odabira različitih strategija pohrane podataka:
- F14NodeMap - troši najmanje memorije za velike i srednje ključeve. Osigurava neizravno pohranjivanje elemenata s pozivom na malloc pri svakom umetanju;
- F14ValueMap - pruža minimalnu potrošnju memorije za male ključeve. Elementi su pohranjeni u samim ćelijama (inline). Za srednje i velike ključeve, ovaj pristup dovodi do značajnog opterećenja memorije;
- F14VectorMap - radi brže za velike tablice i složene ključeve, ali sporije za jednostavne ključeve i male tablice. Elementi su pakirani u kontinuirano popunjen niz i adresirani 32-bitnim pokazivačem indeksa;
- F14FastMap je kombinirana strategija. Ako je ključ manji od 24 bajta, odabran je F14ValueMap, a ako je veći, odabran je F14VectorMap.
Izvor: opennet.ru