title: Guava ImmutableMap has noticeably slower access than HashMap
body: <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 <a href="https://gist.github.com/dimo414/e692e26e276bd9cf1749bd5d7fc800d8" rel="nofollow noreferrer">full benchmark</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&lt;String,String&gt; map) {
      Random rnd = new Random(seed);
      int foundCount = 0;
  
      long start = System.nanoTime();
  
      for(int i = 0; i &lt; 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>