search

MedwynLiang / google-collections

Automatically exported from code.google.com/p/google-collections
Apache License 2.0
0 stars 0 forks source link

Equality comparison semantics for weak/soft references in MapMaker #250

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
MapMaker is very convenient as in-memory cache with the soft keys feature, 
but identity comparison semantic could be a huge limitation (for instance, if 
one wants Long ID as key).
So, an option to switch comparison semantic would be great (of course, by 
default it should be equality for strong references and identity for 
weak/soft ones).

Original issue reported on code.google.com by Andrey.A...@gmail.com on 26 Sep 2009 at 5:30

GoogleCodeExporter commented 9 years ago 
Let's say you have a cache with weak keys of type Long, and the value 12345 is 
mapped
to some value in the cache.  You would like this value to be returned for *any* 
Long
with value 12345, not just the one that was used to store it.

Which of these behaviors would you expect to happen?

(a) this entry is reclaimed once *any* reference to a Long with value 12345 is 
reclaimed.
(b) this entry is reclaimed only once *all* references to Longs with value 
12345 are
reclaimed.

To me, (a) is arbitrary and makes no sense, and as for (b), how would you 
propose to
implement that?

Original comment by kevin...@gmail.com on 27 Sep 2009 at 4:10

GoogleCodeExporter commented 9 years ago 
(a) makes sense for caches where you can re-calculate or re-load cache value. 
E.g.:

// http://mathworld.wolfram.com/DistinctPrimeFactors.html
public class PrimeNuCache {

    private final ConcurrentMap<Long, Integer> cache = new 
MapMaker().softKeys().makeMap();

    public int get(long x) {
        if (!cache.containsKey(x)) {
            cache.putIfAbsent(x, calcPrimeNu(x));
        }
        return cache.get(x);
    }

    private int calcPrimeNu(long x) {
        // implementation of this CPU-consuming func
    }
}

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 4:56

GoogleCodeExporter commented 9 years ago 
mea culpa, corrected example

public class PrimeNuCache {

        private final ConcurrentMap<Long, Integer> cache = new MapMaker()
            .softKeys().equalitySemantics().makeMap();

    public int get(long x) {
        Integer cached = cache.get(x);
        if (cached == null) {
            int calculated = calcPrimeNu(x);
            cache.putIfAbsent(x, calculated);
            return calculated;
        } else {
            return cached;
        }
    }

    private int calcPrimeNu(long x) {
        // implementation of this CPU-consuming func
    }
}

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 5:01

GoogleCodeExporter commented 9 years ago 
It's virtually always going to be the case that "you can re-calculate or 
re-load the 
cache value"; it wouldn't be a "cache" otherwise, and you wouldn't want to use 
MapMaker.

I still cannot understand why (a) would ever make any sense.  You might place 
an 
entry in the cache and then have it immediately cleaned up just because some 
random 
other instance of that key, used in some completely unrelated part of the 
program, 
happened to be gc'd. Where is the sense in that?

Original comment by kevin...@gmail.com on 28 Sep 2009 at 5:19

GoogleCodeExporter commented 9 years ago 
"Virtual machine implementations are, however, encouraged to bias against 
clearing 
recently-created or recently-used soft references."

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 5:22

GoogleCodeExporter commented 9 years ago 
First, that doesn't really change the nature of my question substantially.

Second, this enhancement request does cover weak references, not just soft.

I remain extremely skeptical of the value of this feature.

Original comment by kevin...@gmail.com on 28 Sep 2009 at 5:29

