Mapas con clave compuesta

En mi último post hablé de los problemas de usar una función hash incorrecta cuando guardas un objeto con clave compuesta en un HashMap de Java, pero me quedé con la duda: ¿qué estructura de datos es mejor a la hora de indexar esos objetos?

Siguiendo con el mismo ejemplo hablaré de productos y tiendas, y usaré sus identificadores para formar la clave del mapa. Las estructuras de datos propuestas son:

• Un único mapa con una clave que contenga sus índices: HashMap<Tuple<Integer, Integer>, MyObject>, al que llamaré TupleMap.
• Un mapa anidado: HashMap<Integer, HashMap<Integer, MyObject>>, al que llamaré DoubleMap.

Para salir de dudas y sacar conclusiones mediré:

• La memoria consumida al indexar una colección de objetos
• El tiempo necesario para guardar de forma aleatoria esa colección de objetos
• El tiempo necesario para recuperar, también de forma aleatoria, todos los elementos de la colección

TL;DR: este post es más aburrido, así que os ahorraré el trabajo de leerlo entero:

• DoubleMap es más eficiente en memoria y consume un 30% menos que TupleMap
• En colecciones grandes, DoubleMap es un 30% más rápido indexando, mientras que en colecciones pequeñas es bastante más rápido
• En colecciones grandes, DoubleMap y TupleMap tienen un rendimiento parecido consultando, mientras que en colecciones pequeñas DoubleMap es sensiblemente más rápido

Todo el código fuente necesario para reproducir las pruebas está en este repositorio de GitHub: https://github.com/jerolba/hashcode-map.

En este caso aplicaré la función hash que genera menor número de colisiones y minimiza el consumo de memoria, por lo que no me tendré que preocupar de esa parte en mis benchmarks y estaré en un caso optimo (y optimista) en la versión de TupleMap de no tener que lidiar con las colisiones.

Consumo de memoria

Si usamos un objeto como clave primaria, ¿cuánta memoria consumirán esas instancias de la clave primaria? Si usamos HashMaps anidados, ¿penalizará el overhead de esos objetos?

Si rellenamos de forma aleatoria un mapa con 10.000 productos y 500 tiendas, obtenemos la siguiente gráfica de consumo de memoria, teniendo en cuenta sólo las clases involucradas en los mapas:

De media, el mapa con un objeto clave (Tuple) consume un 50% más de memoria, ocupando finalmente 299 MB frente a los 193 MB del DoubleMap.

Mirando el histograma de los objetos en memoria vemos que las instancias de la clase Tuple están ocupando 114 MB y no se están produciendo colisiones al no aparecer instancias del tipo TreeMap:

mientras que en la versión de DoubleMap las instancias de HashMap extra están ocupando apenas medio megabyte, y la mayor diferencia radica en el espacio empleado en los arrays de nodos:

Por tanto, si al usar este tipo de mapas necesitas crear nuevas instancias del objeto que representa la clave primaria, yo optaría por usar una estructura de datos del tipo HashMap<A, HashMap<B, MyObject>>.

Rendimiento en indexación

¿Cuánto se tarda en crear una colección grande en cada caso? ¿Influye mucho el número de elementos de cada tipo?

Para no aburriros con los detalles del benchmark lo resumo en una única gráfica donde se muestra el tiempo (en milisegundos) necesario para insertar una colección aleatoria de productos y tiendas según diferentes números totales de productos y tiendas:

De media, mantener toda la información en un único mapa tiene una penalización de al menos un 40% de tiempo.

Aunque no muestre gráficas (tienes los datos al final del post), el aumento del número de datos en cualquiera de las dos variables (productos o tiendas) aumenta el tiempo de ejecución de forma lineal.

Rendimiento en consulta

¿Cuánto se tarda en acceder al valor asociado a una clave compuesta? ¿Penalizará el tener que consultar en dos mapas? En la versión de TupleMap, ¿Se tarda más si por cada consulta tengo que instanciar un objeto Tuple?

Al igual que antes, resumiré en una única gráfica el benchmark de consultar en una colección grande todos sus valores de forma aleatoria, según diferentes números totales de productos y tiendas:

Aunque el tiempo de ejecución de DoubleMap está siempre ligeramente por debajo de el de TupleMap podemos considerar que tienen un rendimiento muy similar, y por tanto el tiempo de acceso no debería condicionarnos la elección de una estructura de datos u otra.

Sorprendentemente tener que crear una instancia de Tuple por cada consulta no penaliza en el rendimiento, e incluso lo mejora ligeramente en colecciones grandes (las optimizaciones de la JVM son inescrutables)

Colecciones pequeñas

Los problemas a los que me enfrento normalmente usan colecciones grandes, pero en los resultados de los benchmarks podemos ver que en colecciones pequeñas la implementación de DoubleMap tiene bastante mejor rendimiento.

Indexación

Para visualizarlo mejor mostraré dos gráficas: cuando la colección tiene 1.000 productos y cuando tiene 2.000.

Los tiempos de la versión TupleMap son entre 2 y 6 veces peores. Sin haber analizado el comportamiento interno de la JVM/CPU/Memoria, intuyo que el menor tamaño en datos influye en la localidad de la información y dará menos problema con las línea de caché.

Consulta

Igualmente lo analizamos viendo dos gráficas para distinto número de productos:

Los tiempos de la versión TupleMap son entre un 50% y un 150% peores. Tampoco me atrevo a asegurar a qué se debe, pero sigo creyendo que los tiros van por problemas con la caché.

Conclusiones

A pesar de los resultados obtenidos, en este caso considero que es difícil sacar unas conclusiones claras realizando microbenchmarking. El comportamiento de las estructuras de datos pueden variar entre el código de producción y el del benchmark.

En código de producción, entre acceso y acceso al mapa, tu aplicación puede hacer muchas cosas que influyan en la disponibilidad de la información en las cachés, generando un patrón de acceso complentamente distinto al del benchmark.

Personalmente me quedo con la idea de consumir menos memoria no instanciando la clase Tuple y usar directamente HashMaps anidados. Para evitar el código feo de tanto generico, puedes abstraer y encapsular ese código en una clase.

Tener que insertar/consultar en dos HashMaps parece que no supone un problema de rendimiento, e incluso es más rápido, sobre todo en colecciones relativamente pequeñas.

Usando DoubleMap nos olvidamos del problema de tener que elegir una función hash que minimice las colisiones, ya que la clave estaría distribuida entre los dos niveles de HashMaps.

Resultados de los benchmarks

El código fuente para ejecutar los benchmarks están en el repositorio de GitHub, pero para que podáis ver los datos de las gráficas en crudo os copio los resultados. Así además podéis hacer vuestros análisis y sacar vuestras conclusiones.

Indexación

Consulta