[concurrency-interest] Memory sensitive memoization

Sanchay Harneja sanchay.h at gmail.com
Sun Jun 26 06:30:08 EDT 2011


Suppose I have a pure method f, of 2 arguments, a1, a2. Now, it takes a long
time to compute f(a1,a2), so I want to memoize it, but at the same time want
to make it memory sensitive, i.e., remove memoized entries to reclaim memory
if required. So keys as SoftReferences come to mind. Another requirement is
that this memoized cache should be thread safe, many threads will be writing
and reading from it. With all this in mind, I have the following questions:

1.  Is extra166y.CustomConcurrentHashMap stable enough to use in production?
Or shall I go with org.apache.commons.collections.map.ReferenceMap (and use
Collections.SynchronizedMap)? Or shall I consider writing my own
implementation.

2. Assuming CustomConcurrentHashMap, I have the following pattern in mind,

class Context{
  a1;
  a2;
  // equal and hashcode based on both a1,a2
}

*CustomConcurrentHashMap<Context,V> cache = new
CustomConcurrentHashMap<http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/CustomConcurrentHashMap.html#CustomConcurrentHashMap(extra166y.CustomConcurrentHashMap.Strength,
extra166y.CustomConcurrentHashMap.Equivalence,
extra166y.CustomConcurrentHashMap.Strength,
extra166y.CustomConcurrentHashMap.Equivalence, int)><Context,V>*(
CustomConcurrentHashMap.Strength<http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/CustomConcurrentHashMap.Strength.html>
.SOFT, CustomConcurrentHashMap.Equivalence<http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/CustomConcurrentHashMap.Equivalence.html>
.EQUALS, CustomConcurrentHashMap.Strength<http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/CustomConcurrentHashMap.Strength.html>
.STRONG, CustomConcurrentHashMap.Equivalence<http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/CustomConcurrentHashMap.Equivalence.html>.EQUALS,
0);

V f(a1,a2){
  Context ctx = new Context(a1,a2); //.......... 1.
  V ret = cache.get(ctx);                  //.......... 2.
  if (ret != null)                                 //.......... 3.
    return ret;                                   //.......... 4.
  // actually compute f(a1,a2);          //........... 5.
  ret.putIfAbsent(ctx, val);                //........... 6.
  return val;                                    //........... 7.
}

I think this pattern does the job, what do you guys suggest ? Is there a
more idiomatic way to doing memoization in Java ? Line 2. above relies on
the assumption that f(a1,a2) will never be null, which is fine, but can this
assumption be somehow avoided? Also at line 6. above I don't strictly need
putIfAbsent, should I just go for put (if it is cheaper) ?


3. Suppose thread t1 is busy computing f(5,10), meanwhile another thread t2
calls f(5,10), what can be done so that t2 waits for t1's computation to
finish and then just takes the value from the cache ? Note it is possible
that by the time t2 checks again, (5,10) is garbage collected and some t3
starts computing (5,10), so it would require a loop.

Thanks!
Sanchay
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20110626/819ff5a7/attachment.html>


More information about the Concurrency-interest mailing list