Facebook apre l'implementazione delle tabelle hash F14

Azienda Facebook ha annunciato il sull'implementazione open source delle tabelle hash F14, ottimizzato per un consumo efficiente della memoria. F14 viene utilizzato nell'infrastruttura di Facebook in sostituzione della maggior parte dei tipi di tabelle hash e può ridurre il consumo di memoria senza sacrificare le prestazioni. F14 supera notevolmente le tabelle hash google::sparse_hash_map, che finora sono state considerate le più efficienti in termini di consumo di memoria. Il codice del progetto è scritto in C++ ed è incluso nella libreria Follia.

F14 si riferisce ad algoritmi con un sistema di risoluzione delle collisioni basato sul doppio hashing con 14 sequenze di campioni (una catena di 14 slot viene memorizzata in una cella della tabella hash e l'intervallo tra le celle viene calcolato utilizzando una funzione hash ausiliaria). Per velocizzare le operazioni di filtraggio delle celle, l'implementazione utilizza le istruzioni vettoriali SSE2 per i sistemi x86_64 e NEON per Aarch64, che permettono di parallelizzare l'esecuzione delle operazioni di selezione degli slot con portachiavi e di vagliatura delle chiavi all'interno della catena. Vengono elaborati blocchi di 14 slot alla volta, che rappresenta l'equilibrio ottimale tra l'efficienza dell'utilizzo della cache del processore e il numero di collisioni.

Una caratteristica speciale di F14 è la possibilità di selezionare diverse strategie di archiviazione dei dati:

• F14NodeMap: consuma meno memoria per chiavi di grandi e medie dimensioni. Garantisce che gli elementi vengano archiviati indirettamente con una chiamata a malloc ad ogni inserimento;
• F14ValueMap: fornisce un consumo minimo di memoria per i tasti piccoli. Gli elementi vengono memorizzati nelle celle stesse (in linea). Per i tasti medi e grandi, questo approccio comporta un notevole sovraccarico della memoria;
• F14VectorMap: funziona più velocemente per tabelle di grandi dimensioni e chiavi complesse, ma più lentamente per chiavi semplici e tabelle piccole. Gli elementi sono raggruppati in un array popolato continuamente e indirizzati da un puntatore all'indice a 32 bit;
• F14FastMap è una strategia combinata. Se la chiave è inferiore a 24 byte, viene selezionato F14ValueMap e, se superiore, viene selezionato F14VectorMap.

Fonte: opennet.ru