Removing the garbage from Java
I have a small Android game I have been tinkering with for many years now. It works pretty well on modern phones but I have noticed that it’s performance on older phones has deteriorated over time. I have known this for a while but I chose to ignore it as I wanted to get the app published first. Actually my wife and quite possibly everyone I know and those articles on the internet said I should stop perfecting things and just get it out there.
So, yes I did actually manage to publish it. It’s called Draggled, and I’d love you to try it. Anyway, from profiling (or simply just by looking at the logs) I can see that the slowness is caused by the garbage collector having to run way too frequently. I see many of the following:
12–11 12:58:57.316 31126–31128/com.company.app D/dalvikvm: GC_CONCURRENT freed 1067K, 51% free 9832K/19975K, paused 1ms+2ms
Which also shows up to a lesser degree as garbage cans in the Android Studio memory profiler on my old low end no name phone. Unfortunately, for the really old phones the Android Studio profiler does not work at all which is a shame as they need all the help they can get.
Now for a game this kind of pause is pretty jarring so I decided to finally fix this issue. So how do you stop using the garbage collector? In short you have to stop allocating. This can be particularly difficult when
float[] T = new float[2];is so easy to use and in Java I don’t even have to free it :-). Yes this game is written in Java an odd choice I know but I kind of like a challenge. Besides the original version was written for J2ME phones if you remember those. However, all these allocations eventually result in garbage collection as all the references become unused.
Now in the game I have a physics engine that I crafted myself (see I told you I like challenges) I’ll have to write an article about that sometime. This engine uses my custom vector library ( are you starting to see a trend here) which relies heavily on using arrays as 2D vectors and hence all the allocations. I had originally thought that the jvm or java compiler would be smart with lots of small allocations and treat them more like a stack based allocation. This is what I believe happens on the latest phones (well sort of) but not on the older ones. Instead they seem to accumulate and eventually cause a garbage collection event. For example if you have the following
for (int ct = 0;ct < this.usedContacts;ct++) {
Physics.Contact contact = this.contactPool[ct];
if(contact.Vrel < 0.0f) {
float[] N = contact.normals[0];
int id0 = contact.ids[0];
float[] vel_0 = { vel_x[id0], vel_y[id0] };
float[] V = {m[id0]*vel_0[0]/dt + f_x[id0], m[id0]*vel_0[1]/dt + f_y[id0]};
float[] T = new float[2];
float dp = Vector.dot(V, N);
Vector.multiply(dp, N, T);
Vector.subtract(V, T, T);
float staticFriction = 0.025f;
f_x[id0] -= Math.max(Math.min(V[0], staticFriction), -staticFriction);
f_y[id0] -= Math.max(Math.min(V[1], staticFriction), -staticFriction);
}
}This is part of the code to calculate the static friction between colliding objects in the game (yeah it’s the actual code, and it’s pretty ugly). Notice that there are 3 allocations in this loop. Each of those allocations creates 2 floats which occupy 4 bytes. So for every collision you get 4x2x6 or 48 bytes per object. As you have probably guessed at this stage that can really add up, not to mention lots of really small allocations are generally not a great idea. This example is pretty typical of the mathematically oriented code in the game.
My original thought had been to start moving the allocations outside the loops thus reducing the number of allocations so you end up with something like
float[] V = new float[2];
float[] vel_0= new float[2];
float[] T = new float[2];for (int ct = 0;ct < this.usedContacts;ct++) {
Physics.Contact contact = this.contactPool[ct];
if(contact.Vrel < 0.0f) {
float[] N = contact.normals[0];
int id0 = contact.ids[0];
vel_0[0] = vel_x[id0];
vel_0[1] = vel_y[id0];
V[0] = m[id0]*vel_0[0]/dt + f_x[id0];
V[1] = m[id0]*vel_0[1]/dt + f_y[id0];
float dp = Vector.dot(V, N);
Vector.multiply(dp, N, T);
Vector.subtract(V, T, T);
float staticFriction = 0.025f;
f_x[id0] -= Math.max(Math.min(V[0], staticFriction), -staticFriction);
f_y[id0] -= Math.max(Math.min(V[1], staticFriction), -staticFriction);
}
}
This works ok (in this case anyway) but for more deeply nested code which may be inside another loop you can’t move the allocations. So another idea is needed.
Ever since I started writing this game in Java I have really missed the stack based allocation I had in C++(yes I do like low level coding). You could simply create a variable on the stack and use it without having the overhead of allocating something on the heap. This gave me the idea of modifying my vector class to hold the vectors as well so I could allocate them similar to the stack based allocations in C++ (just not as nicely). So I came up with the following
public class VectorStack {
final float[] stack; // Array to hold the stack variable
int top; // Current top of the stack
/**
* Creates the vector stack with n elements
* @param n Number of vectors to have on the stack
*/
public VectorStack(int n) {
this.stack = new float[2*n];
this.top = 0;
}/**
* Creates a new vector initialized to x and y
* @param x x value
* @param y y value
* @return Returns the id of the vector
*/
public int push(float x, float y) {
int id = this.top;
this.stack[top + 0] = x;
this.stack[top + 1] = y;
this.top += 2;
return id;
}... }
Now I can pop and push vectors onto the stack (not as nice as in C++ but it works). Also I only need 1 allocation which can be released at the end of the game. Each allocation returns a pointer like id which references the vector value. This results in a vector addition method as follows
/**
* Add one array to another
* @param src1 first array
* @param src2 second array
* @param res resulting array
*/
public void add(int src1, int src2, int res) {
this.stack[res + 0] = this.stack[src1 + 0] + this.stack[src2 + 0];
this.stack[res + 1] = this.stack[src1 + 1] + this.stack[src2 + 1];
}It just takes the 2 ids and uses them to look up the vector operands and puts the results in a 3rd vector using it’s id. All pretty simple really. Now I can easily convert my previous code with all the allocations into something that looks very similar.
int posStaticFriction = this.vectorStack.push(0.025f,0.025f);
int negStaticFriction = this.vectorStack.push(-0.025f,-0.025f);
int stackTop = this.vectorStack.save();
for (int ct = 0;ct < this.usedContacts;ct++) {
Physics.Contact contact = this.contactPool[ct];
if(contact.Vrel < 0.0f) {
int N = this.vectorStack.push(contact.normals[0]);
int id0 = contact.ids[0];
int V = this.vectorStack.push(vel_x[id0], vel_y[id0]);
int F = this.vectorStack.push(f_x[id0], f_y[id0]);
this.vectorStack.multiply(m[id0]/dt,V,V);
this.vectorStack.add(V,F,V);
int T = this.vectorStack.push();
float dp = this.vectorStack.dot(V, N);
this.vectorStack.multiply(dp, N, T);
this.vectorStack.subtract(V, T, T);
this.vectorStack.min(V,posStaticFriction, V);
this.vectorStack.max(V,negStaticFriction, V);
f_x[id0] -= this.vectorStack.get(V,0);
f_y[id0] -= this.vectorStack.get(V,1);
this.vectorStack.restore(stackTop);
}
}
this.vectorStack.clear();You may have noticed that I also added a few methods to make freeing all the variables very quick. Instead of using a pop for each push, I decided that I could save the top of the stack before I entered the loop using the save method (I could probably think of a better name here) and then restore it at the end to wipe them all out. This is similar to writing code in assembly (which coincidentally, I really like but it is an acquired taste).
This seems to work great I can now significantly reduce the allocations and as a result the garbage collections that occur in the game making performance more stable. However, debugging the code is a little harder as I have to use the ids to look up the actual values stored in the stack. I have found that I can use the watches in Android Studio to do this for me, so that very little effort is required.
All in all this was a fun experiment and I really liked getting back stack based allocations in Java. This means that I can add more physics to my game and expect reasonable performance even on low end phones, so more users will be happy (if they ever mange to find the game that is).
