Tecnologia de exploração automatizada de funções hash de inteiros

 (github.com/skeeto)
3 pontos por GN⁺ 2024-05-06 | 1 comentários | Compartilhar no WhatsApp
  • Hash Function Prospector é uma ferramenta que gera em grande volume funções hash de inteiros aleatórias, faz compilação JIT e avalia o comportamento de avalanche, depois imprime a melhor função atual em sintaxe C
  • A avaliação usa o avalanche score, que é o número médio de bits de saída que permanecem fixos quando um único bit de entrada é invertido; quanto menor, melhor, e o valor ideal é 0
  • O alvo da exploração são funções hash de inteiros de 32 e 64 bits; por causa do compilador JIT, a execução da ferramenta só é suportada em x86-64, mas as funções descobertas podem ser usadas em outros ambientes
  • As principais funções descobertas usam a estrutura xorshift-multiply-xorshift; o lowbias32 de 2 rodadas mostra um bias menor, por uma pequena diferença, do que o finalizador de 32 bits do MurmurHash3, e o triple32 de 3 rodadas fica próximo do limite teórico de bias
  • A medição exata de bias pode ser feita para funções de 32 bits com -E e -e, enquanto hashes de 16 bits ficam a cargo da ferramenta separada hp16, com atenção às regras de promoção de inteiros em C

O papel do Hash Function Prospector

  • Hash Function Prospector é uma ferramenta automatizada de descoberta de funções hash de inteiros
  • Ele gera aleatoriamente bilhões de funções hash de inteiros, faz compilação JIT delas e avalia seu comportamento de avalanche
  • Entre as funções geradas, a melhor no momento é impressa em sintaxe C
  • O texto relacionado Prospecting for Hash Functions está linkado

Critérios de avaliação e escopo de suporte

  • O avalanche score é o número médio de bits de saída que permanecem fixos quando um bit de entrada é invertido
    • Quanto menor a pontuação, melhor
    • Idealmente, todos os bits de saída seriam invertidos com probabilidade de 50%, resultando em score 0
  • O Prospector pode gerar funções hash de inteiros de 32 bits e 64 bits
  • As opções completas podem ser consultadas com -h
  • Por causa do compilador JIT, a própria ferramenta só oferece suporte a x86-64
    • Ainda assim, as funções hash descobertas podem ser usadas em qualquer lugar

Operações reversíveis usadas na exploração

  • O gerador monta funções aleatoriamente a partir de 9 operações reversíveis selecionadas
  • A lista de operações é a seguinte
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • Tecnicamente, x = ~x pode ser expresso como x ^= constant, mas como a chance de o gerador escolher por acaso essa constante XOR é baixa, ele é tratado como uma operação separada

