Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (578)
games submitted by our members
Games in WIP (498)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  WeakHashMap, canonical cache and value recycling?  (Read 3005 times)
0 Members and 1 Guest are viewing this topic.
Offline nsigma
« Posted 2011-08-16 12:57:01 »

Hi All,

I'm looking to implement a canonical caching strategy in a few places.  WeakHashMap would normally be ideal for this, but I need a variant that lets me grab the values as the keys are collected (for a variety of reasons, including recycling in some cases).  As far as I'm aware, this isn't possible with WeakHashMap.  Does anyone know of a good performing alternative that allows for grabbing values as they come up to be cleared?

Thanks, Neil

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Dx4

Junior Member


Medals: 5



« Reply #1 - Posted 2011-08-16 13:26:40 »

Use a ReferenceQueue when adding keys/values to the map

example:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
ReferenceQueue<MyData> mQueue = new ReferenceQueue<MyData>();
Map<String, MyData> map = new HashMap();

class MyData extends SoftReference/WeakReference {
  YourKey key;
  MyData(Referent r, YourKey key) {
   super(r, mQueue);
   this.key = key;
  }
}

to add to cache

void put(YourKey key, Referent r) {
  map.put(new MyData(r, key));
}

then to read the recycled objects

while (true) {
 MyData data = mQueue.poll();
 if (data == null) break;
 ...process here
}


HTH

- David
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2011-08-16 13:35:54 »

WeakHashMap would normally be ideal for this

WeakHashMap is very unlikely to be a good choice. Its non-strongly-referenced references will be cleared on every GC (in Suns/Oracles JVM), as opposed to only during a full GC, which you probably want. It can easily run a couple of times per second, which kinda invalidates it as a cache.

What you probably need is a SoftHashMap, which (annoyingly) is not in the standard API. Pick a 3rd party one.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline nsigma
« Reply #3 - Posted 2011-08-16 14:37:19 »

Thanks both for your replies.
Use a ReferenceQueue when adding keys/values to the map
Do you mean basically reimplement WeakHashMap, which I'm happy to do but am hoping not to have to, or just wrapping the keys in a second weak reference?  I'm pretty sure the second wouldn't work because by the time I try and get the value out of the map it'll already be nulled.

I don't understand your example - aren't you calling map.put() with a single argument?

WeakHashMap is very unlikely to be a good choice. Its non-strongly-referenced references will be cleared on every GC (in Suns/Oracles JVM), as opposed to only during a full GC, which you probably want. It can easily run a couple of times per second, which kinda invalidates it as a cache.

What you probably need is a SoftHashMap, which (annoyingly) is not in the standard API. Pick a 3rd party one.

I could have put bets on someone saying this!  Grin

No, I want a WeakHashMap!  I understand it's not much use as a cache in itself, though neither usually would a SoftHashMap be - you want a map to soft referenced values.  In fact, I have a slight feeling of deja vu - I'm pretty sure we've had that conversation in another thread.  Smiley

There's a good article here on this http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html

So why do I want a WeakHashMap?  Quote from same article on "What is the WeakHashMap good for?"

Quote
If the WeakHashMap is no good for caching, then what is it good for? It is good to implement canonical maps. Lets say you want to associate some extra information to an object that you have a strong reference to. You put an entry in a WeakHashMap with the object as the key, and the extra information as the map value. Then, as long as you keep a strong reference to the object, you will be able to check the map to retrieve the extra information. And once you release the object, the map entry will be cleared and the memory used by the extra information will be released.

This is basically what I'm trying to do - associate a cached object (most likely soft referenced) with a particular object - should have been clearer earlier!  I want the keys to be GC'd as soon as possible, because once the key is unreferenced, the value is unreachable.  The problem is, I want to get the values added to a queue on clearing the key so that I can do other things with them, rather than just having them set to null.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Dx4

Junior Member


Medals: 5



« Reply #4 - Posted 2011-08-16 14:59:45 »

