Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (480)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (547)
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  
  Object cache  (Read 1430 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd
« Posted 2012-11-03 03:49:43 »

I am creating an awful amount of Point objects (my own Point object, not the standard one) to store selected points in a 3D space in hashmaps/lists. I realized that I might be getting an unhealthy number of instances of the same Point object (this is actually a real problem thanks to mass selection + storing changes to allow for undoing/redoing), so I implemented a cache based on a simple HashMap that stored Point instances. However, I also wanted the cache to clear Points that aren't in use anywhere, so I added a reference counter to the Point class so I can keep track on if it's okay to remove them completely from the HashMap. This turned out to be more messy than I thought since I have to be sure not to screw up the count manually every time I do something with them. Is there any way of automating this? I basically want instances of Point that only exist in the PointCache and aren't used anywhere else to be automatically garbage collected and removed from the PointCache. It's a bit similar to how a daemon thread works. I want my Point objects to be garbage collected when they only exist in the PointCache.

Myomyomyo.
Offline ctomni231

JGO Wizard


Medals: 99
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #1 - Posted 2012-11-03 03:54:29 »

Well, you can always use a Bag system.

http://www.java-gaming.org/topics/implementing-and-using-an-array-backed-bag/27172/view.html

But, given the huge amount of points you are creating, it might be a better idea to make two single integer arrays (one for x and one for y) and add/remove the points from there. It should be a lot quicker, unless you really want to use OOP for this task.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2012-11-03 04:08:18 »

WeakHashMap ! (be sure to read the javadoc, values are not stored as weak references!)

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 sproingie

JGO Kernel


Medals: 202



« Reply #3 - Posted 2012-11-03 04:46:24 »

Use Guava's CacheBuilder and you can have weak keys, weak values, both, expiration, eviction policies, statistics, and so on and so forth.  Extremely spiffy stuff, I use it as a fast duplicate eliminator in my apps in front of Ehcache.
Offline nsigma
« Reply #4 - Posted 2012-11-03 14:21:01 »

WeakHashMap ! (be sure to read the javadoc, values are not stored as weak references!)

@theagentd - how are you retrieving the Point instances?  Creating a Point, seeing if it already exists and discarding the new one?  If so, using WeakHashMap basically as a WeakHashSet could work - seen a few implementations of this that just put Boolean.TRUE as every value.

If you want to create from raw coordinates, you could maybe look at something like an IntHashMap with the keys being the hash of the Point object.  The values are PointReferences (or a list if you can't guarantee no hash collision), which extends WeakReference<Point> and includes an int field for the hashcode, so that the reference can be removed on collection.  It's similar to the Entry inner class in the WeakHashMap.

Use Guava's CacheBuilder and you can have weak keys, weak values, both, expiration, eviction policies, statistics, and so on and so forth.

Probably OT, but you missed my favourite feature here, and one I wish was in WeakHashMap - the ability to listen for evictions and recycle or dispose the value objects - thinking particularly for use in a texture cache.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline theagentd
« Reply #5 - Posted 2012-11-03 14:46:15 »

Here's my full PointCache class:
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  
import java.util.HashMap;

public class PointCache {
   
   private static HashMap<Long, Point> cache = new HashMap<>();
   
   private PointCache(){}
   
   public static Point get(int x, int y, int z){
      long key = ((long)x << 48) | ((long)y << 24) | z;

      Point p = cache.get(key);
      if(p == null){
         p = new Point(x, y, z);
         cache.put(key, p);
      }
     
      p.incRefCount();
      return p;
   }

   //Called by Point when the reference count becomes 0
  protected static void remove(Point p) {
      long key = ((long)p.x() << 48) | ((long)p.y() << 24) | p.z();
      cache.remove(key);
   }
}


WeakHashMap ! (be sure to read the javadoc, values are not stored as weak references!)
That's a big problem in my case. Since I use autoboxed Long values, the values that aren't cached by the VM will be immediately reclaimed by the GC. I want the values to be weak references and the whole entry (key + value) to be removed when the value gets reclaimed.

Use Guava's CacheBuilder and you can have weak keys, weak values, both, expiration, eviction policies, statistics, and so on and so forth.  Extremely spiffy stuff, I use it as a fast duplicate eliminator in my apps in front of Ehcache.
This seems a bit overkill. The objects aren't expensive at all to create. I just want to minimize memory usage as much as possible, so the overhead of something as advanced might defeat the purpose of it all. Thanks anyway, seems like that cache builder might come in handy sometime.

@nsigma
The key I generate now assures me that I have no collisions, though I don't think it's a very good hash code (performance-wise). It's quick to generate though.  The key does not fit in an int.


Maybe the simplest way is just to use a normal HashMap and wrap the Points in WeakReferences. Sadly it seems like WeakReferences are pretty heavyweight and contain lots of stuff, so simply the overhead of the WeakReferences might defeat the purpose of it all. I'd also have to periodically clear all dead WeakReferences from the hash map too...

Myomyomyo.
Offline nsigma
« Reply #6 - Posted 2012-11-03 15:06:52 »

@nsigma
The key I generate now assures me that I have no collisions, though I don't think it's a very good hash code (performance-wise). It's quick to generate though.  The key does not fit in an int.

Maybe the simplest way is just to use a normal HashMap and wrap the Points in WeakReferences. Sadly it seems like WeakReferences are pretty heavyweight and contain lots of stuff, so simply the overhead of the WeakReferences might defeat the purpose of it all. I'd also have to periodically clear all dead WeakReferences from the hash map too...

Well, quick Google for a LongHashMap found this in JogAmp - http://jogamp.org/deployment/v2.0-rc6/javadoc/gluegen/javadoc/com/jogamp/common/util/LongObjectHashMap.html  Get rid of the need to autobox, and should be optimised for the data type.

For the values create a PointReference class as I suggested. ie.

1  
2  
3  
4  
5  
6  
7  
8  
9  
class PointReference extends WeakReference<Point> {

  long key;

  PointReference(Point point, ReferenceQueue<Point> queue, long key) {
    super(point, queue);
    this.key = key;
   
    // etc...


That way you drain the queue periodically, grabbing the keys from the references and remove them from the map - then you don't need to iterate through looking for dead references.

Definitely one to benchmark, though.  You might be right about the overhead.

EDIT: If this is purely about memory overhead, you should probably also consider the PointReference extending SoftReference if it's likely that you'll want the same points again.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline theagentd
« Reply #7 - Posted 2012-11-03 15:40:22 »

@nsigma
The key I generate now assures me that I have no collisions, though I don't think it's a very good hash code (performance-wise). It's quick to generate though.  The key does not fit in an int.

Maybe the simplest way is just to use a normal HashMap and wrap the Points in WeakReferences. Sadly it seems like WeakReferences are pretty heavyweight and contain lots of stuff, so simply the overhead of the WeakReferences might defeat the purpose of it all. I'd also have to periodically clear all dead WeakReferences from the hash map too...

Well, quick Google for a LongHashMap found this in JogAmp - http://jogamp.org/deployment/v2.0-rc6/javadoc/gluegen/javadoc/com/jogamp/common/util/LongObjectHashMap.html  Get rid of the need to autobox, and should be optimised for the data type.

For the values create a PointReference class as I suggested. ie.

1  
2  
3  
4  
5  
6  
7  
8  
9  
class PointReference extends WeakReference<Point> {

  long key;

  PointReference(Point point, ReferenceQueue<Point> queue, long key) {
    super(point, queue);
    this.key = key;
   
    // etc...


That way you drain the queue periodically, grabbing the keys from the references and remove them from the map - then you don't need to iterate through looking for dead references.

Definitely one to benchmark, though.  You might be right about the overhead.

EDIT: If this is purely about memory overhead, you should probably also consider the PointReference extending SoftReference if it's likely that you'll want the same points again.

Ah! ReferenceQueues!

This seems reasonable. Performance is not my main concern here. Soft references might be more what I want then.


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  
48  
49  
50  
51  
52  
53  
54  
import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.HashMap;

/**
 * This class is not thread safe (but neither is the caller in my case)
 */

public class PointCache {
   
   private static HashMap<Long, PointReference> cache = new HashMap<>();
   private static ReferenceQueue<Point> queue = new ReferenceQueue<>();

   public static Point get(int x, int y, int z){
      Long key = getKey(x, y, z);
      PointReference pr = cache.get(key);
      if(pr != null){
         Point p = pr.get();
         if(p != null){
            return p;
         }
      }
      Point p = new Point(x, y, z);
      cache.put(key, new PointReference(p, queue, key));
      return p;
   }
   
   public static void clearDeadReferences(){
      Reference<? extends Point> r;
      while((r = queue.poll()) != null){
         PointReference pr = (PointReference) r;
         cache.remove(pr.getKey());
         System.out.println("Removed an entry from the point cache.");
      }
   }
   
   private static Long getKey(int x, int y, int z){
      return ((long)x << 48) | ((long)y << 24) | z;
   }

   private static class PointReference extends WeakReference<Point>{
     
      private Long key;

      public PointReference(Point p, ReferenceQueue<Point> queue, Long key) {
         super(p, queue);
         this.key = key;
      }
     
      public Long getKey(){
         return key;
      }
   }
}


Tried this code, output:
Quote
Disposing an action (removed an object referring to some Points)
Disposing an action
<5 second pause>
Removed an entry from the point cache.
Removed an entry from the point cache.
Removed an entry from the point cache.
Removed an entry from the point cache.
Removed an entry from the point cache.

Does exactly what I want. I just have to change it to a SoftReference instead to make it more cachy. =S

Thanks everyone! This is a LOT simpler than keeping track of the reference count. Let's hope it works out performance wise too. =S

Myomyomyo.
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.

atombrot (23 views)
2014-08-19 09:29:53

Tekkerue (22 views)
2014-08-16 06:45:27

Tekkerue (21 views)
2014-08-16 06:22:17

Tekkerue (12 views)
2014-08-16 06:20:21

Tekkerue (19 views)
2014-08-16 06:12:11

Rayexar (57 views)
2014-08-11 02:49:23

BurntPizza (37 views)
2014-08-09 21:09:32

BurntPizza (29 views)
2014-08-08 02:01:56

Norakomi (36 views)
2014-08-06 19:49:38

BurntPizza (66 views)
2014-08-03 02:57:17
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!