CODEWITHSUNDEEP
javamaps
Martin Klosi
Martin Klosi

Reputation: 3296

nested maps vs multikey maps performance

I know and it makes sense that using multikey maps is more performant than nested maps, but I wrote testing code that shows that nesting maps is faster AND more memory efficient than using a flat multikey map.

nested maps: - 3 maps with 7 submaps each - each submap has 4 subsubmaps - each subsubmap has about 600,000 entries - total: about 50,400,000 entires

multikey as simple String map: - one huge map with 50,400,000 entires

memory and time to populate the nested maps: 1462M -> 15sec; memory and time to populate the multikey map: 2138M -> 56sec

I'm not sure if I am doing smth wrong or I am missing smth.

Upvotes: 0

Views: 2496

Answers (3)

Martin Klosi
Martin Klosi

Reputation: 3296

I think I figured out why nested maps seem more efficient than multikey maps. Each time I make a new request in a multikey map, I create a new object, either a MultiKey or a String. These "lookup" objects, although local for each call, will build up over time unless gc kicks in, and it won't kick in unless the vm max limit has been reached. When using nested maps, I just do a lookup by each key individually and thus don't create extra object that aren't already created in a higher scope.

Upvotes: 1

Stephen C
Stephen C

Reputation: 719229

Three possible explanations spring to mind:

  1. An invalid benchmark. It is very easy to write a benchmark that gives results that are meaningless. Unless we see your benchmark code, we cannot exclude this. (The classic mistake is take only one measurement for the two cases you are comparing ... and get burned by JVM warmup anomalies.)

  2. For some reason, the there are a lot of hash collisions in the multikey map case.

  3. In the multikey case, I assume that your your keys are concatenations of a number of shorter keys. Depending on how the keys (Strings?) are formed (in the nested map and multikey map cases), you may be using a lot more space to represent the keys in the multikey map case. That also equates to more time to create the keys, and to calculate their hashcodes.

Upvotes: 1

piotrek
piotrek

Reputation: 14550

without benchmarks it will be hard to help. so it's just a guess: maybe you just failing on concatenating strings to build new key for single map. after all you are creating >50M new strings. try using dedicated maps (like apache or guava) that calculates hashcodes quickly without building heavy objects

Upvotes: 2

Related Questions