Facebook abre implementação de tabelas hash F14

Empresa Facebook anunciou o sobre implementação de código aberto de tabelas hash F14, otimizado para consumo eficiente de memória. F14 é usado na infraestrutura do Facebook como substituto para a maioria dos tipos de tabelas hash e pode reduzir o consumo de memória sem sacrificar o desempenho. F14 supera visivelmente as tabelas hash google::sparse_hash_map, que até agora foram consideradas as mais eficientes em termos de consumo de memória. O código do projeto é escrito em C++ e está incluído na biblioteca Loucura.

F14 refere-se a algoritmos com sistema de resolução de colisão baseado em hashing duplo com 14 sequências de amostras (uma cadeia de 14 slots é armazenada em uma célula da tabela hash e o intervalo entre as células é calculado usando uma função hash auxiliar). Para agilizar as operações de filtragem de células, a implementação utiliza instruções vetoriais SSE2 para sistemas x86_64 e NEON para Aarch64, que permitem paralelizar a execução de operações de seleção de slots com chaveiros e triagem de chaves dentro da cadeia. Blocos de 14 slots são processados ​​por vez, o que é o equilíbrio ideal entre a eficiência do uso do cache do processador e o número de colisões.

Uma característica especial do F14 é a capacidade de selecionar diferentes estratégias de armazenamento de dados:

• F14NodeMap - consome menos memória para chaves grandes e médias. Garante que os elementos sejam armazenados indiretamente com uma chamada para malloc em cada inserção;
• F14ValueMap - fornece consumo mínimo de memória para chaves pequenas. Os elementos são armazenados nas próprias células (inline). Para chaves médias e grandes, essa abordagem leva a uma sobrecarga de memória perceptível;
• F14VectorMap – funciona mais rápido para tabelas grandes e chaves complexas, mas mais lento para chaves simples e tabelas pequenas. Os elementos são compactados em uma matriz continuamente preenchida e endereçados por um ponteiro de índice de 32 bits;
• F14FastMap é uma estratégia combinada. Se a chave tiver menos de 24 bytes, então F14ValueMap será selecionado e, se tiver mais, F14VectorMap será selecionado.

Fonte: opennet.ru