Facebook abre a implementación das táboas hash F14

empresa de Facebook anunciou sobre a implementación de código aberto de táboas hash F14, optimizado para un consumo eficiente de memoria. F14 úsase na infraestrutura de Facebook como substituto para a maioría dos tipos de táboas hash e pode reducir o consumo de memoria sen sacrificar o rendemento. F14 supera notablemente as táboas hash de google::sparse_hash_map, que ata agora foron consideradas as máis eficientes en termos de consumo de memoria. O código do proxecto está escrito en C++ e inclúese na biblioteca Folla.

F14 refírese a algoritmos cun sistema de resolución de colisións baseado en hash dobre con 14 secuencias de mostras (nunha cela da táboa hash gárdase unha cadea de 14 slots e o intervalo entre celas calcúlase mediante unha función hash auxiliar). Para acelerar as operacións de filtrado de células, a implementación utiliza instrucións vectoriais SSE2 para sistemas x86_64 e NEON para Aarch64, que permiten paralelizar a execución das operacións para seleccionar slots con chaveiros e filtrar as claves dentro da cadea. Os bloques de 14 slots son procesados ​​á vez, o que é o equilibrio óptimo entre a eficiencia de usar a caché do procesador e o número de colisións.

Unha característica especial de F14 é a capacidade de seleccionar diferentes estratexias de almacenamento de datos:

• F14NodeMap: consome menos memoria para claves grandes e medianas. Asegura que os elementos se almacenen indirectamente cunha chamada a malloc en cada inserción;
• F14ValueMap: proporciona un consumo mínimo de memoria para teclas pequenas. Os elementos almacénanse nas propias celas (en liña). Para claves medianas e grandes, este enfoque leva a unha sobrecarga de memoria notable;
• F14VectorMap: funciona máis rápido para táboas grandes e teclas complexas, pero máis lento para teclas simples e táboas pequenas. Os elementos están empaquetados nunha matriz continuamente poboada e dirixidas por un punteiro de índice de 32 bits;
• F14FastMap é unha estratexia combinada. Se a clave ten menos de 24 bytes, seleccionase F14ValueMap e, se é superior, seleccionase F14VectorMap.

Fonte: opennet.ru