[concurrency-interest] Memory sensitive memoization

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


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/d4e22904/attachment.html>


More information about the Concurrency-interest mailing list