Thanks both for your replies.
Use a ReferenceQueue when adding keys/values to the map
Do you mean basically reimplement WeakHashMap, which I'm happy to do but am hoping not to have to, or just wrapping the keys in a second weak reference?  I'm pretty sure the second wouldn't work because by the time I try and get the value out of the map it'll already be nulled.

I don't understand your example - aren't you calling map.put() with a single argument?

WeakHashMap is very unlikely to be a good choice. Its non-strongly-referenced references will be cleared on every GC (in Suns/Oracles JVM), as opposed to only during a full GC, which you probably want. It can easily run a couple of times per second, which kinda invalidates it as a cache.

What you probably need is a SoftHashMap, which (annoyingly) is not in the standard API. Pick a 3rd party one.

I could have put bets on someone saying this!  Grin

No, I want a WeakHashMap!  I understand it's not much use as a cache in itself, though neither usually would a SoftHashMap be - you want a map to soft referenced values.  In fact, I have a slight feeling of deja vu - I'm pretty sure we've had that conversation in another thread.  Smiley

There's a good article here on this http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html

So why do I want a WeakHashMap?  Quote from same article on "What is the WeakHashMap good for?"

Quote
If the WeakHashMap is no good for caching, then what is it good for? It is good to implement canonical maps. Lets say you want to associate some extra information to an object that you have a strong reference to. You put an entry in a WeakHashMap with the object as the key, and the extra information as the map value. Then, as long as you keep a strong reference to the object, you will be able to check the map to retrieve the extra information. And once you release the object, the map entry will be cleared and the memory used by the extra information will be released.

This is basically what I'm trying to do - associate a cached object (most likely soft referenced) with a particular object - should have been clearer earlier!  I want the keys to be GC'd as soon as possible, because once the key is unreferenced, the value is unreachable.  The problem is, I want to get the values added to a queue on clearing the key so that I can do other things with them, rather than just having them set to null.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
class WeakHashMap<K, V> {
   ReferenceQueue<KeyValuePair> Q = new ReferenceQueue();
   HashMap<K, KeyValuePair<K,V>> M = new HashMap();
   class KeyValuePair<K, V> extends WeakReference<K, V> {
      V value;
     
      KeyValuePair(K key, V value) {
         super(K, Q);
         this.value = value;
      }
   }
   
   public void put(K key, V value) {
      M.put(key, new KeyValuePair(K, V));
   }
   
   public V get(K key) {
      KeyValuePair KVP = M.get(key);
      if (KVP != null) {
       return KVP.value;
      }
      return null;
   }
   
   public void recycle() {
      while (true) {
         KeyValuePair KVP = Q.poll();
         if (KVP != null) {
            V value = KVP.value;
            // do something with value
        }
      }
   }
   
   // etc..
 
}


HTH

- David
Offline nsigma
« Reply #5 - Posted 2011-08-16 15:26:34 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
class WeakHashMap<K, V> {
   ReferenceQueue<KeyValuePair> Q = new ReferenceQueue();
   HashMap<K, KeyValuePair<K,V>> M = new HashMap();
   class KeyValuePair<K, V> extends WeakReference<K, V> {
      V value;
     
      KeyValuePair(K key, V value) {
         super(K, value);
         this.value = value;
      }
   }
   
   public void put(K key, V value) {
      M.put(key, new KeyValuePair(K, V));
   }
   
   public V get(K key) {
      KeyValuePair KVP = M.get(key);
      if (KVP != null) {
       return KVP.value;
      }
      return null;
   }
   
   public void recycle() {
      while (true) {
         KeyValuePair KVP = Q.poll();
         if (KVP != null) {
            V value = KVP.value;
            // do something with value
        }
      }
   }
   
   // etc..
 
}


HTH

- David


Thanks, David, but isn't that storing the value as a weak reference and not the key?  I need the same semantics as WeakHashMap, with the key being wrapped in a weak reference. 

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Dx4

Junior Member


Medals: 5



« Reply #6 - Posted 2011-08-16 15:31:14 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
class WeakHashMap<K, V> {
   ReferenceQueue<KeyValuePair> Q = new ReferenceQueue();
   HashMap<K, KeyValuePair<K,V>> M = new HashMap();
   class KeyValuePair<K, V> extends WeakReference<K, V> {
      V value;
     
