[concurrency-interest] Lock free caches

Mike Quilleash mike.quilleash at subexazure.com
Wed Apr 11 12:18:38 EDT 2007

I've merged the examples/ideas that I've seen here and in the JavaOne
slides and put all the implementations together in one place.  Please
check/comment if you have time!
public interface Computable< K, V >
    public V compute( K input );

// base class for Memoizers - simply holds the computation
public abstract class Memoizer< K, V > implements Computable< K, V >
    private final Computable< K, V > computation;
    public Memoizer( Computable<K, V> computation )
        this.computation = computation;
    protected V doCompute( K input )
        return computation.compute( input );

// implementation that copies the internal map on every cache miss
// minimal synchronization overhead (one volatile read) once the cache
// has settled down
public class CopyOnWriteMemoizer< K, V > extends Memoizer< K, V >
    // technically an unmodifiable map once it is assigned
    private volatile Map< K, V > map = new HashMap< K, V >();
    public CopyOnWriteMemoizer( Computable<K, V> computation )
        super( computation );
    public V compute( K input )
        Map< K, V > localMap = map;
        if ( localMap.containsKey( input ) )
            return localMap.get( input );
        // doCompute the missing value
        V value = doCompute( input );
        // copy the map and add the new value
        Map< K, V > newMap = new HashMap< K, V >( localMap );
        newMap.put( input, value );
        map = newMap;
        return value;

// single ConcurrentMap implementation of memoizer.  multiple threads
may create the
// same entry and overwrite another threads result but this is a benign
race condition
public class ConcurrentMapMemoizer< K, V > extends Memoizer< K, V >
    private final ConcurrentMap< K, V > map = new ConcurrentHashMap< K,
V >();
    public ConcurrentMapMemoizer( Computable<K, V> computation )
        super( computation );
    public V compute( K input )
        if ( input == null )
            throw new NullPointerException( "Input is null" );
        V value = map.get( input );
        if ( value != null )
            return value;
        value = doCompute( input );
        map.put( input, value );
        return value;

// more complex Memoizer that is guaranteed to doCompute each input at
most once
// if two threads request a missing value at the same time one thread
will do the doCompute
// while the other waits for the result
// based on the JavaOne slides here:
public class ConcurrentComputeOnceMemoizer< K, V > extends Memoizer< K,
V >
    private final ConcurrentMap< K, Future< V > > map = new
ConcurrentHashMap< K, Future< V > >();
    public ConcurrentComputeOnceMemoizer( Computable<K, V> computation )
        super( computation );
    public V compute( final K input )
        Future< V > future = map.get( input );
        // not in the map yet
        if ( future == null )
            // create a task wrapping up the computation
            Callable< V > callable = new Callable< V >()
                public V call() throws Exception
                    return doCompute( input );
            FutureTask< V > newFuture = new FutureTask< V >( callable );
            // add the future to the map
            future = map.putIfAbsent( input, newFuture );
            // if the put into the map did NOT succeed then another
thread beat us inserting
            // into the map so just go and wait for the future result to
become available
            // if the put into the map succeeded then execute the newly
created future
            // in this thread
            if ( future == null )
                future = newFuture;
        // get the future result
        // if two threads enter around the same time one will "win" and
run the future
        // the other will wait here for the future result to become
            return future.get();
        catch ( InterruptedException e )
            // re-interrupt
            throw new RuntimeException( e );
        catch ( ExecutionException e )
            throw new RuntimeException( e );



From: tpeierls at gmail.com [mailto:tpeierls at gmail.com] On Behalf Of Tim
Sent: 11 April 2007 15:46
To: Mike Quilleash 
Cc: Ernst, Matthias; concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Lock free caches

On 4/11/07, Ernst, Matthias <matthias.ernst at coremedia.com> wrote: 

	a technique for memoizing small amounts with a minimum of
	I'm sometimes using is copy-on-write on a plain hashmap: [...]
	Synchronization cost: one volatile read and I guess the code
path is a little shorter than with a CHM. 

The synch cost of MemoizedFunction.apply(arg) for a previously cached
value of arg is a CHM.get() plus a FutureTask.get() on a completed task
-- usually a small number of volatile reads, I believe.

It's worth getting memoization right once, and encapsulating it. Once
you have it, all you need to do is something like this:

    private static final Function<String, Pattern> PATTERN_COMPILE =
        new MemoizedFunction<String, Pattern>(new Function<String,
Pattern>() { 
            public Pattern apply(String s) { return Pattern.compile(s);

Then you can safely write:

    Pattern pat = PATTERN_COMPILE.apply("truth(?:iness)?");

This really ought to be standardized, or at least made available via
some quasi-standard resource. I had hoped that http://jcip.net would
become such a resource, but alas, everyone seems to be too busy to
manage this.


 This e-mail is bound by the terms and conditions described at http://www.subexazure.com/mail-disclaimer.html

-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20070411/9283b6e0/attachment.html 

More information about the Concurrency-interest mailing list