Benchmarks realizados no programa SMHasher no Core 2 Duo 3.0 GHzEm Habré falou repetidamente sobre
funções hash não criptográficas , que são uma ordem de magnitude mais rápida que as criptográficas. Eles são usados onde a velocidade é importante e não faz sentido usar o MD5 ou SHA1 lento. Por exemplo, para criar tabelas de hash com armazenamento de pares de valores-chave ou verificar rapidamente a soma de verificação ao transferir arquivos grandes.
Uma das mais populares é a família de funções de hash
xxHash , que surgiu há cerca de cinco anos. Embora inicialmente esses hashes tenham sido concebidos para verificar a soma de verificação durante a compactação LZ4, eles começaram a ser usados em uma variedade de tarefas. É compreensível: basta olhar para a tabela acima com uma comparação do desempenho do xxHash e algumas outras funções de hash. Neste teste, o xxHash supera pela metade o seu concorrente mais próximo em desempenho. A nova versão do
XXH3 eleva ainda mais os
padrões .
A seguir, os gráficos são clicáveisO autor do programa, Yann Collet,
escreve que a idéia de melhorar o algoritmo surgiu durante a implementação do filtro Bloom, que exigiu a geração rápida de 64 bits pseudo-aleatórios com base em pequenos dados de entrada de comprimento variável. Em princípio, o padrão XXH64 poderia lidar com isso, mas o processamento de pequenos dados de entrada nunca foi uma prioridade em seu desenvolvimento. Em outras palavras, a otimização é possível. Como resultado dessa otimização, apareceu uma nova função de hash XXH3, na qual as idéias de alguns outros algoritmos de hash são implementadas. O mais interessante é que o XXH3 é significativamente mais rápido que todas as variantes existentes do xxHash, não apenas em pequenos dados de entrada, mas em quase todos os casos de uso.
XXH3 elimina a principal desvantagem do XXH64 - limitação de hash de 64 bits. O autor diz que, por esse motivo, costumava ser solicitado a lançar pelo menos uma versão de 128 bits. Portanto, a função hash XXH3 é teoricamente capaz de gerar hashes de até 256 bits.
No XXH3, um loop interno que é manipulado de maneira ideal por vetorização. Por esse motivo, a função usa suporte de hardware nos conjuntos de instruções SSE2, AVX2 e NEON. O desempenho depende do compilador. Inesperadamente, a versão compilada pelo clang é muito superior ao restante. Ian Colle até pensou que o desempenho da função hash aqui excederia a largura de banda da memória. Esta versão no gráfico corresponde a uma linha tracejada.
Como resultado, verificou-se que a função hash com suporte para AVX2 tem uma taxa de transferência muito maior que a RAM, portanto o tamanho do cache se torna um fator importante. No entanto, em muitas tarefas, é necessário processar dados que já estão no cache; portanto, trabalhar em uma velocidade mais rápida que a memória faz todo o sentido.
O suporte às instruções SSE2 permite que a nova função de hash contorne significativamente o XXH32 em aplicativos de 32 bits que ainda são comuns no mundo real (por exemplo, código de bytes WASM).
Em pequenos dados de entrada (20 a 30 bytes), a função de hash XXH3 não é muito, mas ainda supera o
CityHash do Google e o FarmHash, que costumavam ser líderes claros.
O gráfico a seguir mostra os resultados do teste mais realista com dados de comprimento variável (variável aleatória de 1 a N).
Outro teste leva em consideração o
atraso : aqui o hash começa em um sinal. A idéia é simular uma carga de trabalho real, onde a função hash não funciona continuamente, mas é chamada em outros processos em um determinado momento.
O autor escreve que esse teste com uma multiplicação de 64 × 64 => 128 bits prefere os algoritmos
mumv2 de Vladimir Makarov e
t1ha2 de Leo Yuryev.
Finalmente, aqui está o gráfico final e mais importante que mostra a taxa de hash nos dados de entrada de comprimento variável, levando em consideração o atraso. Ele reflete o uso real da função hash, por exemplo, em bancos de dados.
O XXH3 foi lançado como parte do
pacote xxHash v0.7.0 . Possui a marca "experimental" e, para desbloquear, você precisa usar a macro
XXH_STATIC_LINKING_ONLY . O autor explica que a função hash até agora só pode ser usada em dados efêmeros de teste, mas não para o armazenamento real de hashes. De acordo com os resultados do período experimental e a coleção de análises de usuários, a função XXH3 receberá um status estável na próxima versão do xxHash.