GoogleCodeExporter commented 9 years ago 
Well, I don't mind if equality semantics will be enabled only for soft 
references, not 
weak ones (though it is enabled in WeakHashMap). 
Soft keys are natural in creating caches constrained by available heap memory 
(http://www.ibm.com/developerworks/java/library/j-jtp01246.html).
With this feature we could extremely easy create concurrent cache with 
memory-driven 
eviction policy.

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 5:34

GoogleCodeExporter commented 9 years ago 
The fact that WeakHashMap uses object equality instead of identity equality is 
broken, and it was Bob's desire to correct that that first led to the 
development of 
this code in the first place.

Thanks for the link, but I know what soft references are already.

Since repeated attempts to get actual new information that would demonstrate 
the 
value of this feature are not being answered, I'll close this bug now.

Original comment by kevin...@gmail.com on 28 Sep 2009 at 5:41

GoogleCodeExporter commented 9 years ago 
Maybe I don't understand something, but to make identity semantic cache work 
you need 
to cache keys (like in Byte.ByteCache), but it's not possible for, say, Long's

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 6:27

GoogleCodeExporter commented 9 years ago 
Andrey, you want soft values, not soft keys.

Original comment by crazybob...@gmail.com on 28 Sep 2009 at 6:38

GoogleCodeExporter commented 9 years ago 
I want soft keys. Consider PrimeNuCache example I put above. Many long keys 
will be 
mapped to a single int value < 127 (and Integer objects <127 are cached). If 
values 
were soft, then GC of one (small) value could remove thousands of entries.

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 6:55

GoogleCodeExporter commented 9 years ago 
Actually, the soft value reference would never be cleared because you will 
always have a 
strong ref to the Integer object in Integer. If you don't want that behavior, 
you should 
just always create a new Integer instance instead of going through valueOf(). 
That solves 
the problem more directly than making the keys soft.

Original comment by crazybob...@gmail.com on 28 Sep 2009 at 7:17

GoogleCodeExporter commented 9 years ago 
OK, probably soft values will work for me, let me double check. Thanks for the 
advise.

Original comment by Andrey.A...@gmail.com on 28 Sep 2009 at 7:22

GoogleCodeExporter commented 9 years ago 
I don't know if I get it wrong, but if the values is an Enum, then our cache 
would never be GC-ed then. In this 
case, we still need a soft keys and thus an equal comparison semantics.

Original comment by nanda.firdausi on 15 Nov 2009 at 9:35

GoogleCodeExporter commented 9 years ago 
I want .equals() comparison semantics on weak keys, so that I can build the 
equivalent of String.intern() for whatever objects I want. To me this seems 
impossible with MapMaker as it stands, am I missing something?

Original comment by jonat...@gmail.com on 22 Oct 2010 at 8:53

GoogleCodeExporter commented 9 years ago 
You can build an interner for any object.  You want to use strong keys and weak 
or soft values.  Strong keys will give you the .equals() behavior and weak or 
soft values will cause the map entry to be GCed.

Original comment by blair-ol...@orcaware.com on 23 Oct 2010 at 2:46

GoogleCodeExporter commented 9 years ago 
I have hit a situation where equality semantics for a weakly-keyed maps are 
extremely useful. My full use case is too involved to discuss, but at a very 
high and very simplified level, it’s a client-server application. The weak 
map is storing a mapping between UUIDs and outstanding client-issued 
operations. The UUIDs are nonces and are put() into the map *once*. On receive, 
I need to look up the operations stored in the map by UUIDs decoded from 
incoming messages. Identity semantics simply don’t allow this to work. 
Equality semantics do. As a result, a WeakHashMap can support this use-case 
(except for the lack of concurrency), but a Guava weakly keyed map can’t. 
Ergo, I disagree with the brokenness of WeakHashMap’s usage of .equals().

The point, here, of the weakly keyed map is to free memory when the 
UUID-operation mapping is no longer needed. I.e. as the UUIDs are no longer 
referenced by the operation issuer, the mappings are automatically cleaned up. 
In the simplified case above, of course, one could also manually remove the 
mapping. In the full use-case, however, the mapping is more complicated and 
manual removal would effectively require a by-hand reference counting 
implementation. Ugly. A weak map allows Java’s GC to automatically remove 
mappings when they are no longer needed. Beautiful.

In a nutshell, using a weakly keyed map greatly simplifies my code, but I 
require equality support to do it. My current solution is to fork Guava to add 
the feature. Not ideal.

Original comment by glenn.ki...@gmail.com on 4 Dec 2012 at 3:44

GoogleCodeExporter commented 9 years ago 
Not sure how complex your keys are but it may work to make them  
Strings and intern() them.

Original comment by jonat...@gmail.com on 4 Dec 2012 at 6:51