      KeyValuePair(K key, V value) {
         super(K, value);
         this.value = value;
      }
   }
   
   public void put(K key, V value) {
      M.put(key, new KeyValuePair(K, V));
   }
   
   public V get(K key) {
      KeyValuePair KVP = M.get(key);
      if (KVP != null) {
       return KVP.value;
      }
      return null;
   }
   
   public void recycle() {
      while (true) {
         KeyValuePair KVP = Q.poll();
         if (KVP != null) {
            V value = KVP.value;
            // do something with value
        }
      }
   }
   
   // etc..
 
}


HTH

- David


Thanks, David, but isn't that storing the value as a weak reference and not the key?  I need the same semantics as WeakHashMap, with the key being wrapped in a weak reference.  

The key is the weak reference, look at the KVP constructor

Btw typo:

1  
super(K, value);


should be

1  
super(key, Q);
Offline nsigma
« Reply #7 - Posted 2011-08-16 15:50:39 »

The key is the weak reference, look at the KVP constructor

I know you're storing the key as a weak reference in the KVP object.

However, surely doing -

1  
2  
3  
 public void put(K key, V value) {
        M.put(key, new KeyValuePair(K, V));
    }


means the key is stored as a strong reference in the map as well, so will never be collected.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Dx4

Junior Member


Medals: 5



« Reply #8 - Posted 2011-08-16 17:16:31 »

well then you could just override hashCode and use this

1  
2  
3  
4  
5  
6  
7  
public int hashCode() {
 K key = get();
 if (key == null) {
  return 0;
 }
 return key.hashCode();
}


put:

1  
2  
3  
4  
public void put(K key, V value) {
KeyValuePair kvp = new KeyValuePair(key, value);
       M.put(kvp, kvp);
   }


full:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
class WeakHashMap<K, V> {
    ReferenceQueue<KeyValuePair> Q = new ReferenceQueue();
    HashMap<K, KeyValuePair<K,V>> M = new HashMap();
    class KeyValuePair<K, V> extends WeakReference<K, V> {
        V value;
         
        KeyValuePair(K key, V value) {
            super(key, Q);
            this.value = value;
        }
     
      @Override
      public int hashCode() {
         K key = get();
         if (key == null) {
            return 0;
         }
         return key.hashCode();
      }
    }
     
    public void put(K key, V value) {
      KeyValuePair kvp = new KeyValuePair(K, V);
        M.put(kvp, kvp);
    }
     
    public V get(K key) {
        KeyValuePair KVP = M.get(key);
        if (KVP != null) {
         return KVP.value;
        }
        return null;
    }
     
    public void recycle() {
        while (true) {
            KeyValuePair KVP = Q.poll();
            if (KVP != null) {
                V value = KVP.value;
                // do something with value
           }
        }
    }
     
    // etc..
   
}
Offline philfrei
« Reply #9 - Posted 2011-08-16 19:56:05 »

Quote
This is basically what I'm trying to do - associate a cached object (most likely soft referenced) with a particular object - should have been clearer earlier!  I want the keys to be GC'd as soon as possible, because once the key is unreferenced, the value is unreachable.  The problem is, I want to get the values added to a queue on clearing the key so that I can do other things with them, rather than just having them set to null.

Maybe go back a step? Make a finalize() method on the object itself, and have THAT put the value on the queue. The GC will check finalize() as well as clearing the key from your cache. I'm not sure of the exact timing, but the two events should be directly tied together, yes?

If only some of the objects are in your cache, encode that as a property to be consulted by finalize().

Could be cleaner than going through a lot of rigamarole with special cache handling?

In any case, though, it seems the exact timing of what you are doing is "passive" and things have to be handled carefully to avoid concurrency issues.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline nsigma
« Reply #10 - Posted 2011-08-16 21:15:08 »

Hi Phil,

Thanks for your response.
Maybe go back a step? Make a finalize() method on the object itself, and have THAT put the value on the queue. The GC will check finalize() as well as clearing the key from your cache. I'm not sure of the exact timing, but the two events should be directly tied together, yes?

