Implementation of a cache using soft references both for keys and values

Question

I'd like to implement a cache whose keys and values are soft references because the instances that it will contain can take a long time to be computed (especially the values) and I'd like the entries containing unreferenced objects as keys or as values to get garbage collected if and only if I may run out of memory. If I used weak references for the values, they would be garbage collected as soon as they aren't referenced which isn't what I want to do.

At first, I used this example. It works but creating a single thread per cache instance annoys me, it uses strong references for the keys and expunging stale entries by myself (like WeakHashMap) in some method calls of the cache class doesn't work (obviously) when I risk to run out of memory when I don't call them. I wanted to use Guava but MapMaker does no longer allow the use of soft keys which is logical as the default equivalence is based on equality (==) and not on the equals() method which means that it's impossible to recreate an identical key. However, I agree with sebastien-lorber's comment:

i think soft keys would make sense if Guava was overriding equals method of the SoftReference. I've seen that Guava uses an "equivalence mecanism" and i think, for soft references, the defaultEquivalence should not be identity but equals, to handle such a case.

I looked at MapDB and JCS too.

How can I modify the example I quoted above or use Guava to make a cache based on soft references, preferably using equals() instead of == to determine the equality of keys?

score 1 · Answer 1 · edited Jun 20 '20 at 09:12

I guess the only perfect solution would be to have a CacheBuilder.softKeysDelegatingEquals in Guava as you proposed.

Skip to the end for a much better idea

Maybe this workaround would do:

whenever you put something in the Cache, put a new SoftReference<Key> into your own HashSet.
add a removalListener to the Cache and remove the SoftReference from your HashSet

Anyway, you need no thread.

The second part is a bit tricky as you're given a Key and need to remove its corresponding soft reference. For this you could either replace the set by a WeakHashMap<Key, SoftReference<Key>, or get hacky by letting your Key being equals to the reference:

class Key {
    Key(Somedata somedata) {
        this.somedata = somedata;
    }

    @Override public int hashCode() {
        return somedata.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj instanceof Key) {
            return somedata.equals(((Key) obj).somedata);
        }
        if (obj instanceof KeySoftReference) {
            return equals(((KeySoftReference) obj).get());
        }
        return false;
    }

    @NonNull private final Somedata somedata;
}

// Hacky, never use for anything else.
class KeySoftReference extends SoftReference<Key> {
    protected KeySoftReference(Key key) {
        super(key);
        this.hashCode = key.hashCode();
    }

    @Override public int hashCode() {
        return hashCode;
    }

    @Override public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj instanceof Key) {
            return ((Key) obj).equals(this);
        }
        if (obj instanceof KeySoftReference) {
            Key key = get();
            // This makes no two cleared reference equal to each other,
            // That's OK as long as you never create two references to the same object.
            return key!=null && key.equals(((KeySoftReference) obj).get());
        }
        return false;
    }

    private final int hashCode;
}

I guess, this satisfies the contract, but as I said, it's hacky and untested.

UPDATE

There's simple solution. Use

CacheBuilder.weakKeys().softValues()

and add a SoftReference<Key> to your Value. This makes the key softly reachable.

If you really need comparison be equality, then you're probably out of luck, although a WeakInterner<Key> could help.

Your last solution seems to be very interesting. I'll give it a try. Thank you very much for your very complete answer. I'll give you some feedback. — gouessej, Sep 04 '14 at 21:05

score 0 · Accepted Answer · answered Sep 05 '14 at 14:14

Actually, I've just reintroduced soft keys in Guava (removed from it in version 14) but in CacheBuilder: https://code.google.com/p/guava-libraries/issues/detail?id=1845

Then, I have to call the non public method CacheBuilder.keyEquivalence(Equivalence.equals()) in order to use equals() instead of == to compare keys. I'll let you know whether it works. I'll accept my own answer in this case. Otherwise, I'll have to use maaartinus's suggestions.

Implementation of a cache using soft references both for keys and values

2 Answers2

UPDATE