Técnica automatizada para explorar funciones hash de enteros

 (github.com/skeeto)
3 puntos por GN⁺ 2024-05-06 | 1 comentarios | Compartir por WhatsApp
  • Hash Function Prospector es una herramienta que genera aleatoriamente grandes cantidades de funciones hash de enteros, las compila con JIT, evalúa su comportamiento de avalanche y luego imprime la mejor función actual en sintaxis C
  • La evaluación usa el avalanche score, que es la cantidad de bits de salida que, en promedio, permanecen fijos cuando se invierte un solo bit de entrada; cuanto más bajo, mejor, y el valor ideal es 0
  • El objetivo de la búsqueda son funciones hash de enteros de 32 y 64 bits; por el compilador JIT, la ejecución de la herramienta solo admite x86-64, pero las funciones encontradas pueden usarse en otros entornos
  • Las principales funciones encontradas usan una construcción xorshift-multiply-xorshift; lowbias32, de 2 rondas, muestra un sesgo ligeramente menor que el finalizer de 32 bits de MurmurHash3, y triple32, de 3 rondas, se acerca al límite teórico de sesgo
  • La medición exacta del sesgo puede realizarse para funciones de 32 bits con -E y -e; los hashes de 16 bits los maneja una herramienta separada, hp16, y hay que tener cuidado con las reglas de promoción de enteros en C

Rol de Hash Function Prospector

  • Hash Function Prospector es una herramienta automatizada de descubrimiento de funciones hash de enteros
  • Genera aleatoriamente miles de millones de funciones hash de enteros, las compila con JIT y luego evalúa su comportamiento de avalanche
  • La mejor función actual entre las generadas se imprime en sintaxis C
  • Se vincula como artículo relacionado Prospecting for Hash Functions

Criterios de evaluación y alcance soportado

  • El avalanche score es la cantidad de bits de salida que, en promedio, permanecen fijos cuando se invierte un bit de entrada
    • Cuanto más bajo sea el puntaje, mejor
    • Idealmente, todos los bits de salida se invierten con una probabilidad del 50%, por lo que el score queda en 0
  • Prospector puede generar funciones hash de enteros de 32 bits y 64 bits
  • Todas las opciones pueden consultarse en el uso de -h
  • Debido al compilador JIT, la herramienta en sí solo admite x86-64
    • Sin embargo, las funciones hash encontradas pueden usarse en cualquier lugar

Operaciones reversibles usadas en la búsqueda

  • El generador compone funciones aleatoriamente a partir de 9 operaciones reversibles seleccionadas
  • La lista de operaciones es la siguiente
    • 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)
  • Técnicamente, x = ~x puede expresarse como x ^= constant, pero como es poco probable que el generador elija por azar esa constante XOR, se trata como una operación separada

