400390102. Contenedores de Hash en STL C++ y sus Prestaciones

Si estamos escribiendo aplicaciones comerciales, códigos back-end para sitios web, juegos, o prácticamente cualquier otra aplicación moderna, es probable que necesitemos tener acceso de forma rápida a grandes cantidades de datos y a realizar cálculos en base a dichos datos.

Por ejemplo, en Advertising.com tenemos que realizar con rapidez complejos cálculos matemáticos en base a enormes cantidades de datos que se hallan en la memoria, para así poder elegir los anuncios más pertinentes para mostrar a los visitantes del sitio web.

Existen, desde luego, muchas y distintas técnicas de perfilado y optimización que podemos utilizar una vez hemos completado la aplicación. Pero incluso aunque creamos que “la optimización prematura es la causa de todos los males”, conviene que empecemos a pensar lo antes posible en las prestaciones de la aplicación. ¿Por qué? Porque la elección correcta de las estructuras de datos es una decisión arquitectónica clave para las aplicaciones de prestaciones críticas.

Afortunadamente, para los programadores de C++, la Biblioteca de Plantillas Estándar de C++ ofrece una enorme cantidad de estructuras de datos que se usan con frecuencia y que se pueden incorporar fácilmente a la mayoría de los programas. Muchas de las estructuras de datos más sencillas son bien conocidas: Los intercambios de prestaciones entre vectores, listas enlazadas y colas se enseñan en los cursos de introducción a la ciencia de la computación.

Es también sencillo entender y usar contenedores asociativos clasificados como mapas y conjuntos sin saber lo que realmente contienen, especialmente si ha pasado algún tiempo desde la última vez que examinamos los detalles de los algoritmos de Árboles Rojos/Negros que normalmente los sustentan.

Pero la comprensión de los detalles de implementación y los intercambios en el diseño es fundamental para usar algunas de las estructuras más eficaces y potentes de datos que se encuentran disponibles en las distribuciones de STL —estructuras basadas en hash y que incluyen hash_map, hash_set, hash_multimap, y hash_multiset.

Aunque estas estructuras todavía no son parte del Estándar de C++, vienen incluidas en muchos paquetes de STL, incluida la versión SGI que se envía con la mayoría de las distribuciones de Linux. Se incluirán también en TR1 con los nombres ligeramente diferentes de unordered_map, unordered_multimap, unordered_set, y unordered_multiset. Los ejemplos que se incluyen en el presente artículo usan la implementación SGI STL. Pero incluso si utilizamos un STL distinto, es probable que las implementaciones sean similares.

Cada una de estas estructuras de datos ofrece una funcionalidad similar a sus equivalentes no basados en hash.

– hash_maps almacena parejas de clave/valor que tienen claves exclusivas.
– hash_sets almacena valores exclusivos.
– hash_multimaps almacena parejas de clave/valor con claves no exclusivas.
– hash_multisets almacena valores no exclusivos.

Con muchas aplicaciones, la velocidad que se obtiene al usar, por ejemplo, hash_maps en lugar de mapas normales es significativa. En teoría, los contenedores basados en hash pueden ofrecer inserción, eliminación y acceso en tiempo constante a cualquier valor que se halle en los contenedores. Por el contrario, los Árboles Rojos/Negros que alimentan los mapas, conjuntos, mapas y conjuntos múltiples de STL necesitan de un tiempo O(log n) para operaciones equivalentes.

Factores que influyen en las prestaciones

Pero los contenedores basados en hash no son una garantía, y el tiempo de reloj varía drásticamente dependiendo de la función hash empleada, el número de objetos almacenados en el contenedor, el tiempo que se tarda en comprobar los valores para la igualdad y otros factores. Saber como interactúan estos factores es esencial para aprovechar las mejoras en las prestaciones que ofrecen los contenedores de hash.

Para entender el efecto que cada uno de estos factores tiene en las prestaciones, hemos de entender cómo se implementan los contenedores basados en hash. Pensemos en los conjuntos de hash.

Los conjuntos de hash se pueden considerar como matrices de listados enlazados. Cada elemento de la matriz, denominado en la figura 1 como B0…B4, es un «cubo.» Cuando se inserta un nuevo elemento en el conjunto de hash, se computa el valor de hash del elemento. A continuación, se computa el número del cubo tomando el valor de hash mediante la factorización modular del número de cubos.

En la figura 1, el elemento A, cuyo valor hash es 7, se almacena en el cubo 2 (Valor de Hash de 7 factorización modular 5 cubos=cubo 2). Cuando invocamos find(A) para comprobar si el elemento A está en el conjunto de hash, el programa computa el valor hash de 7 para A, y busca en el cubo 2 para ver si A está allí. Como sólo hay un elemento en el cubo 2, es relativamente rápido.

Pero incluso aunque sólo haya un elemento en un cubo, find() sigue teniendo que comprobar si es el elemento en cuestión que buscamos, lo que conlleva una invocación a operator==. Si la comparación de igualdad es lenta, las prestaciones del contenedor de hash se degradan.

Figura 1: Elementos de la matriz

Supongamos ahora que insertamos otro elemento, el elemento Z, en el conjunto de hash. Si el elemento Z tiene un valor hash de 12, y no aumentamos el número de cubos en el conjunto de hash, en ese caso el elemento Z también termina en el cubo 2. (Figura 2). Cuando hay más de un elemento en un cubo de hash, find() puede hacerse más lento. Si invocamos find(Z), el programa busca de nuevo en el cubo 2, pero tiene que examinar primero el elemento A antes de ir al siguiente elemento de las lista enlazada, y de decirnos que Z está de hecho en nuestro conjunto hash. Afortunadamente, conforme va aumentando el número de elementos en nuestro conjunto de hash, aumenta también de forma automática el número de cubos. Eso reduce la posibilidad de que dos elementos con distintos valores de hash terminen en el mismo cubo.

Figura 2: Inserción de otro elemento en un conjunto de hash.

Pero, ¿qué pasa si teníamos muchos elementos con el mismo valor de hash, como en el listado número 1? Cuando dos elementos distintos se “reducen” (hash) al mismo valor, hay una “colisión hash”. Estos elementos siempre terminan en el mismo cubo, independientemente del número de cubos que tengamos, lo que degrada de forma significativa las prestaciones de la colección.

Si las colisiones de hash se producen con la suficiente frecuencia, el hallazgo de elementos en el contenedor se convierte de manera efectiva en O(n) en vez de O(1) porque tenemos que atravesar las listas enlazadas que forman los cubos de hash.


struct terribleHasher

size_t operator()(const myClass& myObj) const

return 1;

;


Listado número 1

Además de ser relativamente exclusivos, los valores hash deberían ser muy rápidos de computar. SGI STL ofrece algunas funciones hash básicas. La mayoría de los primitivos se reducen a sí mismos. integers, characters, y longs sencillamente se asignan todos ellos a size_t, que es el tipo de retorno para las funciones hash compatibles con STL. SGI STL incluye además funciones para reducir char*s (cadenas, por ejemplo) que iteran sobre cada carácter y aplican una sencilla fórmula recursiva.

El manejo de otros tipos sencillos es casi igual de fácil. Igual que con los primitivos, tiene sentido reducir (hash) cualquier cosa que se pueda asignar rápidamente y de forma exclusiva a un size_t, a su propio valor. Esta asignación es trivial y, por tanto, muy rápida. Puesto que obviamente es exclusivo, debería preferirse a otras funciones hash siempre que sea posible. Pero en lugar de volver a implementar este concepto de “hashing” para cada tipo que puede ser asignado a size_t, es mejor utilizar la plantilla del listado número 2.


template< typename T_TypeToHash >

struct SizeTCastHasher

size_t operator()( const T_TypeToHash& i_TypeToHash ) const

return size_t( i_TypeToHash );

;


Listado número 2

Un caso de uso para SizeTCastHasher es la reducción o “hashing” de un puntero. Supongamos, por ejemplo, que estamos escribiendo un programa para una empresa de publicidad en Internet. Tenemos una clase adFactory que crea objetos del tipo myAdvertisement. La clase de fábrica coloca también los anuncios en los sitios web invocando myWebsite.placeAd(); véase el listado número 3. El sitio web sigue la pista de los anuncios que se han colocado en dicho sitio colocando cada anuncio en un hash_set.

Como se crea cada myAdvertisement en una posición distinta dentro de la memoria, podemos utilizar la dirección del objeto myAdvertisement (el valor del puntero) como la clave para entrar en el mapa, y asignar el puntero a size_t cuando tengamos que calcular el valor hash de la clave. Indudablemente ello restringe de alguna forma la gestión de la memoria, ya que dos objetos idénticos situados en distintas posiciones dentro de la memoria no se reducirán al mismo valor.

