Facebook otvara implementaciju F14 hash tablica

Facebook kompanija najavljeno o implementaciji hash tablica otvorenog koda F14, optimiziran za efikasnu potrošnju memorije. F14 se koristi u infrastrukturi Facebooka kao zamjena za većinu tipova hash tablica i može smanjiti potrošnju memorije bez žrtvovanja performansi. F14 primjetno nadmašuje google::sparse_hash_map hash tablice, koje su do sada smatrane najefikasnijim u smislu potrošnje memorije. Kod projekta je napisan u C++ i uključen je u biblioteku Ludost.

F14 se odnosi na algoritme sa sistemom za rješavanje sudara zasnovanim na dvostrukom heširanju sa 14 sekvence uzoraka (lanac od 14 slotova je pohranjen u jednoj ćeliji heš tabele, a interval između ćelija se izračunava pomoću pomoćne funkcije heširanja). Da bi se ubrzale operacije filtriranja ćelija, implementacija koristi vektorske instrukcije SSE2 za x86_64 sisteme i NEON za Aarch64, koje omogućavaju paralelno izvršavanje operacija za odabir slotova sa lancima ključeva i određivanje ključeva unutar lanca. Blokovi od 14 slotova se obrađuju istovremeno, što je optimalna ravnoteža između efikasnosti korišćenja keš memorije procesora i broja kolizija.

Posebna karakteristika F14 je mogućnost odabira različitih strategija skladištenja podataka:

• F14NodeMap - troši najmanje memorije za velike i srednje tipke. Osigurava da se elementi spremaju indirektno s pozivom malloc-a na svakom umetanju;
• F14ValueMap - pruža minimalnu potrošnju memorije za male ključeve. Elementi se pohranjuju u samim ćelijama (inline). Za srednje i velike ključeve, ovaj pristup dovodi do primjetnih troškova memorije;
• F14VectorMap - radi brže za velike tabele i složene ključeve, ali sporije za jednostavne ključeve i male tabele. Elementi su spakovani u kontinuirano popunjeni niz i adresirani pomoću 32-bitnog indeksnog pokazivača;
• F14FastMap je kombinovana strategija. Ako je ključ manji od 24 bajta, odabire se F14ValueMap, a ako više, odabire se F14VectorMap.

izvor: opennet.ru