Mapa hash C / C ++ de alto rendimiento (tabla, diccionario) [cerrado]

Necesito mapear claves primitivas (int, tal vez long) para estructurar valores en una estructura de datos de mapa hash de alto rendimiento.

Mi programa tendrá algunos cientos de estos mapas, y cada mapa generalmente tendrá como máximo algunos miles de entradas. Sin embargo, los mapas se "actualizarán" o "agitarán" constantemente; imaginar procesar millones de addy deletemensajes de un segundo.

¿Qué bibliotecas en C o C ++ tienen una estructura de datos que se ajusta a este caso de uso? O, ¿cómo recomendarías construir el tuyo propio? ¡Gracias!

Le recomendaría que pruebe Google SparseHash (o la versión C11 de Google SparseHash-c11 ) y vea si se adapta a sus necesidades. Tienen una implementación de memoria eficiente, así como una optimizada para la velocidad. Hice un punto de referencia hace mucho tiempo, fue la mejor implementación de tabla hash disponible en términos de velocidad (sin embargo, con inconvenientes).

¿Qué bibliotecas en C o C ++ tienen una estructura de datos que se ajusta a este caso de uso? O, ¿cómo recomendarías construir el tuyo propio? ¡Gracias!

Echa un vistazo a las matrices Judy LGPL . Nunca me utilicé, pero me lo anunciaron en pocas ocasiones.

También puede intentar comparar contenedores STL (std :: hash_map, etc.). Dependiendo de la plataforma / implementación y el ajuste del código fuente (preasignar tanto como sea posible, la administración de memoria dinámica es costosa), podrían tener el rendimiento suficiente.

Además, si el rendimiento de la solución final supera el costo de la solución, puede intentar ordenar el sistema con suficiente RAM para poner todo en arreglos simples. El rendimiento de acceso por índice es inmejorable.

Las operaciones de agregar / eliminar son mucho (100 veces) más frecuentes que la operación de obtención.

Eso sugiere que es posible que desee concentrarse primero en mejorar los algoritmos. Si los datos solo se escriben, no se leen, ¿por qué escribirlos?

Simplemente use boost::unordered_map(o tr1etc.) de forma predeterminada. Luego, perfile tu código y fíjate si ese código es el cuello de botella. Solo entonces sugeriría analizar con precisión sus requisitos para encontrar un sustituto más rápido.

Si tiene un programa multiproceso, puede encontrar algunas tablas hash útiles en la biblioteca de bloques de construcción de subprocesos de Intel . Por ejemplo, tbb :: concurrent_unordered_map tiene la misma API que std :: unordered_map, pero sus funciones principales son seguras para subprocesos.

También eche un vistazo a la biblioteca de locura de Facebook , tiene una tabla hash concurrente de alto rendimiento y una lista de omisión .

khash es muy eficiente. Hay un punto de referencia detallado del autor: https://atteriouschaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ y también muestra que khash supera a muchas otras bibliotecas hash.

de fuentes de Android (por lo que Apache 2 tiene licencia)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

mire hashmap.c, elija include / cutils / hashmap.h, si no necesita seguridad para subprocesos, puede eliminar el código mutex, una implementación de muestra está en libcutils / str_parms.c

Primero verifique si las soluciones existentes como libmemcache se ajustan a sus necesidades.

Si no ...

Los mapas hash parecen ser la respuesta definitiva a sus necesidades. Proporciona o (1) búsqueda basada en las claves. La mayoría de las bibliotecas STL proporcionan algún tipo de hash en estos días. Así que usa el que te proporciona tu plataforma.

Una vez que termine esa parte, debe probar la solución para ver si el algoritmo de hash predeterminado es lo suficientemente bueno en cuanto a rendimiento para sus necesidades.

Si no es así, debería explorar algunos buenos algoritmos de hash rápido que se encuentran en la red.

1. buen número primo multiplicar algo
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

Si esto no es lo suficientemente bueno, puede lanzar un módulo hash por su cuenta, que solucione el problema que vio con los contenedores STL que ha probado y uno de los algoritmos hash anteriores. Asegúrese de publicar los resultados en algún lugar.

Ah, y es interesante que tenga múltiples mapas ... quizás pueda simplificar al tener su clave como un número de 64 bits con los bits altos utilizados para distinguir a qué mapa pertenece y agregar todos los pares de valores de clave a un hash gigante. He visto hashes que tienen cientos de miles de símbolos que funcionan perfectamente bien en el algoritmo básico de hash de números primos bastante bien.

Puede comprobar cómo funciona esa solución en comparación con cientos de mapas ... creo que podría ser mejor desde el punto de vista del perfil de la memoria ... por favor publique los resultados en algún lugar si puede hacer este ejercicio

Creo que más que el algoritmo hash, podría ser la adición / eliminación constante de memoria (¿se puede evitar?) Y el perfil de uso de caché de la CPU lo que podría ser más crucial para el rendimiento de su aplicación.

buena suerte

Pruebe las tablas hash de varias plantillas de contenedores . Tiene closed_hash_mapaproximadamente la misma velocidad que la de Google dense_hash_map, pero es más fácil de usar (sin restricciones en los valores contenidos) y también tiene otras ventajas.

Sugeriría uthash . Simplemente incluya y #include "uthash.h"luego agregue UT_hash_handlea la estructura y elija uno o más campos en su estructura para que actúen como clave. Unas palabras sobre el rendimiento aquí .

http://incise.org/hash-table-benchmarks.html gcc tiene una muy buena implementación. Sin embargo, tenga en cuenta que debe respetar una decisión estándar muy mala:

Si ocurre un refrito, todos los iteradores se invalidan, pero las referencias y punteros a elementos individuales siguen siendo válidos. Si no ocurre ningún refrito real, no hay cambios.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

Esto significa que básicamente el estándar dice que la implementación DEBE ESTAR basada en listas enlazadas. Evita el direccionamiento abierto que tiene un mejor rendimiento.

Creo que Google Sparse utiliza direcciones abiertas, aunque en estos puntos de referencia solo la versión densa supera a la competencia. Sin embargo, la versión dispersa supera a toda la competencia en el uso de memoria. (tampoco tiene meseta, línea recta pura con número de elementos)