¿Debería almacenar en caché el código hash de una cadena STL utilizada como clave hash?

Question

He estado haciendo algunos análisis de rendimiento en el software que desarrollo, y he encontrado que las búsquedas en un diccionario global de URL toman aproximadamente el 10% del tiempo de fase de "carga" de la aplicación. El diccionario se implementa como C++ STL std :: map, que tiene búsquedas O (lg n). Voy a moverlo a hash_map, que tiene aproximadamente búsquedas de tiempo fijo. La clase stl string no tiene una propiedad de código hash, y ciertamente no almacena en caché un código hash. Eso significa que cada búsqueda requiere volver a generar el código hash.

Soy escéptico de que el almacenamiento en memoria caché del código hash valga la pena. Significaría cambiar muchas líneas de código para usar una nueva clase de cadena con una propiedad de código hash en caché. Dado que la implementación actual registra (n) comparaciones completas de cadenas en cada búsqueda, creo que reducirla a básicamente un recorrido de cadenas (por la función de hash) por búsqueda es una gran ganancia.

¿Alguien tiene experiencia con los códigos hash de cadena de almacenamiento en caché? ¿Ha probado alguna vez que vale la pena el esfuerzo?

Answer 1

No tengo experiencia con los códigos hash de almacenamiento en caché, pero he hecho algunos trabajos recientemente convirtiendo std::map en std::tr1::unordered_map. Dos pensamientos vienen a la mente. Primero, intente realizar un perfil de ese cambio relativamente simple primero, porque a veces empeora las cosas, dependiendo de lo que esté haciendo su código. Podría darle suficiente aceleración por sí mismo antes de intentar optimizar aún más. En segundo lugar, ¿qué dice su perfilador sobre el otro 90% de su tiempo de inicialización? Incluso si optimizó las cosas del diccionario global a 0 veces, como mucho mejorará el rendimiento en un 10%.

Answer 2

Una palabra de advertencia.

Mientras que un mapa de hash puede tener búsquedas de tiempo fijo, también puede tener búsquedas de O (N). Si bien no es un caso común, sucede.

Por lo tanto, aunque siempre tiene que pagar por el tiempo O (log N) en un mapa, también se le garantiza que no será peor.

Answer 3

Por supuesto, necesitará un perfil para verificar sus resultados. Cambie a un mapa hash y luego vea dónde pasa la mayor parte de su tiempo. A menos que estés haciendo un hash con las teclas de la izquierda y la derecha, dudo que la mayor parte de tu tiempo se gaste allí. Hashing está destinado a ser una operación rápida, de lo contrario, un mapa hash no tendría ventajas sobre un contenedor ordenado.

El propio compilador sabrá si una cadena no ha sido modificada, y probablemente pueda almacenar el resultado en caché (dentro del mismo ámbito). Dicho esto, usted no desea heredar de std::string; Las clases de STL no estaban hechas para eso.

Más bien, hacer una std::pair y pasan alrededor que:

std::pair<const std::string, const size_t> string_hash_pair;

te había entonces necesidad de sobrecargar el (pasando por Boost aquí, no TR1; no sé lo similares que son) hash_value función de su tipo, en el mismo espacio de nombres como el par se define:

size_t hash_value(const string_hash_pair& pPair) 
{ 
    return pPair.second; // don't actually hash 
} 

Y eso es todo. Tenga en cuenta que en el par, ambos string y size_t son inmutables. Esto es porque si cambia el string, su hash es incorrecto. Así que lo hacemos const, y también podemos hacer el hash const también.

usted querrá una función auxiliar:

string_hash_pair make_string_hash(const std::string& pStr) 
{ 
    return std::make_pair(pStr, boost::hash_value(pStr)); 
} 

Ahora bien, si usted va a utilizar una cadena de look-ups, acaba de hacer un par de ella y se obtiene hash constante en el tiempo.

Dicho esto, realmente dudo que este trabajo sea necesario. Las funciones hash realmente son triviales, por lo general. Además, no haga su propio. Use un hash comprobado preexistente; es bastante fácil hacer un hash horrible.

Answer 4

Cuando se compara el mapa hash al mapa, también tratar un trie, o estructura de datos relacionado (lo que puede obtener fuera de la plataforma):

Trie implementation

Desafortunadamente A continuación, puede pasar mucho tiempo preocupándose por la caché-amistad. En ese sentido, un Trie es similar al árbol que ya tienes, y un mapa hash probablemente se comportará mejor que un árbol ingenuamente asignado.

Además, estoy un poco confundido por la pregunta. Si está buscando la misma cadena objeto varias veces, de modo que vale la pena almacenar en caché su valor hash, ¿no debería simplemente estar almacenando en caché el resultado de la búsqueda? El objetivo de una tabla hash es que los diferentes objetos que tienen valor hash igual al mismo valor. Si no está computando el mismo hash varias veces desde distintas cadenas que contienen los mismos caracteres, entonces su tabla hash probablemente no está haciendo su trabajo.

Si se refiere al almacenamiento en caché de los valores de las claves que ya están en la tabla hash, eso depende de la tabla hash.

Answer 5

Realicé algunas comparaciones de un conjunto establecido y desordenado con 4k - 64k cadenas en mi diccionario.

Encontré que un std :: set y unordered_set tenían aproximadamente el mismo tiempo de ejecución en mi situación porque el cálculo de hash_value tomó aproximadamente el 80% del tiempo de ejecución para el conjunto desordenado.

empequeñecía el ahorro de búsqueda (se usa impulso :: hash_value para std :: string Fwiw)

tu caso es distinto, y para los casos generales diría perfil y no se deje engañar por los ajustes a escala teóricos que no lo hacen cuenta para la arquitectura de la CPU, etc. Un mapa hash puede correr más lento debido al costo de hash y consumirá más memoria.

Mi caso de uso es que almaceno información durante mucho tiempo y recibe actualizaciones regularmente que no cambian el hash de información_id pero pueden cambiar otro contenido.

Cada actualización se pasa luego a mi función de búsqueda para decidir si necesito notificar externamente esta actualización.

La lista de information_ids a notificar se encuentra en esta búsqueda y puede cambiar independientemente de la información.

Al almacenar en caché el hash para el information_id, es probable que se reutilice 10 veces durante la vida útil de la información.

Mi cambio de dos líneas de caché de tiempo de ejecución de la picadillo mejorado de unordered_set por> x8 conjunto

prueba: Benched en MSVC 2012 Update 4 entradas 1M levantaron la vista 10 veces cada uno contra un 4k y 64k diccionario: Todos menos 10 cheques son pierde en 4k, a 500 golpes para 64k (más aardvarks :))

conjunto: 1373 ms/1938 ms

multiset: 1376 ms/1913 ms

unordered_set i 64k nitial factor de cubo/carga 0,5: 168 ms/362 ms

unordered_set 4k/1.0: 331 ms/452 ms

cf pre-caché

unordered_set 64k/0,5: 1519 ms/1881 ms

Fwiw mismas cosas funcionan contra MinGW 4.9.1 -O3

conjunto: 2003 ms/ms 2490

multiconjuntos: 1978 ms/ms 2306

factor de 64k/cubo de carga 0.5 inicial unordered_set: 140 ms/605 ms

unordered_set 4k/1.0: 318 ms/683 ms

cf pre-cache

unordered_set 64k/0.5: 1619 ms/2455 ms