Facebook abre implementación de tablas hash F14

empresa facebook anunció el sobre la implementación de código abierto de tablas hash F14, optimizado para un consumo eficiente de memoria. F14 se utiliza en la infraestructura de Facebook como reemplazo de la mayoría de los tipos de tablas hash y puede reducir el consumo de memoria sin sacrificar el rendimiento. F14 supera notablemente a las tablas hash google::sparse_hash_map, que hasta ahora se han considerado las más eficientes en términos de consumo de memoria. El código del proyecto está escrito en C++ y está incluido en la biblioteca. Locura.

F14 se refiere a algoritmos con un sistema de resolución de colisiones basado en doble hash con 14 secuencias de muestras (Se almacena una cadena de 14 ranuras en una celda de la tabla hash y el intervalo entre celdas se calcula utilizando una función hash auxiliar). Para acelerar las operaciones de filtrado de celdas, la implementación utiliza instrucciones vectoriales SSE2 para sistemas x86_64 y NEON para Aarch64, que permiten paralelizar la ejecución de operaciones para seleccionar ranuras con llaveros y filtrar claves dentro de la cadena. Se procesan bloques de 14 ranuras a la vez, lo que constituye el equilibrio óptimo entre la eficiencia del uso de la memoria caché del procesador y el número de colisiones.

Una característica especial de F14 es la capacidad de seleccionar diferentes estrategias de almacenamiento de datos:

• F14NodeMap: consume la menor cantidad de memoria para claves grandes y medianas. Garantiza que los elementos se almacenen indirectamente con una llamada a malloc en cada inserción;
• F14ValueMap: proporciona un consumo mínimo de memoria para claves pequeñas. Los elementos se almacenan en las propias celdas (en línea). Para claves medianas y grandes, este enfoque genera una sobrecarga de memoria notable;
• F14VectorMap: funciona más rápido para tablas grandes y claves complejas, pero más lento para claves simples y tablas pequeñas. Los elementos se empaquetan en una matriz que se completa continuamente y se abordan mediante un puntero de índice de 32 bits;
• F14FastMap es una estrategia combinada. Si la clave tiene menos de 24 bytes, se selecciona F14ValueMap y, si tiene más, se selecciona F14VectorMap.

Fuente: opennet.ru