Funções hash de 32 bits descobertas

  • Funções de 2 rodadas

    • Um dos grupos úteis de funções descobertas usa a estrutura xorshift-multiply-xorshift de 2 rodadas
    • TheIronBorn encontrou os parâmetros ótimos conhecidos dessa estrutura usando otimização combinatória, e o resultado é [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32 é uma permutação de 32 bits em 2 rodadas, com baixo bias e bias menor, por uma margem muito pequena, do que o finalizador de 32 bits do MurmurHash3
    • O bias exato de lowbias32 é 0.17353355999581582
    • A estrutura foi descoberta pelo Prospector, e os parâmetros foram ajustados com hill climbing e algoritmo genético
    • A função inversa lowbias32_r também é fornecida
    • prospector32 é uma função descoberta usando apenas o Prospector
    • O bias exato é 0.34968228323361017
    • Ela tem bias maior que o lowbias32 citado acima
    • Para explorar aleatoriamente constantes de multiplicação alternativas, o padrão é especificado assim
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • Funções de 3 rodadas

    • Se for adicionada mais uma rodada multiply-xorshift à mesma estrutura, é possível atingir o limite teórico de bias com parâmetros cuidadosamente escolhidos
    • triple32 tem bias exato de 0.020888578919738908
    • O README explica que ele é indistinguível de um PRF perfeito, como uma permutação aleatória de todos os inteiros de 32 bits
    • A função inversa triple32_r também é fornecida
    • A lista de constantes de 3 rodadas inclui resultados de baixo bias entre 0.020888578919738908 e cerca de 0.022984943828687553
    • triple32inc, que adiciona uma operação de incremento antes de triple32, elimina o problema hash(0) = 0 e reduz um pouco mais o bias
    • O bias exato é 0.020829410544597495
    • A função inversa triple32inc_r executa x-- no final

Medição exata de bias

  • O modo -E avalia o bias de uma função hash informada
  • Por padrão, o Prospector usa uma estimativa para avaliar o bias rapidamente
    • Essa estimativa é não determinística e tem bastante ruído nos resultados
  • Para medir o bias exato por busca exaustiva, usa-se a opção -e
  • A função a ser testada pode ser definida de duas formas
    • com -p e um padrão
    • com -l e uma biblioteca compartilhada contendo a função hash()
  • O modo com biblioteca compartilhada permite testar funções hash que não podem ser representadas pela expressão limitada de funções do Prospector
  • A entrada padrão é tratada como uma função hash de 32 bits
  • A chave -8 testa funções de 64 bits por estimativa
    • Funções hash de 64 bits demoram demais, então não existe teste exaustivo exato

hp16 para hash de 16 bits

  • Hashes de 16 bits têm restrições diferentes, então a ferramenta separada hp16 é fornecida
  • Ao contrário do Prospector de 32 e 64 bits, o hp16 é totalmente portável e pode rodar em quase qualquer sistema
  • O hp16 também pode gerar e avaliar s-boxes de 128KiB
  • Como hashes de 16 bits podem ser necessários em máquinas sem instrução rápida de multiplicação, também existem opções para omitir operações específicas durante a exploração
    • -m
    • -r

Resultados de 16 bits e cuidados com implementação em C

  • Até agora, exemplos de resultados de 16 bits são os seguintes
    • xorshift-multiply de 2 rodadas hash16_xm2: bias 0.0085905051336723701
    • xorshift-multiply de 3 rodadas hash16_xm3: bias 0.0045976709018820602
    • sem multiplicação hash16_s6: bias 0.023840118344741465
  • É apresentado que hash16_s6, sem multiplicação, é equivalente a uma forma específica de xorshift-multiply
  • Um bom hash xorshift de 3 rodadas encontrado rapidamente com hp16 -Xn3 é uma aproximação próxima de uma boa s-box de hp16 -S
  • Ao escrever operações de 16 bits em C, é preciso tomar cuidado com as regras de promoção de inteiros
    • Por exemplo, em uma implementação de 32 bits, um operando unsigned de 16 bits pode ser promovido a um inteiro signed de 32 bits
    • Nesse caso, resultados incorretos podem ocorrer em certas situações
    • O código C emitido por este programa toma cuidado para promover operações de 16 bits a unsigned int onde for necessário

Leituras relacionadas

1 comentários

 
GN⁺ 2024-05-06
Comentários do Hacker News

  • Não o conheço pessoalmente, mas gosto do código dele
    Gosto especialmente da biblioteca JSON https://github.com/skeeto/pdjson, das bibliotecas de parsing de opções https://github.com/skeeto/optparse e https://github.com/skeeto/getopt, do decodificador UTF-8 sem branches https://github.com/skeeto/branchless-utf8, da stack sem locks https://github.com/skeeto/lstack e da biblioteca de trie https://github.com/skeeto/trie
    Também gosto da preferência de licença dele: todos os projetos acima são distribuídos sob The Unlicense

    • Skeeto é lendário. Para mim, está no mesmo nível de Fabrice Bellard
      Sigo ele no GitHub há anos, e ele está sempre soltando pequenas ferramentas de nicho estranhas e interessantes. Branchless UTF-8, por exemplo, é famoso
    • Ele também é o autor do elfeed https://github.com/skeeto/elfeed, “An Emacs web feeds client”. Tirei muita inspiração daquela implementação minimalista

  • Olá, sou a pessoa que criou o MurmurHash. É um trabalho interessante, e é curioso ver como a abordagem multiplicação-shift-XOR resistiu tão bem por tanto tempo

    • O XOR-shift compensa duas fraquezas da multiplicação: os bits altos não têm bits acima deles para influenciá-los, e os bits baixos não têm bits abaixo deles pelos quais possam ser influenciados
    • Assim como o MurmurHash, estes também parecem ser pensados como hashes não criptográficos
      Dito isso, parece que as ideias de avalanche + bias deixam bastante coisa passar. Por exemplo, a função triple32 listada no final tem bias exato de 0.020888578919738908, e, quando FabriceNeyret2 a implementa no ShaderToy, sai uma imagem como esta: https://www.shadertoy.com/view/WttXWX ou https://i.imgur.com/qU2P5rx.png
      Mas, se você fizer uma simples derivada de inclinação de normal map, aparecem várias linhas de “cristal” bem visíveis. Provavelmente existe algum termo técnico para esse tipo de forma em cristas: https://i.imgur.com/IHWT1GM.png
      Além disso, acho que essa ideia toda já tem uns 5 anos: https://nullprogram.com/blog/2018/07/31/

  • Pela experiência que tive desenvolvendo boas funções hash, pensei muitas vezes na ideia de busca automática de hashes
    É bacana ver esse tipo de trabalho. Seria bom conectá-lo ao SMHasher3, uma variante muito melhorada e mais rápida da antiga suíte de testes de hash criada por Frank J. T. Wojcik, para avaliar automaticamente os resultados de saída. Para ganhar velocidade, também daria para usar só parte dos testes e falhar rápido
    Também seria interessante expandir para hashes de 64 e 128 bits, mas naturalmente o espaço de busca fica maior. Relacionado a isso, já fiz um código em NodeJS para medir avalanche em multiplicações por primos de 64 bits, quando estava escolhendo valores para usar no Rain
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • Seria interessante generalizar isso para as operações disponíveis na extensão de manipulação de bits do RISC-V. Talvez descubra funções fortes que possam ser usadas no futuro, quando essas instruções estiverem mais difundidas
    A multiplicação sem carry também pode ampliar o conjunto de operações reversíveis e é rápida em alguns hardwares existentes. CRC também tem alguma relação, mas está disponível em um conjunto mais amplo de hardware e deve ser um subconjunto estrito do que o CLMUL consegue encontrar
    Muitos usos de hash só se importam com os bits menos significativos ou mais significativos do valor do hash, então também seria interessante avaliar o bias nas faixas de bits mais/menos significativos ou os restos da divisão por vários números. Uma função que parece não ter viés considerando a saída inteira pode ficar melhor ou pior em métricas que não observam a saída completa, ou com entradas não uniformes, como texto ASCII

  • Alguém consegue explicar por que isso é legal e onde seria usado?

    • Parece ser uma ferramenta que gera uma sequência de instruções para criar uma função de hash e avalia quão boa essa função de hash é
      O indicador-alvo parece ser se, quando um bit da entrada muda, o maior número possível de bits da saída muda da forma mais aleatória possível. Ela emite o código C da melhor função de hash entre as geradas
      Então é útil quando você precisa de uma função de hash, mas acha que as funções existentes não são boas o suficiente, ou quando está pesquisando funções de hash e precisa de novas ideias de estrutura. A geração de código em si já é legal, e fazer isso aleatoriamente é o primeiro passo para algo ainda mais legal: programação genética. E, pelo visto, há cerca de 15 anos os humanos gostam de fazer computadores gastarem ciclos de CPU calculando hashes que, na maior parte, nunca serão usados
    • Funções assim são essenciais para tabelas hash. Nomes relacionados incluem mapas hash e conjuntos hash
      Tabelas hash são estruturas de dados excelentes que permitem implementar muitos algoritmos de forma simples e eficiente. Essa eficiência depende de conseguir criar, para os dados, hashes pequenos — por exemplo, de 32 ou 64 bits — e quase únicos
      Por exemplo, ao fazer hash de nomes de usuário, se você usar apenas o código ASCII da primeira letra do nome, muitos nomes de usuário serão mapeados para o mesmo número, e isso não funciona bem. Isso é chamado de colisão, e, com muitas colisões, uma tabela hash fica muito ineficiente
      Uma abordagem melhor é pegar bits de todo o nome de usuário e misturá-los de alguma forma, para que throwaway_1237 e throwaway_12373 virem números diferentes. A função de hash faz esse mapeamento, e a propriedade de avalanche descreve quão bem ela evita colisões
      Em geral, há um compromisso entre a velocidade de uma função de hash real e quão bem ela evita colisões. Funções de hash de nível mundial parecem bastante esquisitas, com multiplicações por constantes estranhas, XORs, deslocamentos etc., e é muito difícil para uma pessoa olhar para uma função obscura dessas e prever seu desempenho
      Este código tenta várias funções de hash aleatoriamente e as coloca para competir entre si. Se der certo, é legal porque pode melhorar o desempenho real de uma estrutura de dados central usada em várias linguagens e bibliotecas
    • Como é uma função de hash para inteiros, pode ser usada quando você precisa de um hash inteiro rápido em conjuntos ou mapas. Se as funções se separarem de forma suficientemente diferente, também fornecem hashes rápidos para filtros de Bloom

  • Algumas semanas atrás implementei o 1brc em Go: https://github.com/infogulch/1brc-go, e este repositório me inspirou a tentar encontrar uma função hash perfeita personalizada para que cada estação de observação caísse no seu próprio bucket sem colisões
    Aí vi a regra de que não era permitido customizar a função de hash de acordo com os dados antes do início do programa e abandonei a ideia
    Criei um aparato de teste que verificava constantes arbitrárias, valores iniciais, constantes de multiplicação, quantidades de deslocamento/rotação etc., e imprimia as melhores constantes encontradas até então com base no número de buckets com colisão e no número de colisões. Acho que reduzi até o ponto de, com uma taxa de ocupação de cerca de 40%, haver apenas um único bucket com colisão entre dois valores. Curiosamente, as constantes com melhor desempenho incluíam quantidades de posições de deslocamento parecidas, independentemente das outras constantes, então acabei codificando esses valores diretamente

  • Seria realmente interessante se fosse possível inserir seu próprio gerador de dados de entrada. Na prática, muitas vezes os dados não são binários aleatórios, mas estruturados de alguma forma, e talvez essa estrutura permita obter uma função de hash muito boa

  • Limitar-se a operações reversíveis tem algumas vantagens matemáticas, mas ao mesmo tempo exclui muita coisa
    Quando fiz algo parecido, eu estava pensando em hashing perfeito, em que o conjunto de entradas é conhecido de antemão. A abordagem comum usa um array de constantes, mas eu queria ver se dava para compactar mais, especialmente quando as entradas já são inteiros pequenos. Naturalmente, é possível fazer algo como hash -= hash >> gap_index
    Então experimentei uma lista de talvez umas 100 operações primitivas. Algumas se sobrepunham entre si, mas eram úteis quando consideradas separadamente. Depois fiquei entediado e não fiz nada do projeto

    • O que seria essa “vantagem matemática de limitar-se a operações reversíveis”, e por que operações reversíveis seriam desejáveis neste contexto?

  • Não entendi bem o que isso faz exatamente. Está procurando o melhor de todos os tempos? Se não, fico curioso por que o melhor valor muda a cada execução
    Também fico curioso se alguém conhece algum mecanismo para descobrir uma boa função de hash quando se sabe que só aparecerão valores inteiros em uma faixa específica, por exemplo de 10.000 a 200.000, para colocá-los em um número ótimo de buckets de hash

    • É uma abordagem que tenta valores aleatoriamente para encontrar o melhor entre os valores testados naquela execução
      Não é realista percorrer todo o espaço de busca em uma única execução e encontrar o ótimo absoluto, e a ordem das tentativas também é aleatória, então os valores podem variar a cada execução
      Se você só precisa de um hash “bom”, quase sempre o melhor é usar uma função de hash genérica. Se os números forem extremamente grandes e a faixa for muito pequena, dá para aplicar um deslocamento para que o valor mínimo volte a ser 0 e usar um hash menor e mais rápido. Se quiser encontrar uma “escolha perfeita” para uma faixa exata, essa abordagem aleatória provavelmente é o mais próximo disso; basta alterar os testes para serem executados nesse intervalo

  • Fico imaginando se usar a mesma constante nas duas multiplicações reduziria o tamanho do código e talvez deixasse o cálculo um pouco mais rápido
    Também atualizei a resposta no StackOverflow: https://stackoverflow.com/questions/664014/what-integer-hash...