Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.mixmin.net!news.musoftware.de!wum.musoftware.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Robert Klemme <shortcutter@googlemail.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: multithreaded cache?
Date: Thu, 17 May 2012 12:06:34 +0200
Lines: 152
Message-ID: <a1k0taF206U1@mid.individual.net>
References: <zsWdnVufD87Egy_SnZ2dnUVZ7oednZ2d@brightview.co.uk> <a1k06fFtdtU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net YI8r3IEzCB8epHDNBgxF8QiwrOD5U9M6XCz7Gq4ravUiSEZGFRFnGRfFb8MxKEMGE=
Cancel-Lock: sha1:38AmX1td9Hkzk4D5HYBa8p/GbD4=
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:12.0) Gecko/20120430 Thunderbird/12.0.1
In-Reply-To: <a1k06fFtdtU1@mid.individual.net>
Xref: csiph.com comp.lang.java.programmer:14572

On 05/17/2012 11:54 AM, Robert Klemme wrote:
> On 05/15/2012 11:14 AM, bugbear wrote:
>> However, if the underlying function is slow
>> and/or resource hungry (consider cacheing
>> a ray traced image!) many threads can
>> end up calling the real function (second
>> and subsequent threads to the first get a miss
>> during the first threads call to the underlying function).
>>
>> "obviously..." what I want is for only
>> the thread that FIRST has a cache miss
>> calls the underlying function, whilst other
>> threads (for the same key) wait.
>
> I provide a variant of Silvio's, Eric's and Daniel's solution which
> should yield higher throughput because it works without read write
> locking. You can find it as gist in case the code is garbled in the
> newsgroup posting:
> https://gist.github.com/2717818

There was one important detail missing.  This is the corrected code 
(gist is updated as well):

package clj;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

/**
  * The cache works with as few locking as possible. Lookup is done in 
two steps
  * on cache miss:
  * <ol>
  * <li>On a cache miss a retriever is inserted into the cache which 
will obtain
  * the value synchronized from a {@link Calculator}.</li>
  * <li>Once calculation has finished a simple lock free reference to 
the value
  * replaces the retriever in the cache and the value is returned.</li>
  * </ol>
  *
  * @author robert klemme
  *
  * @param <K>
  *            key type
  * @param <V>
  *            value type
  */
public final class LazyCache<K, V> {
     /**
      * Calculate values from given keys.
      *
      * @param <K>
      *            key type
      * @param <V>
      *            value type
      */
     public interface Calculator<K, V> {
         V get(K key);
     }

     /**
      * Obtain a value.
      *
      * @param <V>
      *            value type.
      */
     private interface Reference<V> {
         V get();
     }

     /**
      * Stupid simple reference which only hands out a fixed value all 
the time
      * without synchronization.
      *
      * @param <V>
      *            value type.
      */
     private static final class Ref<V> implements Reference<V> {
         private final V val;

         public Ref(V val) {
             this.val = val;
         }

         @Override
         public V get() {
             return val;
         }
     }

     /** Mapping from keys to objects which yield values. */
     private final ConcurrentMap<K, Reference<V>> map = new 
ConcurrentHashMap<K, Reference<V>>();

     /** User provided. */
     private final Calculator<K, V> calc;

     /**
      * Create a cache.
      *
      * @param calc
      *            user must provide a reasonable implementation, not
      *            <code>null</code>.
      */
     public LazyCache(final Calculator<K, V> calc) {
         if (calc == null)
             throw new NullPointerException();
         this.calc = calc;
     }

     /**
      * Get a value from the cache. The value might have to be calculated.
      *
      * @param key
      *            lookup key.
      * @return value, might even be <code>null</code> depending on 
algorithm.
      */
     public V get(final K key) {
         Reference<V> ref = map.get(key);

         if (ref == null) {
             // miss
             ref = new Reference<V>() {
                 private V val;
                 private boolean here = false; // superfluous but explicit

                 @Override
                 public synchronized V get() {
                     if (!here) {
                         val = calc.get(key);
                         here = true;
                         // next time lock free access:
                         Reference<V> x = map.put(key, new Ref<V>(val));
                         assert x == this;
                     }

                     return val;
                 }
             };

             final Reference<V> old = map.putIfAbsent(key, ref);

             if (old != null)
                 ref = old; // someone else was faster
         }

         return ref.get();
     }
}