tablas - Mapa hash C/C++ de super alto rendimiento(tabla, diccionario)
tablas hash c++ (10)
Necesito mapear claves primitivas (int, quizás largas) para estructurar valores en una estructura de datos de mapas hash de alto rendimiento.
Mi programa tendrá unos cientos de estos mapas, y cada mapa generalmente tendrá como mucho unos miles de entradas. Sin embargo, los mapas serán "refrescantes" o "agitados" constantemente; Imagine procesar millones de mensajes de add y delete 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? ¡Gracias!
¿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? ¡Gracias!
Echa un vistazo a las matrices Judy LGPL. Nunca me usé, pero me lo anunciaron en pocas ocasiones.
También puede intentar comparar los contenedores STL (std :: hash_map, etc.). Dependiendo de la plataforma / implementación y el ajuste del código fuente (preasignar tanto como pueda la administración de memoria dinámica es costoso) podrían ser lo suficientemente eficaces.
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 del acceso por índice es inmejorable.
Las operaciones de agregar / eliminar son mucho (100x) más frecuentes que la operación get.
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?
Primero compruebe si las soluciones existentes como libmemcache se ajustan a sus necesidades.
Si no ...
Los mapas hash parecen ser la respuesta definitiva a su requerimiento. 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. Entonces usa el proporcionado por tu plataforma.
Una vez que se hace 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í, debes explorar algunos buenos algoritmos rápidos de hash que se encuentran en la red
- buen viejo número primo multiplicar algo
- http://www.azillionmonkeys.com/qed/hash.html
- http://burtleburtle.net/bob/
- http://code.google.com/p/google-sparsehash/
Si esto no es lo suficientemente bueno, puede rodar un módulo de hash usted mismo, que corrige el problema que vio con los contenedores de STL que ha probado, y uno de los algoritmos de hash anteriores. Asegúrese de publicar los resultados en alguna parte.
Ah, y es interesante que tengas varios mapas ... quizás puedas simplificar teniendo tu clave como un número de 64 bits con los bits más altos para distinguir a qué mapa pertenece y agregar todos los pares de valores clave a un hash gigante. He visto hashes que tienen cien mil o más símbolos que funcionan perfectamente bien en el algoritmo básico de hash de números primos.
Puedes comprobar el rendimiento de esa solución en comparación con cientos de mapas ... creo que podría ser mejor desde el punto de vista de la creación de perfiles de memoria ... por favor, publica los resultados en algún lugar si logras hacer este ejercicio
Creo que más que el algoritmo hash podría ser la constante agregar / eliminar memoria (¿se puede evitar?) Y el perfil de uso de la memoria caché de la CPU que podría ser más crucial para el rendimiento de la aplicación
buena suerte
Pruebe las tablas hash de las plantillas de varios contenedores . Su closed_hash_map es aproximadamente la misma velocidad que dense_hash_map de Google, pero es más fácil de usar (sin restricciones en los valores contenidos) y también tiene otras ventajas.
Si tiene un programa multiproceso, puede encontrar algunas tablas hash útiles en la biblioteca de bloques de creación de hilos de intel . Por ejemplo, tbb :: concurrent_unordered_map tiene la misma API que std :: unordered_map, pero sus funciones principales son seguras para hilos.
También eche un vistazo a la biblioteca de locura de Facebook, tiene una tabla de hash concurrente de alto rendimiento y lista de omisiones .
Solo use boost::unordered_map tr1 (o tr1 etc.) de forma predeterminada. Luego perfila tu código y ve si ese código es el cuello de botella. Solo entonces le sugiero que analice con precisión sus requisitos para encontrar un sustituto más rápido.
Te recomendaría probar Google SparseHash (o la versión C11 de Google SparseHash-c11 ) y ver si se adapta a tus 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 hashtable disponible en términos de velocidad (sin embargo, con inconvenientes).
de fuentes de Android (por lo tanto Apache 2 con licencia)
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
mira hashmap.c, elige include / cutils / hashmap.h, si no necesitas seguridad de subprocesos puedes eliminar el código mutex, una implementación de muestra está en libcutils / str_parms.c
khash es muy eficiente. Hay un punto de referencia detallado del autor: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ y también muestra que khash supera a muchas otras bibliotecas hash.
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 una repetición, todos los iteradores son invalidados, pero las referencias y punteros a los elementos individuales siguen siendo válidos. Si no ocurre una repetición real, no hay cambios.
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
Esto significa básicamente que el estándar dice que la implementación DEBE estar basada en listas vinculadas. Impide el direccionamiento abierto que tiene un mejor rendimiento.
Creo que Google Sparse utiliza el direccionamiento abierto, aunque en estos puntos de referencia solo la versión densa supera a la competencia. Sin embargo, la versión dispersa supera a toda competencia en el uso de la memoria. (también no tiene ninguna meseta, número de elementos puros en línea recta)