title: ThreadLocal HashMap vs ConcurrentHashMap for thread-safe unbound caches
body: <p>I'm creating a memoization cache with the following characteristics:</p>
  
  <ul>
  <li>a cache miss will result in computing and storing an entry
  <ul>
  <li>this computation is very expensive</li>
  <li>this computation is idempotent</li>
  </ul></li>
  <li>unbounded (entries never removed) since:
  <ul>
  <li>the inputs would result in at most 500 entries</li>
  <li>each stored entry is very small</li>
  <li>cache is relatively shorted-lived (typically less than an hour)</li>
  <li>overall, memory usage isn't an issue</li>
  </ul></li>
  <li>there will be thousands of reads - over the cache's lifetime, I expect 99.9%+ cache hits</li>
  <li><em>must be thread-safe</em></li>
  </ul>
  
  <p>What would have superior performance, or under what conditions would one solution be favored over the other?</p>
  
  <p>ThreadLocal HashMap:</p>
  
  <pre><code>class MyCache {
      private static class LocalMyCache {
          final Map&lt;K,V&gt; map = new HashMap&lt;K,V&gt;();
  
          V get(K key) {
              V val = map.get(key);
              if (val == null) {
                  val = computeVal(key);
                  map.put(key, val);
              }
              return val;
          }
      }
  
      private final ThreadLocal&lt;LocalMyCache&gt; localCaches = new ThreadLocal&lt;LocalMyCache&gt;() {
          protected LocalMyCache initialValue() {
              return new LocalMyCache();
          }
      };
  
      public V get(K key) {
          return localCaches.get().get(key);
      }
  }
  </code></pre>
  
  <p>ConcurrentHashMap:</p>
  
  <pre><code>class MyCache {
      private final ConcurrentHashMap&lt;K,V&gt; map = new ConcurrentHashMap&lt;K,V&gt;();
  
      public V get(K key) {
          V val = map.get(key);
          if (val == null) {
              val = computeVal(key);
              map.put(key, val);
          }
          return val;
      }
  }
  </code></pre>
  
  <p>I figure the ThreadLocal solution would initially be slower if there a lot of threads because of all the cache misses per thread, but over thousands of reads, the amortized cost would be lower than the ConcurrentHashMap solution. Is my intuition correct?</p>
  
  <p>Or is there an even better solution?</p>