If only some of the objects are in your cache, encode that as a property to be consulted by finalize().

Could be cleaner than going through a lot of rigamarole with special cache handling?

Normally I'd agree with you, but this involves a number of situations where I can't (easily) edit the key objects concerned.  One situation involves objects from a 3rd party library, and the other would involve circular module dependencies. 

You did trigger a related thought though (at least I think it's related, it might be what you meant!) - I might be able to get away with wrapping the current value object in a lightweight wrapper that uses finalize().

I also may have managed to find a 3rd-party solution - http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/com/google/common/collect/MapMaker.html#evictionListener%28com.google.common.collect.MapEvictionListener%29 - first thing I've found ready-made that seems to offer a solution.  Have no idea what the performance will be like, and a bit wary it's beta tagged.  Other suggestion still welcomed.

And I realise all the added complexity of this may turn out just not to be worth it and I'll end up sticking with a plain WeakHashMap!  Smiley

well then you could just override hashCode
I'm pretty sure that would still not work unless you also overrode equals(), and that would end up in equals() having asymmetric qualities which are sure to blow up somewhere!

Thanks and best wishes, Neil

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline philfrei
« Reply #11 - Posted 2011-08-17 00:37:36 »

Sure, maybe a wrapper makes sense. Whatever it takes to make the objects themselves be the instigators, rather than having to monitor their presence in your cache.

Mostly, I was just thinking that maybe there was an event "upstream" that could solve your problem rather than dealing with it from the POV of the cache. It felt from the description that things were getting kind of hairy.

HOWEVER, for lunch, I just finished chapter 7 in "Java Concurrency in Practice" and they strongly recommend avoiding finalizers. They say it's better to have and use a close() method for an object than to rely on a finalizer. Or, if there is a "try" involved, making good use of the finally block.

So, I take back the finalizer suggestion, and leave it as suggesting a look upstream for an alternative moment to put the objects in your queue. (A wrapper with a close() method that manages the queue entry?)
 

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline nsigma
« Reply #12 - Posted 2011-08-17 13:10:22 »

Sure, maybe a wrapper makes sense. Whatever it takes to make the objects themselves be the instigators, rather than having to monitor their presence in your cache.

Mostly, I was just thinking that maybe there was an event "upstream" that could solve your problem rather than dealing with it from the POV of the cache. It felt from the description that things were getting kind of hairy.

HOWEVER, for lunch, I just finished chapter 7 in "Java Concurrency in Practice" and they strongly recommend avoiding finalizers. They say it's better to have and use a close() method for an object than to rely on a finalizer. Or, if there is a "try" involved, making good use of the finally block.

So, I take back the finalizer suggestion, and leave it as suggesting a look upstream for an alternative moment to put the objects in your queue. (A wrapper with a close() method that manages the queue entry?)
 


For lunch, I tend to prefer a sandwich ...  Tongue

Yes, finalize() introduces some interesting concurrency issues, so probably isn't the right approach.  Unfortunately, I can't use the explicit close() approach here.  I'm talking about various usages in a library, where objects are passed in from user code - the only way to know for definite that the user object will not be passed in again, and cached information is definitely no longer required, is when they go out of scope.  My understanding is that this is exactly what WeakHashMap was written for.

I'll probably experiment with the Guava approach as this will also allow the cached information to be soft referenced and the possibility of LRU within one map - see if it's all worth the complexity.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (27 views)
2014-04-15 18:08:23

BurntPizza (23 views)
2014-04-15 03:46:01

UprightPath (38 views)
2014-04-14 17:39:50

UprightPath (20 views)
2014-04-14 17:35:47

Porlus (36 views)
2014-04-14 15:48:38

tom_mai78101 (61 views)
2014-04-10 04:04:31

BurntPizza (119 views)
2014-04-08 23:06:04

tom_mai78101 (219 views)
2014-04-05 13:34:39

trollwarrior1 (186 views)
2014-04-04 12:06:45

CJLetsGame (193 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!