StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGuava ImmutableMap has noticeably slower access than HashMap
text
Body
copied!<p>While working on a memory benchmark of some high-throughput data structures, I realized I could use an <code>ImmutableMap</code> with only a little refactoring. </p> <p>Thinking this would be an improvement, I threw it into the mix and was surprised to discover that not only was it slower than <code>HashMap</code>, in a single-threaded environment it appears to be consistently slower even than <code>ConcurrentHashMap</code>!</p> <p>You can see the full benchmark here: <a href="https://bitbucket.org/snippets/dimo414/89K7G" rel="nofollow noreferrer">https://bitbucket.org/snippets/dimo414/89K7G</a></p> <p>The meat of the test is pretty simple, time how long it takes to get a large number of random strings that may exist in the map.</p> <pre><code>public static void timeAccess(Map<String,String> map) { Random rnd = new Random(seed); int foundCount = 0; long start = System.nanoTime(); for(int i = 0; i < loop; i++) { String s = map.get(RndString.build(rnd)); if(s != null) foundCount++; } long stop = System.nanoTime() - start; System.out.println("Found "+foundCount+" strings out of "+loop+" attempts - "+ String.format("%.2f",100.0*foundCount/loop)+" success rate."); System.out.println(map.getClass().getSimpleName()+" took "+ String.format("%.4f", stop/1_000_000_000.0)+" seconds."); System.out.println(); } </code></pre> <p>And running this against a <code>HashMap</code>, a <code>ConcurrentHashMap</code>, and an <code>ImmutableMap</code>, all containing the same values, consistently showed a dramatic slowdown when using <code>ImmutableMap</code> - often upwards of 15% slower. The more sparse the map (i.e. the more often <code>map.get()</code> returned null) the greater the disparity. Here's the result of a sample run:</p> <pre><code>Found 35312152 strings out of 100000000 attempts - 35.31 success rate. HashMap took 29.4538 seconds. Found 35312152 strings out of 100000000 attempts - 35.31 success rate. ConcurrentHashMap took 32.1465 seconds. Found 35312152 strings out of 100000000 attempts - 35.31 success rate. RegularImmutableMap took 37.9709 seconds. </code></pre> <p>Is this a documented / expected issue? The <a href="https://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained" rel="nofollow noreferrer">Guava Docs</a> indicate <code>Immutable***</code> is more memory efficient, but says nothing about speed. For slowdowns of this magnitude, I'm inclined to deal with the memory costs and avoid <code>Immutable***</code> when speed is an issue (and when isn't it?!). Am I missing something?</p> <p>See also: <a href="https://groups.google.com/forum/?fromgroups=#!topic/guava-discuss/I7yPpa5Hlpg" rel="nofollow noreferrer">https://groups.google.com/forum/?fromgroups=#!topic/guava-discuss/I7yPpa5Hlpg</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload