Implementazione aperta di Facebook di F14 hash tables

Cumpagnia di Facebook annunziatu circa l'implementazione open source di tabelle hash F14, ottimizzata per u cunsumu di memoria efficiente. F14 hè utilizatu in l'infrastruttura di Facebook cum'è un sustitutu per a maiò parte di i tipi di tavule hash è ponu riduce u cunsumu di memoria senza sacrificà u rendiment. F14 notevolmente supera google::sparse_hash_map hash tables, chì finu à avà sò stati cunsiderati i più efficaci in quantu à u cunsumu di memoria. U codice di u prughjettu hè scrittu in C++ è hè inclusu in a biblioteca Follia.

F14 si riferisce à algoritmi cù un sistema di risuluzione di collisione basatu nantu à doppia hashing cù 14 sequenze di campioni (Una catena di 14 slots hè almacenata in una cellula di table hash, è l'intervallu trà e cellule hè calculatu utilizendu una funzione hash ausiliaria). Per accelerà l'operazioni di filtrazione di e cellule, l'implementazione usa l'istruzzioni vettoriali SSE2 per i sistemi x86_64 è NEON per Aarch64, chì permettenu di parallelizà l'esekzione di l'operazioni per a selezzione di slots cù catene chjave è sifting out keys in a catena. I blocchi di 14 slots sò processati à tempu, chì hè l'equilibriu ottimale trà l'efficienza di l'usu di u cache di u processatore è u numeru di collisioni.

Una caratteristica speciale di F14 hè a capacità di selezziunà diverse strategie di almacenamiento di dati:

• F14NodeMap - cunsuma a minima memoria per e chjave grande è mediu. Assicura chì l'elementi sò almacenati indirettamente cù una chjama à malloc in ogni inserimentu;
• F14ValueMap - furnisce u cunsumu minimu di memoria per i chjavi chjuchi. L'elementi sò almacenati in i celi stessi (inline). Per i chjavi mediu è grande, questu approcciu porta à un sopratuttu di memoria notevuli;
• F14VectorMap - funziona più veloce per tavule grandi è chjavi cumplessi, ma più lento per chjavi simplici è tavulini chjuchi. L'elementi sò imballati in una matrice continuamente populata è indirizzate da un punteru d'indici 32-bit;
• F14FastMap hè una strategia cumminata. Se a chjave hè menu di 24 bytes, allora F14ValueMap hè sceltu, è se più, F14VectorMap hè sceltu.

Source: opennet.ru