Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
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  
  GC problem with HashMap put() and clear()  (Read 6367 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Posted 2009-10-20 14:00:42 »

Hi,

I've got a garbage collection problem relating to java.util.HashMap. After profiling, I've found that the garbage collector (GC) is using around 5% of the processor time. The problem is that I create lots of HashMap.Entry's since I'm always adding to HashMaps then calling clear() to empty the HashMap again, and repeating.

I'm using the HashMaps in the A* path finding code I've been working on. I use HashMaps instead of ArrayLists to achieve constant-time get() and add()/put() operations which has sped up the algorithms, but contributed to GC time. That's because with every put(), a new HashMap.Entry is created.

What should I do to avoid the huge amount of HashMap.Entry object creation? I'm 99% certain that the HashMap.Entry creation is the problem since NetBeans profiler says that I have 248 'live' instances of HashMap.Entry lying around, but I've allocated 58,000 instances over the program's life. Those 248 live instances comprise 6,000 bytes which is 6% of the 'live' bytes.

Any thoughts appreciated  Smiley
Thanks,
Keith


Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #1 - Posted 2009-10-20 14:06:47 »

Write your own HashMap that pools and reuses entry objects?
Offline CommanderKeith
« Reply #2 - Posted 2009-10-20 14:15:49 »

Good idea! Thanks. I should have thought of that  Tongue

I googled 'HashMap that pools entries' and found this which looks perfect:
http://javolution.org/target/site/apidocs/javolution/util/FastMap.html

Quote
FastMap are reusable; they maintain an internal pool of Map.Entry objects. When an entry is removed from a map, it is automatically restored to its pool (unless the map is shared in which case the removed entry is candidate for garbage collection as it cannot be safely recycled).

Awesome  Cool  I'll try it out and report back

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2009-10-20 15:21:05 »

Thanks a lot Bleb!

javaolution.util.FastMap fixed the problem, no more excessive allocations of HashMap.Entry.

The only garbage left now is from java2D (which is surprisingly quite a lot!)


Offline JL235

JGO Coder


Medals: 10



« Reply #4 - Posted 2009-10-20 17:03:06 »

As an alternative I'd like to put forward my own CachingHashMap available as a part of my game library with the source code here (the library is still yet to be completed).

Mine is just a HashMap that caches it's entry nodes when you clear it and remove items. As such if you fill it with a million entries and then remove them all, it still has a million entry nodes stored internally. The advantage is that if you add another million then rather then making new entry nodes it'll re-use all the entry nodes from the last million. This avoids the cost of creating objects (which is where the performance is from) and means that internally it's dereferencing no objects for the GC to clean up (to clarify; it does not hang on to a reference to the items you add, just to it's internal entry nodes).

In terms of CPU performance, using my own very cheap and brief benchmarks I find the FastMap to be marginally faster then then the HashMap but marginally slower then my CachingHashMap.

Offline Jono
« Reply #5 - Posted 2009-10-20 21:34:03 »

I'm using the HashMaps in the A* path finding code I've been working on. I use HashMaps instead of ArrayLists to achieve constant-time get() and add()/put() operations which has sped up the algorithms, but contributed to GC time. That's because with every put(), a new HashMap.Entry is created.

My only thought is that there shouldn't be ArrayLists in an A* implementation in the first place. The algorithm requires a priority queue (there's a heap-based PriorityQueue class in java.util that would work), and a hash map can be used in conjunction to speed up contains() checks on the queue.

If you don't expect duplicates in the open list to occur very often then you don't need a contains() check (the duplicates will just order themselves in the queue) and the hash map can be left out.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2009-10-20 22:41:42 »

My only thought is that there shouldn't be ArrayLists in an A* implementation in the first place.

That's why he switched... Cool

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #7 - Posted 2009-10-20 23:11:26 »

My only thought is that there shouldn't be ArrayLists in an A* implementation in the first place. The algorithm requires a priority queue (there's a heap-based PriorityQueue class in java.util that would work), and a hash map can be used in conjunction to speed up contains() checks on the queue.

If you don't expect duplicates in the open list to occur very often then you don't need a contains() check (the duplicates will just order themselves in the queue) and the hash map can be left out.
Are you talking about using HashMap's etc. for the open and closed lists in A*? If not, which lists are you talking about?

See my work:
OTC Software
Offline CommanderKeith
« Reply #8 - Posted 2009-10-20 23:45:22 »

As an alternative I'd like to put forward my own CachingHashMap available as a part of my game library with the source code here (the library is still yet to be completed).

Mine is just a HashMap that caches it's entry nodes when you clear it and remove items. As such if you fill it with a million entries and then remove them all, it still has a million entry nodes stored internally. The advantage is that if you add another million then rather then making new entry nodes it'll re-use all the entry nodes from the last million. This avoids the cost of creating objects (which is where the performance is from) and means that internally it's dereferencing no objects for the GC to clean up (to clarify; it does not hang on to a reference to the items you add, just to it's internal entry nodes).

In terms of CPU performance, using my own very cheap and brief benchmarks I find the FastMap to be marginally faster then then the HashMap but marginally slower then my CachingHashMap.

