title: Using standard Java HashMap (compared to Trove THashMap) causes non-HashMap code to run slower
body: <p>I use a HashMap to cache about 2 million values calculated through a recursive algorithm. I use either <code>HashMap&lt;Integer, Double&gt;</code> from the Collections Framework, or the <code>TIntDoubleHashMap</code> from the Trove library, controlled by the <code>boolean useTrove</code> variable, as in the code below.</p>
  
  <p>I do expect the Trove library to be faster, as it avoids auto-boxing etc. And indeed, the <code>put()</code> and <code>get()</code> calls take about 300ms to run (in total) for the <code>THashMap</code> compared to about 500ms for the <code>HashMap&lt;&gt;</code>.</p>
  
  <p>Now, my overall program runtime is about 2.8s when using <code>THashMap</code>, and 6.7s when using <code>HashMap&lt;&gt;</code>. This difference cannot be explained by the increased runtime for the <code>put()</code> and <code>get()</code> calls alone.</p>
  
  <ol>
  <li><p>I suspect this vastly increased runtime with <code>HashMap&lt;&gt;</code> is driven
  by the fact that this implementation is quite memory inefficient as
  each int/double needs to be boxed into an Object, and this increased
  memory usage causes cache misses in other parts of the program. Does
  this explanation make sense, and how could I confirm/reject this
  hypothesis?</p></li>
  <li><p>In general, how do I explore algorithmic optimisations for such scenarios? Profiling the algorithm doesn't readily point to the
  <code>HashMap&lt;&gt;</code> being the culprit, at least if CPU time alone is
  considered. Is it simply a question of knowing in advance that
  memory usage needs to be prioritised for memory-hungry programs?</p></li>
  </ol>
  
  <p>Code in full below.</p>
  
  <pre><code>import java.util.HashMap;
  import gnu.trove.map.hash.TIntDoubleHashMap;
  
  class RuntimeStopWatch {
      long elapsedTime;
      long startTime;
      RuntimeStopWatch() { reset(); }
      void reset() { elapsedTime = 0; }
      void start() { startTime = System.nanoTime(); }
      void stop() {
          long endTime = System.nanoTime();
          elapsedTime += (endTime - startTime);
          startTime = endTime;
      }
      void printElapsedTime(String prefix) {
          System.out.format(prefix + "%dms\n", elapsedTime / 1000000);
      }
  }
  
  public class HashMapBehaviour {
  
      static RuntimeStopWatch programTime = new RuntimeStopWatch();
      static RuntimeStopWatch hashMapTime = new RuntimeStopWatch();
      static HashMap&lt;Integer, Double&gt; javaHashMapCache;
      static TIntDoubleHashMap troveHashMapCache;
      static boolean useTrove;
  
      public static void main(String[] args) {
  //        useTrove = true;
          useTrove = false;
  
          javaHashMapCache = new HashMap&lt;&gt;();
          troveHashMapCache = new TIntDoubleHashMap();
  
          programTime.start();
          recursiveFunction(29, 29, 178956970);
          programTime.stop();
  
          programTime.printElapsedTime("Program: ");
          hashMapTime.printElapsedTime("Hashmap: ");
      }
  
  
      static double recursiveFunction(int n, int k, int bitString) {
          if (k == 0) return 0.0;
          if (useTrove) {
              hashMapTime.start();
              if (troveHashMapCache.containsKey(bitString | (1 &lt;&lt; n))) return troveHashMapCache.get(bitString | (1 &lt;&lt; n));
              hashMapTime.stop();
          } else {
              hashMapTime.start();
              if (javaHashMapCache.containsKey(bitString | (1 &lt;&lt; n))) return javaHashMapCache.get(bitString | (1 &lt;&lt; n));
              hashMapTime.stop();
          }
          double result = 0.0;
          for (int i = 0; i &lt; (n &gt;&gt; 1); i++) {
              double play1 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, i));
              double play2 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, n - i - 1));
              result += Math.max(play1, play2);
          }
          if (useTrove) {
              hashMapTime.start();
              troveHashMapCache.put(bitString | (1 &lt;&lt; n), result);
              hashMapTime.stop();
          } else {
              hashMapTime.start();
              javaHashMapCache.put(bitString | (1 &lt;&lt; n), result);
              hashMapTime.stop();
          }
          return result;
      }
  
      static int stripSingleBit(int bitString, int bitIndex) {
          return ((bitString &gt;&gt; (bitIndex + 1)) &lt;&lt; bitIndex) | (bitString &amp; ((1 &lt;&lt; bitIndex) - 1));
      }
  }
  </code></pre>