[concurrency-interest] Lock free caches

Mike Quilleash mike.quilleash at subexazure.com
Wed Apr 11 18:43:09 EDT 2007

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 );



-----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.

Concurrency-interest mailing list
Concurrency-interest at altair.cs.oswego.edu

 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