Thanks JL235, that will be fantastic if i can use your CachingHashMap implementation. The Javolution FastMap requires me to use the whole 0.4MB package so your single file is much better. The only benefit that Javolution provides is that add() is constant time since the underlying array is never copied when the hashmap outgrows its capacity, but I have no use for that since my map is always re-used so it will always stay big. Thanks  Cool Out of interest, what was your reason for making the CachingHashMap? Where did you need it?

My only thought is that there shouldn't be ArrayLists in an A* implementation in the first place. The algorithm requires a priority queue (there's a heap-based PriorityQueue class in java.util that would work), and a hash map can be used in conjunction to speed up contains() checks on the queue.

If you don't expect duplicates in the open list to occur very often then you don't need a contains() check (the duplicates will just order themselves in the queue) and the hash map can be left out.

Hi Jono, thanks for your comments. Yes I use a BinaryHeap priority queue for the openList, but to eliminate use of List.contains() I also use a HashMap for the open and closed lists.




Offline Jono
« Reply #9 - Posted 2009-10-21 00:17:41 »

Hi Jono, thanks for your comments. Yes I use a BinaryHeap priority queue for the openList, but to eliminate use of List.contains() I also use a HashMap for the open and closed lists.
Ah, just a misunderstanding from your original post then. I had the impression that you had replaced an ArrayList with a Hash Map for the open list, which is obviously not the case  Grin
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #10 - Posted 2009-10-21 00:26:10 »

I'd like to use the Javolution collections and text stuff in some of my projects. I wish the JAR wasn't 400+ kb! The classes aren't easily extracted either.

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #11 - Posted 2009-10-21 04:53:25 »

Having never done anything with A*, this may very well be a stupid suggestion, but here goes anyway. Smiley Can you get away with using IdentityHashMap? I'm seeing it about 30% faster than HashMap on gets. Obviously this doesn't solve your GC problems, but maybe you could modify JL235's class to use == or base a new one off IdentityHashMap.

I started a related thread with some benchmarks:
http://www.java-gaming.org/topics/map-performance/21395/view.html

Offline JL235

JGO Coder


Medals: 10



« Reply #12 - Posted 2009-10-21 06:46:59 »

Thanks JL235, that will be fantastic if i can use your CachingHashMap implementation. The Javolution FastMap requires me to use the whole 0.4MB package so your single file is much better. The only benefit that Javolution provides is that add() is constant time since the underlying array is never copied when the hashmap outgrows its capacity, but I have no use for that since my map is always re-used so it will always stay big.
If you can predict how big it will be, then you could set an initial capacity to avoid the resizing of the array.
Out of interest, what was your reason for making the CachingHashMap? Where did you need it?
For exactly this problem that your having. I use a hashmap in my collisions grid and found if I had only 1,000 enemies in there, all moving and testing for collisions, then the JVM would be spending about 5% of it's time running the GC in order to clean up the millions of objects passively created. Now it's only spending about 0.5%.

Bear in mind that this is released under a BSD license, and so it does need to be properly credited if you are going to be using it. Otherwise go right ahead and take it.

Offline jezek2
« Reply #13 - Posted 2009-10-21 07:16:49 »

There is also GNU Trove, it has faster hashmaps, supports primitive types and it doesn't need to allocate Entry objects when traversing the map by using methods such as forEachEntry.

I'd like to use the Javolution collections and text stuff in some of my projects. I wish the JAR wasn't 400+ kb! The classes aren't easily extracted either.

You can use ProGuard for eliminating unneeded classes in your whole application/libraries, also you can obfuscate them (which will shrink them by some amount too), but it can be set to not obfuscate if not wanted.
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #14 - Posted 2009-10-21 08:32:20 »

You can use ProGuard for eliminating unneeded classes in your whole application/libraries, also you can obfuscate them (which will shrink them by some amount too), but it can be set to not obfuscate if not wanted.
Looking at their source, the classes can't be easily extracted without bringing ~80% of all the classes along for the ride.

Offline CommanderKeith
« Reply #15 - Posted 2009-10-21 13:47:15 »

Having never done anything with A*, this may very well be a stupid suggestion, but here goes anyway. Smiley Can you get away with using IdentityHashMap? I'm seeing it about 30% faster than HashMap on gets. Obviously this doesn't solve your GC problems, but maybe you could modify JL235's class to use == or base a new one off IdentityHashMap.

I started a related thread with some benchmarks:
http://www.java-gaming.org/topics/map-performance/21395/view.html

Cool idea, I'll try that and report back. Thanks!

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.

rwatson462 (30 views)
2014-12-15 09:26:44

Mr.CodeIt (23 views)
2014-12-14 19:50:38

BurntPizza (50 views)
2014-12-09 22:41:13

BurntPizza (84 views)
2014-12-08 04:46:31

JscottyBieshaar (45 views)
2014-12-05 12:39:02

SHC (59 views)
2014-12-03 16:27:13

CopyableCougar4 (57 views)
2014-11-29 21:32:03

toopeicgaming1999 (123 views)
2014-11-26 15:22:04

toopeicgaming1999 (114 views)
2014-11-26 15:20:36

toopeicgaming1999 (32 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!