[concurrency-interest] Memory sensitive memoization

Tim Peierls tim at peierls.net
Sun Jun 26 08:59:44 EDT 2011


In this case, consider using Guava
MapMaker<http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/index.html?com/google/common/collect/MapMaker.html>.
The example in the javadoc is close to what you're looking for.

--tim

On Sun, Jun 26, 2011 at 6:30 AM, Sanchay Harneja <sanchay.h at gmail.com>wrote:

> 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,%20extra166y.CustomConcurrentHashMap.Equivalence,%20extra166y.CustomConcurrentHashMap.Strength,%20extra166y.CustomConcurrentHashMap.Equivalence,%20int)>
> <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
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20110626/aca03d08/attachment.html>


More information about the Concurrency-interest mailing list