[concurrency-interest] Memory sensitive memoization

Sanchay Harneja sanchay.h at gmail.com
Sun Jun 26 12:17:09 EDT 2011


Hi Bob,

Indeed, MapMaker's javadoc says:

If strong or weak references were requested, it is possible for a key or
value present in the the map to be reclaimed by the garbage collector. If
this happens, the entry automatically disappears from the map.

But I find this somewhat counter intuitive.

Thanks for pointing that out though!

- Sanchay

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

> Hi Bob,
>
> I would prefer soft reference to key, as just the keys themselves might be
> too many.
>
> Thanks,
> Sanchay
>
>
> On Sun, Jun 26, 2011 at 9:16 PM, Bob Lee <crazybob at crazybob.org> wrote:
>
>> 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/8e20e080/attachment-0001.html>


More information about the Concurrency-interest mailing list