In my last post I talked about the problems of using an incorrect hash function when you put an object with a composite key in a Java HashMap, but I was stuck with the question: Which data structure is better to index those objects?
Continuing with the same example I will talk about products and stores, and I will use their identifiers to form the map key. The proposed data structures are:
- A single map with a key containing its indexes:
HashMap<Tuple<Integer, Integer>, MyObject>, which I will call TupleMap. - A nested map:
HashMap<Integer, HashMap<Integer, MyObject>>, which I will call DoubleMap.
To solve all doubts and draw conclusions I will measure:
- Memory consumed by indexing a collection of objects
- The time needed to randomly store that collection of objects
- The time needed to recall, also randomly, all the elements of the collection
. . .
TL;DR: this post is more boring, so I’ll save you the job of reading the whole post:
- DoubleMap is more memory efficient and consumes 30% less than TupleMap
- In large collections, DoubleMap is 30% faster indexing, while in small collections it is considerably faster.
- In large collections, DoubleMap and TupleMap have similar fetching performance, while in small collections DoubleMap is significantly faster.
. . .
All the source code needed to reproduce the tests is in this GitHub repository: https://github.com/jerolba/hashcode-map.
In this case, I will apply the hash function that generates the least number of collisions and minimizes memory consumption, so I will not have to worry about this in my benchmarks and I will be in an optimal (and optimistic) case in the TupleMap version of not having to deal with collisions (less memory and CPU consumption).
Memory consumption
If we use an object as the primary key, how much memory will those instances of the primary key consume? If we use nested HashMaps, will it penalize the overhead of those objects?
If we randomly fill a map with 10,000 products and 500 stores, we get the following chart of memory consumption, taking into account only the classes involved in the maps:
On average, the map with a key object (Tuple) consumes 50% more memory, using 299 MB compared to the 193 MB of DoubleMap.
Looking at the histogram of the objects in memory we see that the instances of the Tuple class are using 114 MB and collisions are not taking place because instances of the TreeMap type do not appear:
| Class | instances | size |
| java.util.HashMap$Node | 5,000,000 | 160,000,000 |
| com.jerolba.bikey.Tuple | 5,000,000 | 120,000,000 |
| java.util.HashMap$Node[] | 1 | 33,554,448 |
| java.util.HashMap | 1 | 48 |
| com.jerolba.bikey.TupleMap | 1 | 16 |
while in the DoubleMap version the extra HashMap instances are consuming only half a megabyte, and the biggest difference lies in the space used in the node arrays:
| Class | instances | size |
| java.util.HashMap$Node | 5,010,000 | 160,320,000 |
| java.util.HashMap$Node[] | 10,001 | 41,185,552 |
| java.util.HashMap | 10,001 | 480,048 |
| com.jerolba.bikey.DoubleMap | 1 | 16 |
Therefore, if you need to create new instances of the object that represents the primary key when using this type of maps, I would choose a data structure such as HashMap<A, HashMap<B, MyObject>>.
Indexing performance
How long does it take to create a large collection in each case? Does the number of elements of each type have much influence?
In order not to bore you with the details of the benchmark I summarize it in a single chart where it shows the time (milliseconds) needed to insert a random collection of products and stores according to different total numbers of products and stores:
On average, keeping all the information on a single map has a penalty of at least 40% of the time.
Even if I don’t show you graphs (you have the data at the end of the post), the increase in the number of data in either of the two variables (products or stores) increases the execution time linearly.
Search performance
How long does it take to access to the value associated to a composite key? Will it penalize having to consult in two maps? In the TupleMap version, will it take longer if I have to instantiate a new Tuple object for each query?
As before, I will summarize in a single chart the benchmark of consulting in a large collection all its values randomly, according to different total numbers of products and stores:
Although DoubleMap’s execution time is always slightly below that of TupleMap, we can consider that they have a very similar performance, and therefore the access time should not condition the choice of one data structure over another.
Surprisingly, having to create a Tuple instance for each access does not penalize performance, and even slightly improves it in large collections (JVM optimizations are inscrutable).
Small collections
The problems I face usually have large collections, but in the benchmark results we can see that in small collections the implementation of DoubleMap performs much better.
Indexing
To visualize it better I show two charts: when the collection has 1,000 products and when it has 2,000:
TupleMap version times are between 2 and 6 times worse. Without having analyzed the internal behavior of the JVM/CPU/Memory, I intuit that the smaller size in data influences the location of the information and will give less problem with the cache lines.
Search
I also analyze it by looking at two charts for a different number of products:
The times of the TupleMap version are between 50% and 150% worse. I also don’t dare to say what it’s due to, but I still believe that it is related to differences in the cache usage pattern.
Conclusions
In spite of the obtained results, in this case I consider that it is difficult to draw clear conclusions by performing microbenchmarking. The behavior of the data structures can vary between the production code and the benchmark code.
In production code, between access and access to the map, your application can do many things that influence the availability of information in the caches, generating an access pattern completely different to the one in benchmark.
Personally I keep the idea of consuming less memory by not instantiating the Tuple class and using directly nested HashMaps. To avoid ugly code you can create an abstraction which encapsulates the behavior of the double map.
Working with two levels of HashMaps does not seem to be a performance problem, and is even faster, especially in relatively small collections.
Using DoubleMap we forgot about the problem of having to choose a hash function that minimizes collisions, because the key would be distributed between the two levels of HashMaps.
Benchmarks results
The source code to execute the benchmarks are in the GitHub repository, but in order that you can see the raw data of the charts, I copy you the results. This way you can also do your analysis and draw your conclusions.
Indexing
| Nº Productos | Nº Tiendas | Total | TupleMap (ms) |
DoubleMap (ms) |
| 1,000 | 100 | 100,000 | 33.1 | 5.61 |
| 2,500 | 100 | 250,000 | 103.38 | 24.78 |
| 5,000 | 100 | 500,000 | 177.71 | 116.43 |
| 7,500 | 100 | 750,000 | 272.02 | 160.95 |
| 10,000 | 100 | 1,000,000 | 314.94 | 241.86 |
| 1,000 | 250 | 250,000 | 129.18 | 19.82 |
| 2,500 | 250 | 625,000 | 292.97 | 114.85 |
| 5,000 | 250 | 1,250,000 | 644.29 | 421.45 |
| 7,500 | 250 | 1,875,000 | 1,061.19 | 631.18 |
| 10,000 | 250 | 2,500,000 | 1,432.11 | 1,102.94 |
| 1,000 | 500 | 500,000 | 326.49 | 55.98 |
| 2,500 | 500 | 1,250,000 | 805.16 | 368.4 |
| 5,000 | 500 | 2,500,000 | 1,503.63 | 994.39 |
| 7,500 | 500 | 3,750,000 | 2,601.49 | 1,687.45 |
| 10,000 | 500 | 5,000,000 | 3,158.44 | 2,601.42 |
| 1,000 | 750 | 750,000 | 450.98 | 82.68 |
| 2,500 | 750 | 1,875,000 | 1,427.11 | 569.73 |
| 5,000 | 750 | 3,750,000 | 2,531.31 | 1,347.68 |
| 7,500 | 750 | 5,625,000 | 3,730.37 | 2,436.08 |
| 10,000 | 750 | 7,500,000 | 5,108.52 | 3,753.73 |
| 1,000 | 1,000 | 1,000,000 | 790.76 | 272.73 |
| 2,500 | 1,000 | 2,500,000 | 1,833.54 | 905.38 |
| 5,000 | 1,000 | 5,000,000 | 3,487.37 | 2,360.07 |
| 7,500 | 1,000 | 7,500,000 | 5,550.26 | 3,886.36 |
| 10,000 | 1,000 | 10,000,000 | 7,763.96 | 5,728.61 |
Search
| Nº Productos | Nº Tiendas | Total | TupleMap (ms) |
Tuple new (ms) |
DoubleMap (ms) |
| 1,000 | 100 | 100,000 | 12.08 | 12.55 | 3.81 |
| 2,500 | 100 | 250,000 | 37.11 | 38.21 | 14.35 |
| 5,000 | 100 | 500,000 | 77.40 | 77.39 | 46.84 |
| 7,500 | 100 | 750,000 | 125.96 | 126.35 | 68.53 |
| 10,000 | 100 | 1,000,000 | 148.55 | 141.47 | 163.37 |
| 1,000 | 250 | 250,000 | 48.96 | 50.41 | 18.30 |
| 2,500 | 250 | 625,000 | 140.25 | 144.70 | 70.04 |
| 5,000 | 250 | 1,250,000 | 332.23 | 344.52 | 242.27 |
| 7,500 | 250 | 1,875,000 | 533.58 | 498.65 | 428.10 |
| 10,000 | 250 | 2,500,000 | 689.37 | 656.38 | 640.08 |
| 1,000 | 500 | 500,000 | 112.44 | 115.91 | 67.37 |
| 2,500 | 500 | 1,250,000 | 426.38 | 436.60 | 236.71 |
| 5,000 | 500 | 2,500,000 | 838.11 | 827.97 | 721.81 |
| 7,500 | 500 | 3,750,000 | 1,092.23 | 1,032.17 | 1,146.23 |
| 10,000 | 500 | 5,000,000 | 1,659.28 | 1,671.45 | 1,445.54 |
| 1,000 | 750 | 750,000 | 220.95 | 228.46 | 104.46 |
| 2,500 | 750 | 1,875,000 | 690.21 | 694.86 | 493.78 |
| 5,000 | 750 | 3,750,000 | 1,224.58 | 1,185.30 | 1,052.61 |
| 7,500 | 750 | 5,625,000 | 1,950.89 | 2,206.49 | 1,735.02 |
| 10,000 | 750 | 7,500,000 | 2,750.52 | 2,567.10 | 2,750.77 |
| 1,000 | 1,000 | 1,000,000 | 342.89 | 351.78 | 216.07 |
| 2,500 | 1,000 | 2,500,000 | 973.66 | 1,019.16 | 677.97 |
| 5,000 | 1,000 | 5,000,000 | 1,838.45 | 1,968.09 | 1,618.03 |
| 7,500 | 1,000 | 7,500,000 | 2,789.49 | 2,598.46 | 2,448.23 |
| 10,000 | 1,000 | 10,000,000 | 4,468.78 | 4,318.66 | 3,970.30 |