[concurrency-interest] Memory sensitive memoization

Bob Lee crazybob at crazybob.org
Sun Jun 26 11:46:45 EDT 2011


Sounds like you want a soft reference to the values, not the keys (MapMaker
will remove the entire entry when the value gets reclaimed).

Bob

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

> 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
>>>
>>>
>>
>
> _______________________________________________
> 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/2c25dcd4/attachment.html>


More information about the Concurrency-interest mailing list