[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!
 
Cheers.
 
Mike.
 
 
 
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:
http://developers.sun.com/learning/javaoneonline/2005/coreplatform/TS-34
23.pdf
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;
                newFuture.run();
            }
        }
 
        // 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
available
        try
        {
            return future.get();
        }
        catch ( InterruptedException e )
        {
            // re-interrupt
            Thread.currentThread().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
Peierls
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
synchronization
	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.

--tim




 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