Funciones hash de 32 bits encontradas

  • Funciones de 2 rondas

    • Una de las familias de funciones útiles encontradas es una construcción xorshift-multiply-xorshift de 2 rondas
    • TheIronBorn usó optimización combinatoria para encontrar los parámetros óptimos conocidos de esta construcción, y el resultado es [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32 es una permutación de 32 bits y 2 rondas, con bajo sesgo y un sesgo apenas menor que el finalizer de 32 bits de MurmurHash3
    • El sesgo exacto de lowbias32 es 0.17353355999581582
    • La construcción fue descubierta por Prospector, y los parámetros se ajustaron con hill climbing y algoritmos genéticos
    • También se proporciona la función inversa lowbias32_r
    • prospector32 es una función descubierta usando solo Prospector
    • Su sesgo exacto es 0.34968228323361017
    • Tiene más sesgo que el lowbias32 anterior
    • Para buscar aleatoriamente constantes de multiplicación alternativas, se especifica el patrón así
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • Funciones de 3 rondas

    • Si a la misma construcción se le agrega una ronda más de multiply-xorshift, con parámetros elegidos cuidadosamente se puede alcanzar el límite teórico de sesgo
    • El sesgo exacto de triple32 es 0.020888578919738908
    • El README explica que no puede distinguirse de una PRF perfecta, como una permutación aleatoria de todos los enteros de 32 bits
    • También se proporciona la función inversa triple32_r
    • La lista de constantes de 3 rondas incluye resultados de bajo sesgo desde 0.020888578919738908 hasta aproximadamente 0.022984943828687553
    • triple32inc, que antepone una operación de incremento a triple32, rompe el problema de hash(0) = 0 y también reduce un poco más el sesgo
    • Su sesgo exacto es 0.020829410544597495
    • La función inversa triple32inc_r ejecuta x-- al final

Medición de sesgo exacto

  • El modo -E evalúa el sesgo de una función hash dada
  • Por defecto, Prospector usa una estimación para evaluar el sesgo rápidamente
    • Esta estimación es no determinista y sus resultados tienen mucho ruido
  • Para medir el sesgo exacto mediante búsqueda exhaustiva, se usa la opción -e
  • La función a examinar puede definirse de dos formas
    • Con -p y un patrón
    • Con -l y una biblioteca compartida que incluya la función hash()
  • El método de biblioteca compartida permite probar incluso funciones hash que no pueden representarse con la expresión limitada de funciones de Prospector
  • La entrada predeterminada se trata como una función hash de 32 bits
  • El switch -8 prueba funciones de 64 bits mediante el método de estimación
    • Para las funciones hash de 64 bits no hay una prueba exhaustiva exacta porque tomaría demasiado tiempo

hp16 para hashes de 16 bits

  • Para hashes de 16 bits, las restricciones son distintas, por lo que se proporciona una herramienta separada, hp16
  • A diferencia de los Prospector de 32 y 64 bits, hp16 es completamente portable y puede ejecutarse en casi cualquier sistema
  • hp16 también puede generar y evaluar s-boxes de 128 KiB
  • Como los hashes de 16 bits pueden necesitarse en máquinas sin instrucciones de multiplicación rápida, también hay opciones para omitir ciertas operaciones durante la búsqueda
    • -m
    • -r

Resultados de 16 bits y precauciones para la implementación en C

  • Algunos ejemplos de resultados actuales de 16 bits son los siguientes
    • xorshift-multiply de 2 rondas hash16_xm2: sesgo 0.0085905051336723701
    • xorshift-multiply de 3 rondas hash16_xm3: sesgo 0.0045976709018820602
    • hash16_s6 sin multiplicación: sesgo 0.023840118344741465
  • Se presenta que hash16_s6 sin multiplicación es equivalente a cierta forma xorshift-multiply
  • Un buen hash xorshift de 3 rondas encontrado con una búsqueda corta usando hp16 -Xn3 es una aproximación cercana a una buena s-box de hp16 -S
  • Al escribir operaciones de 16 bits en C, hay que tener cuidado con las reglas de promoción de enteros
    • Por ejemplo, en una implementación de 32 bits, los operandos unsigned de 16 bits pueden promocionarse a enteros signed de 32 bits
    • En ese caso, pueden producirse resultados incorrectos en ciertas situaciones
    • El código C que imprime este programa se asegura de promocionar las operaciones de 16 bits a unsigned int donde sea necesario

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-05-06
Opiniones de Hacker News

  • No lo conozco personalmente, pero me gusta su código.
    En particular, me gustan la biblioteca JSON https://github.com/skeeto/pdjson, las bibliotecas de parseo de opciones https://github.com/skeeto/optparse y https://github.com/skeeto/getopt, el decodificador UTF-8 sin bifurcaciones https://github.com/skeeto/branchless-utf8, la pila sin locks https://github.com/skeeto/lstack y la biblioteca de tries https://github.com/skeeto/trie.
    También me gusta su preferencia de licencia: todos esos proyectos se distribuyen bajo The Unlicense.

    • Skeeto es una leyenda. Para mí está al nivel de Fabrice Bellard.
      Lo sigo en GitHub desde hace años y siempre va sacando herramientas pequeñas, raras y de nicho. Por ejemplo, Branchless UTF-8 es bastante conocido.
    • También es el autor de elfeed https://github.com/skeeto/elfeed, “An Emacs web feeds client”, y me inspiré mucho en su implementación minimalista.

  • Hola, soy quien creó MurmurHash. Es un trabajo interesante, y me resulta curioso que el enfoque multiplicación-shift-XOR haya aguantado tan bien durante tanto tiempo.

    • El XOR-shift compensa dos debilidades de la multiplicación: los bits altos no tienen bits por encima que puedan influir en ellos, y los bits bajos no tienen bits por debajo de los que puedan recibir influencia.
    • Al igual que MurmurHash, estos también parecen estar pensados como hashes no criptográficos.
      Dicho eso, parece que la idea de avalanche + bias deja fuera bastantes cosas. Por ejemplo, la función triple32 listada al final tiene un bias exacto de 0.020888578919738908, y si FabriceNeyret2 la implementa en ShaderToy se ve una imagen como esta: https://www.shadertoy.com/view/WttXWX o https://i.imgur.com/qU2P5rx.png
      Pero si se hace una simple derivada de la pendiente de un normal map, aparecen bastantes líneas de “cristales” visibles. Probablemente exista algún término técnico para este tipo de formas de crestas: https://i.imgur.com/IHWT1GM.png
      Además, creo que toda esta idea ya tiene unos 5 años: https://nullprogram.com/blog/2018/07/31/

  • Por mi experiencia desarrollando buenas funciones hash, he pensado muchas veces en la idea de una búsqueda automática de hashes.
    Es genial ver este tipo de trabajo. Sería bueno conectarlo con SMHasher3, una variante mucho más mejorada y rápida de la antigua suite de pruebas de hashes creada por Frank J. T. Wojcik, para evaluar automáticamente los resultados. Para ganar velocidad, también se podrían usar solo algunas pruebas y fallar rápido.
    También sería bueno extenderlo a hashes de 64 y 128 bits, aunque obviamente el espacio de búsqueda crecería. Relacionado con eso, alguna vez hice código en NodeJS para medir el avalanche en multiplicaciones por primos de 64 bits, con el fin de elegir valores para usar en Rain.
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • Sería interesante generalizar esto a las operaciones disponibles en la extensión de manipulación de bits de RISC-V. Quizá se descubran funciones fuertes que puedan usarse más adelante, cuando esas instrucciones estén más difundidas.
    La multiplicación sin acarreo también puede ampliar el conjunto de operaciones reversibles, y en cierto hardware existente es rápida. CRC también está relacionado en cierta medida, pero está disponible en un conjunto más amplio de hardware y debería ser un subconjunto estricto de lo que CLMUL puede encontrar.
    Como muchos usos de los hashes solo se preocupan por los bits menos significativos o más significativos del valor hash, también sería interesante evaluar el bias en los rangos de bits más/menos significativos, o los restos al dividir por varios números. Una función que parece no tener sesgo al mirar toda la salida puede mejorar o empeorar en métricas que no observan toda la salida, o con entradas no uniformes como texto ASCII.

  • ¿Alguien puede explicar por qué esto es genial y dónde se usa?

    • Parece una herramienta para generar una secuencia de instrucciones para crear una función hash y evaluar qué tan buena es esa función hash.
      El objetivo parece ser que, cuando cambia un solo bit de entrada, cambien de forma lo más aleatoria posible la mayor cantidad posible de bits de salida. Imprime el código C de la mejor función hash entre las generadas.
      Así que es útil cuando necesitas una función hash y crees que las funciones existentes no son lo suficientemente buenas, o cuando investigas funciones hash y necesitas ideas para nuevas estructuras. La generación de código en sí ya es genial, y hacerlo al azar es el primer paso hacia la programación genética, que es aún más genial. Además, parece que desde hace unos 15 años a los humanos les gusta hacer que las computadoras gasten ciclos de CPU calculando hashes que en su mayoría no se van a usar.
    • Este tipo de funciones son esenciales para las tablas hash. Nombres relacionados: mapas hash y conjuntos hash.
      Una tabla hash es una excelente estructura de datos que permite implementar muchos algoritmos de forma simple y eficiente. Esa eficiencia depende de poder crear un hash pequeño para los datos —por ejemplo, de 32 o 64 bits— y casi único.
      Por ejemplo, si al hashear nombres de usuario solo usas el código ASCII de la primera letra del nombre, muchos nombres de usuario se mapearán al mismo número y no funcionará bien. A eso se le llama colisión, y si hay muchas colisiones, la tabla hash se vuelve muy ineficiente.
      Una mejor forma es tomar bits de todo el nombre de usuario y mezclarlos de alguna manera para que throwaway_1237 y throwaway_12373 terminen siendo números distintos. La función hash realiza este mapeo, y la propiedad avalanche describe qué tan bien evita colisiones.
      Normalmente hay un compromiso entre qué tan rápida es una función hash real y qué tan bien evita colisiones. Las funciones hash de primer nivel se ven bastante extrañas: multiplican por constantes raras, hacen XOR, shifts, etc.; y para una persona es muy difícil mirar una función tan críptica y estimar su rendimiento.
      Este código prueba al azar varias funciones hash y las hace competir entre sí. Si tiene éxito, puede mejorar el rendimiento real de una estructura de datos central usada en muchos lenguajes y bibliotecas, así que es genial.
    • Como es una función hash para enteros, se puede usar cuando se necesita un hash entero rápido en conjuntos o mapas. Si las funciones se separan lo suficiente entre sí, también proporciona hashes rápidos para filtros de Bloom.

  • Hace unas semanas implementé 1brc en Go: https://github.com/infogulch/1brc-go, y ver este repositorio me inspiró a intentar encontrar una función hash perfecta personalizada para que cada estación de observación cayera en su propio bucket sin colisiones.
    Luego vi la regla de que no se podía personalizar la función hash según los datos antes de iniciar el programa, así que descarté la idea.
    Construí un banco de pruebas que verificaba constantes arbitrarias, valores iniciales, constantes de multiplicación, cantidades de shift/rotación, etc., e imprimía las mejores constantes encontradas hasta el momento según la cantidad de buckets con colisiones y la cantidad de colisiones. Creo que, con una tasa de llenado de alrededor del 40%, lo reduje a que solo un bucket tuviera una colisión de dos valores. Curiosamente, las constantes con mejor rendimiento incluían cantidades de posiciones de shift similares, independientemente de las demás constantes, así que terminé hardcodeando esos valores.

  • Sería muy interesante si se pudiera incorporar un generador de datos de entrada propio. En la práctica, muchos datos no son binarios aleatorios, sino que están estructurados de alguna manera, y tal vez se pueda obtener una función hash muy buena gracias a esa estructura.

  • Limitarse a operaciones reversibles tiene ventajas matemáticas, pero al mismo tiempo excluye muchas cosas.
    Cuando hice algo parecido, estaba pensando en hashing perfecto, donde se conoce de antemano el conjunto de entradas. El enfoque común usa un arreglo de constantes, pero quería ver si podía compactarlo más, especialmente si las entradas ya eran enteros pequeños. Por supuesto, algo como hash -= hash >> gap_index lo permite.
    Así que probé una lista de quizá unas 100 operaciones primitivas. Algunas se superponían entre sí, pero eran útiles si se las pensaba por separado. Luego me aburrí y no hice nada con el proyecto.

    • ¿Cuáles son esas “ventajas matemáticas de limitarse a operaciones reversibles” y por qué son deseables las operaciones reversibles en este contexto?

  • No entiendo muy bien qué hace exactamente. ¿Busca el mejor valor histórico? Si no es así, me pregunto por qué el mejor valor cambia en cada ejecución.
    También me pregunto si alguien conoce un mecanismo para descubrir una buena función hash cuando se sabe que solo aparecerán valores enteros de un rango específico, por ejemplo entre 10,000 y 200,000, y se quiere meterlos en una cantidad óptima de buckets hash.

    • Es un método que prueba valores al azar para encontrar el mejor entre los valores probados en esa ejecución.
      No es realista recorrer todo el espacio de búsqueda en una sola ejecución para encontrar el óptimo absoluto, y como el orden de prueba también es aleatorio, los valores pueden cambiar entre ejecuciones.
      Si solo necesitas un hash “bueno”, casi siempre lo mejor es usar una función hash general. Si los números son extremadamente grandes y el rango es muy pequeño, puedes aplicar un offset para que el valor mínimo vuelva a ser 0 y así usar un hash más pequeño y rápido. Si quieres encontrar la “opción perfecta” para un rango exacto, creo que este tipo de enfoque aleatorio es lo más cercano; bastaría con modificar las pruebas para que se ejecuten sobre ese intervalo.

  • Me pregunto si usar la misma constante en las dos multiplicaciones podría reducir el tamaño del código y quizá hacer que el cálculo sea un poco más rápido.
    También actualicé la respuesta de StackOverflow: https://stackoverflow.com/questions/664014/what-integer-hash...