[concurrency-interest] Lock free caches

Mike Quilleash mike.quilleash at subexazure.com
Thu Apr 12 07:58:12 EDT 2007


As an enhancment to the implementation using FutureTask I think you can make it a bit more fail-safe by removing an entry from the map if the computation throws an exception.

        try
        {
            return future.get();
        }
        catch ( InterruptedException e )
        {
            // re-interrupt
            Thread.currentThread().interrupt();

            throw new RuntimeException( e );
        }
        catch ( ExecutionException e )
        {
            // remove the future from the map as it is now broken - next thread to request
            // this input will attempt to recompute the value
            if ( retryFailedCompute )
                map.remove( input );

            throw new RuntimeException( e.getCause() );
        }

So on an ExecutionException, originally thrown from doCompute(), the "dead" future will be removed from the map so the next request will cause a retry (depending on the retryFailedCompute flag).  This might be useful for operations that can-but-usually-don't fail.  Threads already passed the initial map.get() will still throw the exception but subsequent ones stand a chance of succeeding.  When the computation should never fail and is broken if it does fail then setting the retryFailedCompute to false will cause the same exception to be thrown for every thread requesting the value.

Further enhancements could involve some sort of retry policy to handle failure and decide on retrying vs exception and anything else like wait time between retries etc.

Cheers.

Mike.

-----Original Message-----
From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Mike Quilleash 
Sent: 11 April 2007 23:43
To: Holger Hoffstätte; concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Lock free caches

Thanks for your comments.

As Joe pointed out in my original RegEx "memoizer" the putIfAbsent doesn't really accomplish anything over a normal put as you will always be replacing the same computed value in the map.

Regarding the first the convention in the examples I've seen seems to be to use containsKey + get or !containsKey + put so I've followed that where possible.  The exception being the implementations using ConcurrentHashMap that doesn't support null keys or values.  The implementations could be extended to use a Null object placeholder to allow this I guess.  Would be sensible as someone could swap out implementations and get NPEs.  Or just change the Memoizer contract to disallow null inputs and null computed values in which case you, as you say, just use get() and skip the containsKey check.

For completeness and uselessness at the same time here's another implementation! ;)

// dumb non-implementation of a memoizer public class NonMemoizer< K, V > extends Memoizer< K, V > {
    public NonMemoizer( Computable<K, V> computation )
    {
        super( computation );
    }

    public V compute( K input )
    {
        return doCompute( input );
    }
}


Cheers.

Mike.

-----Original Message-----
From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Holger Hoffstätte
Sent: 11 April 2007 18:21
To: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Lock free caches

Mike Quilleash wrote:
>         Map< K, V > localMap = map;
>  
>         if ( localMap.containsKey( input ) )
>             return localMap.get( input );

You could still shave off the redundant lookup here, no?

In ConcurrentMemoizer:
>         value = doCompute( input );
>         map.put( input, value );
>  
>         return value;

  value = doCompute(input);
  concurrentValue = map.putIfAbsent(input, value);

  // flip refs on conflict
  if (concurrentValue != null)
  {
      value = concurrentValue;
  }

  return value;

So you'd actually use the ConcurrentMap interface.

-h
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at altair.cs.oswego.edu
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


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


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at altair.cs.oswego.edu
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


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




More information about the Concurrency-interest mailing list