[concurrency-interest] Memory sensitive memoization

Sanchay Harneja sanchay.h at gmail.com
Sun Jun 26 09:43:13 EDT 2011


Hi Tim,

According to my understanding, unfortunately, Guava MapMaker has a
limitation which makes it unusable in this instance:

*Note:* by default, the returned map uses equality comparisons (the
equals<http://download.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#equals(java.lang.Object)>
 method) to determine equality for keys or values. However, if
weakKeys()<http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/com/google/common/collect/MapMaker.html#weakKeys()>
 or softKeys()<http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/com/google/common/collect/MapMaker.html#softKeys()>
 was specified, the map uses identity (==) comparisons instead for keys.

Not sure why they have that limitation. I would want to use .equals for soft
keys.

Thanks!

On Sun, Jun 26, 2011 at 6:29 PM, Tim Peierls <tim at peierls.net> wrote:

> 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/2f02b020/attachment-0001.html>


More information about the Concurrency-interest mailing list