Por consiguiente, hemos de asegurarnos de que sólo tengamos una copia en la memoria de un myAdvertisement dado. No obstante, a cambio de satisfacer esta restricción, la invocación de funciones de búsqueda como website.doWeShowAd() es ahora muy rápida porque la función hash es a la vez computacionalmente trivial y reduce cada objeto a un valor exclusivo.


class adFactory

...

myAdvertisement* createAd(TAdType adType)

myAdvertisement* newAd=new myAdvertisement(adType);

myWebsite* website=websiteFactory.getBestWebsite(newAd);

website.placeAd(newAd);

return newAd;

...

;

class website

public:

...

void placeAd(const myAdvertisement* const ad)

myAds.insert(ad);

bool doWeShowAd(myAdvertisement* ad) const

return myAds.find(ad)!=myAds.end();

...

private:

__gnu_cxx::hash_set< const myAdvertisement*, SizeTCastHasher< const myAdvertisement* > > myAds;

;


Listado número 3

Cuando diseñemos funciones hash para tipos más complejos, es importante saber lo más posible sobre los datos que utilizamos. La extensión y distribución de los datos es especialmente importante. Por ejemplo, supongamos que en la aplicación de anuncios, queremos saber cuantas personas vieron un anuncio dado, en un sitio web dado.

Una forma de realizarlo sería mediante un mapa de hash que reduzca un anuncio y un sitio web a un size_t. Supongamos ahora que cada anuncio y sitio web tiene un identificador exclusivo asociado al mismo.

Por ejemplo, podría ser un número de fila que nuestra aplicación asignó al anuncio o al sitio web cuando se cargaba desde una base de datos. En esa situación, queremos que el mapa de hash reduzca un par de enteros no asignados (el número de fila del anuncio y el sitio web) a otro entero no asignado.

Si asumimos que las identidades del sitio web y del anuncio son ambas más pequeñas que 216, en ese caso podemos empaquetar ambos identificadores a un único size_t sin que haya colisión hash. Eso es exactamente lo que hace ShiftedPairHasher (en el listado número 4).

struct ShiftedPairHasher

size_t operator()(std::pair key)

return (key.first << ( sizeof(unsigned int) * 8/2)) ^ key.second;

Listado número 4

Cómo funciona el código

Así es cómo funciona el código. Conceptualmente, estamos colocando key.first dentro de los 16 bits superiores de size_t y key.second en los 16 bits inferiores. Para ello, utilizamos el << operator de bits para trasladar key.first el número adecuado de bits a la izquierda. El número de bits a trasladar es la mitad del número de bits que hay en nuestro tipo de clave, y que calculamos con la fórmula sizeof(unsigned int)*8/2. A continuación, utilizamos ^, el operador XOR de bits, para poner key.second en la mitad inferior del valor hash. He elegido XOR en vez de OR porque si key.second aumenta a más de 16 bits, XOR produce valores hash que son más exclusivos que OR, ya que OR fija el bit nº17 en 1, para todos los valores de key.second que superan la cifra de 65536. ShiftedPairHasher es bastante rápido: Simplemente hace una operación de cambio a la izquierda y una operación XOR. El compilador optimiza sizeof(unsigned int)*8/2 a una constante en el tiempo de compilación. Este mismo concepto se puede ampliar si deseamos reducir más de dos valores, con simplemente cambiar cada valor el número adecuado de bits y a continuación utilizar XOR con los otros valores cambiados. Con los “hashers” adecuados, los contenedores de hash nos pueden dar un tiempo de acceso O(1). No obstante, incluso si somos capaces de crear unas funciones hash excelentes, hay ciertos casos en los que los contenedores que no han sido reducidos nos dan mejores prestaciones en tiempo de ejecución. Consideremos el caso en el que creamos un número enorme de contenedores que contienen sólo unos cuantos valores, y entonces sólo haremos unas cuantas búsquedas en cada contenedor (Listado número 5). Si tecleamos typedef TMap en un mapa normal en doMapBenchmark(), este programa tarda entorno a 5,9 segundos en ejecutarse (todos los tiempos se generaron en un Pentium 4 2.8 GHz). Pero si cambiamos TMap para que sea hash_map, ese mismo programa tarda 16,5 segundos. La razón de este aumento del 280% en el tiempo de ejecución está en cómo se asigna la memoria cuando la aplicación instancia mapas de hash y mapas.
#include

