Object Pooling and arrays

Performance Tuning
#1

I made a simple game for Android devices last month and learned first hand just how easy it is to use up the heap memory assigned to an app on Android and ended up with a functional game that calls the garbage collector far too often for my liking, resulting in annoying stutters about once per second.
To combat these memory issues I’ve been researching and implementing a generic object pool. It adds some abstract mess to my code, but its been super helpful in dealing with my memory niggles. I’ve run into a bit of an issue though and I’ve been failing to find information on this topic so I’d like to get some opinions here.

The object pools I’ve been coding have been working great for classes I’ve personally coded (Polygon, Vectors, game objects, etc.), but what about the memory allocations of external classes? Mainly I’m curious about how high performance Android games deal with the memory allocations of arrays and arraylists. If I create an arraylist of objects in a class that’s run on each loop of the core game loop, I can easily reuse the memory of the objects this arraylist holds by handling their creation through an object pool and then recycling them into the pool once each object is no longer in use, but this leaves me with the memory overhead of the empty arraylist which was never recycled. What can I do with this? Create a separate object pool for the arraylist object to be recycled each frame?
Similarly, what can I do about a situation where I need to create some arrays holding primitives (lets say a float[] array) very frequently. Is there some means of clearing the memory of these arrays, in maybe another object pool? Maybe I just need pools everywhere…

If the question is unclear, I apologize. It’s 3AM and I’m quite tired. :slight_smile:
I’ll check back tomorrow and can post sources of my current object pool implementation if the question seems unclear. I tried pooling arraylists but ended up creating my own memory leaks somehow, so I feel I’m not on the right track yet.

#2

I tackled this problem relatively successfully, my engine is finally allocation free. In the means of “allocation free at runtime”. This should be the goal.

First of all, abandon all third party components that allocate too much memory. Pretty much all of the standard library can be used more or less garbage free. An exception is iteration over a hashmap and such things for example. But that means you should avoid creating collections at runtime. Using pools is one appraoch to tackle this problem. But for example you can decide that your scene is “memory static” once loaded. For example you could load all game objects, put them in a fixed size list once and done. On scene loading, colleciton is thrown away and a new scene creates its own…which should be fine.

If you have requirements that prevents you from using this approach, we should discuss your case more particularly.

For your “per frame primitive collections” I would go for the same appraoch: Add a “cache” to your scene class (list, intlist, whatever) and have it the size you need for this scene. Don’t free it up ever. Throw it away when you want to change scene automatically, as it is created together with the scene.

Does that make sense? A multithreaded renderer appraoch has different needs though. Give us a hint if you have such an environment.

#3

Grrr to Android for still having a hopeless garbage collector.

Pooling is effective and works nicely but especially for large, complex, or expensive to construct objects - arrays and arraylists are good candidates. Use Arrays.fill to clear them out when they are needed.

Cas :slight_smile:

#4

Thanks guys. The advice alone already put me in the right direction.

I saw first hand the issue with using iterators to parse through hashmaps (or arrays via iterator style for loops) and I’ve had to change a bunch of looping logic to reduce memory usage.
To tackle the the pooling of arrays I extended my object pool class and implemented a pool that creates arrays of fixed sizes using the component type of the class passed into the pool as a generic.
I’m hoping to reach some sort of memory static scene when complete but my engine was never prepared for this overall structure so its slow progress. Learning as I go! :slight_smile:

Once I get the lower-level engine code Android-optimized it should be fairly straight forward to work on a static scene that loads objects once and reusing them within the world from thereon.

#5

Indeed it’s a problem on Android. I was very lucky to have tackled this area long before starting Android development in '08 on the desktop previously and refined things even further with my TyphonRT efforts especially after switching to a component architecture which is based on HashMaps. I created a custom collections implementation which recycles iterators automatically at the end of iteration in loops in addition to internal objects used in all the collections. Even better is that the component architecture allows easy recycling of components (objects!). So yeah you’ll get hit hard on Android using iterators and the standard collection API for anything near real time usage. Even worse was the piss poor annotation support as it lacked all caching and did a bunch of string comparisons (left over poor implementation from Harmony), so I have my own annotation cache for TyphonRT. I had a demo showing milliseconds for my cache and up to 10 seconds for the same amount of queries by the Android API in a tight loop. In addition I found early in ~'12 though never reported a serious flaw in Enums on Android. At that point I just gave up on reporting things as Google simply didn’t care about quality or performance to the degree that I thought it was important and worked around it as the workarounds work on any version of Android. Some details on the Enum bug here.

As you noted though that recycling variable length primitive arrays is troublesome in general. That is worked around for say in a component architecture you have a ParticleData component with primitive arrays for tracking X particles. You recycle this object / component and when you pull it off the pool you know the primitive arrays are the right length, etc. So recycling objects with explicit primitive array lengths is fine.

#6

Hmm I don’t really agree with you on the enum flaw… the implementation is valid. It sounds to me like you were rather just hoping to use hashCode() instead of equals() for identity comparisons and while it appeared to work on the desktop, it fell over on Android…

Cas :slight_smile:

#7

How is it valid? It differs from the JDK implementation which is the identity hashcode. It’s clearly a mistake in the Harmony implementation never corrected in Android. Even Romain Guy in the discussion went, “oh shit…” or thereabout… Go look at the JDK source and compare against Android. HashMaps will fail on Android if you have two separate enums with the same name at the same ordinal. QED.

#8

That implementation of hashCode() is indeed completely valid according to the well known “equals/hashCode contract”.
Read especially the first sentence of the third rule:

[quote]It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results.
[/quote]

#9

You guys are nitpicking. It’s an extremely poor implementation of hashCode valid or not… Which causes instant clashes with HashMap. You have to use IdentityHashMap when using enums as keys on Android.

JDK:
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/Enum.java?av=f#151

Harmony / same code as in Android for 8 years until switch to OpenJDK:

#10

@KaiHH Exactly. HashMap does not use hashCode() to determine key equality - it uses the hashCode() to bucket keys. After it has found the right bucket, it then scans a list of keys using equals() to find a match.

@Catharsis No, I think you’d be wrong there. HashMap works whether hashCode() is implemented that way or not provided hashCode() keeps the contract as specified, which it does for both implementations.

Cas :slight_smile:

#11

Unfortunately it’s not something I can confirm right away as it’s been a while since I’ve been doing Android dev and my larger TyphonRT projects (video engine) are stuck back at a gradle version well below the current setup I’m running. IE I don’t want to spend the ~3+ hours now to get things running to verify this point; updating gradle from an old version and a multi-module IDE project is no fun…

It was a bit more nuanced and problems only occurred when running a large project based on TyphonRT when using HashMap as the component storage versus IdentityHashMap. The problem occurred when mixing ‘Class / .class’ and enum types as keys in the same HashMap and not just various enums as keys. When i get back to Android dev after my Javascript adventures / server side stuff is complete later this year I’ll do the test and report back if I remember though this thread might be locked by then. If I recall though it was because Class and Enum have different hashCode implementations; I could be wrong. Pending verification…