El problema al que me enfrento es que la función devuelve key como void * .

No es asi. No devuelve nada ( void ). El resultado del hash se registra en el búfer que especifique (un puntero a) a través del último argumento. Para MurmurHash3_x86_32() , tiene más sentido que sea un puntero a uint32_t .

Como el tamaño de mi tabla hash sería más pequeño que el hash más grande que puede generar, necesito colocarlo en el rango de la tabla [0, N-1]. La solución más fácil parece ser usar el operador %. Pero como se sabe que es un operador lento, me pregunto si hay una forma más rápida de resolver el problema.

El % no solo es la solución más fácil, sino la más habitual. "Lento" es relativo: % es más lento que + , pero mucho, mucho más rápido que una llamada a MurmurHash3_x86_32() .

Una sugerencia interesante que encontré [...] sugiere [usar un tamaño de tabla de potencia de dos y calcular el módulo a través del operador & ]

Tenga en cuenta que, contrariamente a la afirmación en la respuesta SO, de hecho, esto no depende en absoluto de la representación del complemento a dos.

Mi problema con esto es que en las CPU más nuevas, a veces (¿o es la mayoría de las veces?), el rendimiento se degrada alrededor de los tamaños 2^n, IIRC, debido a las líneas de caché de múltiples vías. (Este enlace proporciona una ilustración sobre las inserciones Big Memory, Parte 3.5: ¡Google sparsehash!).

La degradación del rendimiento descrita en el informe que vinculó se atribuye a la repetición de hash, lo que parece bastante plausible. Eso no tiene nada que ver con las operaciones por las que preguntas. Es concebible que la asociatividad de la memoria caché (falta de) pueda afectar el rendimiento de las tablas hash grandes, pero probablemente no más de lo que suele afectar tener tablas hash grandes. Los patrones de acceso a la memoria inherentes al uso de una tabla hash producen naturalmente una localidad de caché deficiente. Ese es prácticamente el punto .

Por el momento, las ventajas de murmur3 parecen quedar anuladas por problemas relacionados con el hardware y la conocida ineficiencia del operador %. Como el rendimiento es una limitación, solicito soluciones más rápidas y de baja latencia para mis requisitos, incluso si no es MurmurHash3_x86_32.

Estás pensando demasiado en esto. La falta de uso efectivo de la caché de su CPU es simplemente un precio que paga por usar una tabla hash grande. No está asociado con la función hash (siempre y cuando la función hash haga bien su trabajo). El costo de una sola operación aritmética, ya sea % o & , no se notará en comparación con el costo de calcular un hash para operar , por lo que poco importa cuál elija. Si desea una pequeña ventaja para esa operación, use una tabla de tamaño de potencia de dos y el operador & . Por otro lado, eso descarta algunos de los bits de hash que tanto trabajo le costó calcular. Considere, en cambio, elegir un tamaño de tabla hash principal y el operador % ; luego, todos los bits hash contribuirán a la selección del segmento, lo que puede mejorar su margen.