#include

#include

Listado número 5

Al implementarse los mapas como árboles binarios, el constructor de mapas sólo necesita crear unos cuantos punteros cuando la aplicación instancia un nuevo mapa. Pero los mapas de hash se implementan como matrices de listas enlazadas. Cuando creamos un nuevo mapa de hash, por defecto, STL crea 193 cubos e inserta un puntero NULL en cada uno. Si estamos creando un gran número de mapas de hash, puede llevar un montón de tiempo.

El problema puede ser mitigado hasta un cierto punto pidiendo un número menor de cubos. En el programa de medición (Listado número 5), podemos cambiar «TMap myMap;» por «TMap myMap(0);».

Aunque no obtendremos cero cubos, sí obtendremos el menor número de cubos que ofrece nuestra implementación de STL; en el caso de SGI STL son 53 cubos. Al realizar este cambio se reduce el tiempo de reloj de la medición a entorno 8,8 segundos – casi un 50% de disminución en el tiempo de ejecución.

Es importante también tener en cuenta el tiempo que se tarda en computar la función hash relativa a la exclusividad de la función. Por ejemplo, si tenemos dos funciones hash —una que produce muchas colisiones de hash pero es más rápida de calcular —y otra—que es más lenta pero produce muy pocas colisiones— puede ser razonable elegir la más rápida aunque pueda llevar al escalamiento que está más cerca de O(n) que de O(1). Por ejemplo, este tipo de estrategia es razonable cuando estamos tratando con cadenas largas.

Como el “hasher” de cadenas por defecto itera sobre cada carácter de la cadena cuando calcula el hash, las búsquedas se convierten en O(l) en donde l es la longitud de la cadena. Si los caracteres de la cadena están bien distribuidos, el tiempo de reloj puede mejorarse al reducir (hashing) menos caracteres, como en el listado número 6, (disponible online; véase la versión americana de DDJ, “Resource Center”, página 5.).

En este ejemplo, estamos insertando 10.000 cadenas de longitud 10.000, generadas de forma aleatoria, en un mapa de hash y a continuación buscamos a cada una de ellas 10.000 veces. Si utilizamos el “hasher” de cadenas por defecto, nos lleva 17,1 segundos. No obstante, si calculamos el hash basado sólo en los tres primeros caracteres de la cadena, el tiempo de ejecución se reduce a 8,4 segundos. Obviamente, el tiempo de cálculo de la función hash domina los laterales adicionales de las listas enlazadas que se necesitan para resolver las colisiones de hash.

Opciones STL

Si el STL no tiene una función hash que se adapta a nuestras necesidades, podemos echar un vistazo a las funciones hash de la biblioteca Boost antes de elaborar las nuestras propias. La biblioteca boost::hash (www.boost .org/doc/html/hash.html) ofrece funciones de “hashing “ para muchos primitivos, pero su función hash_combine es incluso más útil. Esta función toma dos valores hash y a partir de ellos calcula un hash nuevo y exclusivo.

La biblioteca para el «hashing» de Boost incluye plantillas que aplican hash_combine de forma recursiva para calcular los valores hash para estructuras de datos de objetos múltiples, tales como las matrices, las parejas y los contenedores STL. Empezando a partir de un valor semilla especificado para usuarios, el valor hash se calcula iterando sobre cada objeto individual y combinando el valor hash del objeto con el valor hash anteriormente calculado (o el valor semilla si el objeto en cuestión es el primero del contenedor).

Esto es un concepto útil, aunque, de nuevo, las prestaciones de los contenedores de hash y sus funciones hash asociadas dependen en gran media de los detalles de los datos. Cuando podemos elegir entre múltiples funciones hash, conviene que midamos cada opción antes de comprometernos con la decisión final.

Conclusión

Los contenedores basados en hash pueden ofrecer un incremento significativo de velocidad en la aplicación según una serie de condiciones. Aun así, no son adecuados para todas la situaciones y la ganancia en las prestaciones se ve en gran medida influida por la elección que tomemos en lo que respecta a la función hash, que a su vez depende de las propiedades de los datos que estamos reduciendo y mezclando de forma aleatoria (hashing).

Si se entienden los detalles de una aplicación y sus datos, los contenedores de hash son una potente herramienta de la caja de herramientas de las prestaciones.