Taming garbage collection to prevent stutter

Airships: Conquer the Skies
23 Apr 2014, 12:11 p.m.

Spurred on by this post, here is an in-depth post on memory management in Airships.

The game is written in Java, where unused data is automatically deleted in a process called garbage collection. This is nice, but comes with a big drawback: you can't control when garbage collection (GC) happens, and it can take too long.

The game runs at 60 frames per second, giving each frame a bit more than 16 milliseconds to advance the game state and redraw the screen. If GC kicks in during a frame and takes 30 milliseconds, the game stutters noticeably.

So this is something that needs fixing. There are two ways of going about this: reducing the amount of temporary memory allocated each frame, and tuning the garbage collector to make smaller but more frequent collections.

As with optimizing CPU performance, the most important thing when reducing memory allocation is to measure before you optimize! Conveniently, Netbeans, the IDE I use, has a memory profiler, which can measure memory allocation.

So to start, I started the game with the profiler and set up a combat.

Then I reset the collected profiling data so far, started the combat, played for a few seconds, and took a snapshot. The reason for the reset is that I'm interested only in what objects get allocated every frame during combat. Without the reset, this information would be swamped by memory allocation to do with loading assets.

Inspecting the snapshot, I could see three culprits - three classes that were being instantiated in their thousands for no good reason.

The worst offender was the Direction class. Direction objects encapsulate an angle and take care of trigonometry calculations and the modular arithmetic of angles (270 degrees + 270 degrees = 180 degrees). Unfortunately, it was being used in one of the most frequently used bits of the code: targeting.

Each gun on each ship considers each tile on each enemy ship as a potential place to shoot at. As a part of this, it checks whether the angle to the target tile is within its fire arc. This angle was represented as a Direction object, which meant that in a moderately sized fight, tens of thousands of Direction objects would be allocated.

This was an easy thing to fix: instead of a Direction object, I used a raw double value for the firing angle, normalising it with a convenience function. So instead of

Direction dir = Direction.fromTo(sx, sy, tX, tY);

the code now reads

double dir = Direction.radiansFromTo(sx, sy, tX, tY);

This makes a difference because raw values are allocated differently and don't need garbage collection: as soon as the function they're used in ends, they vanish automatically. Replacing Direction with double throws away some of the safety of the Direction class, but it's OK, because the value only stays around for the next three lines of code.

The second-worst problem was with Color objects. Turns out that Slick2D, the 2D engine the game runs on, creates a new Color object each time you set the draw colour, which is something that happens at least once per module and tile every frame!

So I dug into the guts of Slick2D and bypassed this problem by doing some raw OpenGL calls. It's not elegant, but that's optimisations for you.

The final big culprit were Arraylist iterators: In Java, if you do a loop like this:

for (Foo foo : foos) {
  // Some stuff.
}

this creates an Iterator object in the background! Unsurprisingly, there is a lot of looping in the game: loops over tiles, crew and modules, often nested, sometimes three deep. This created a lot of iterators.

The fix? First I used the "record stack trace for allocations" feature of the profiler to figure out where most of the iterators were being created. Then I rewrote those loops to old-style ones:

int foosSize = foos.size();
for (int i = 0; i < foosSize; i++) {
  Foo foo = foos.get(i);
  // Some stuff.
}

This is much more verbose, but does avoid creating an Iterator object.

Again, much as with CPU performance tuning, you can stick in an almost arbitrary amount of effort reducing memory allocation. Unless you contort your code in weird ways, some memory will get allocated each frame, and that's OK. After all, there's a second way to prevent stutter: garbage collector tuning.

Remember that GC is fine in and of itself, it's only a problem if it takes too long and holds up the game. So we can also try and make the GC do small but frequent collections. Conveniently, Java 7 now has a MaxGCPauseMillis virtual machine option. Using MaxGCPauseMillis=8 causes the garbage collector to try and keep GC cycles to 8 milliseconds or less. The setting is only a hint, so there's no guarantee it won't take longer from time to time, but with object allocation carefully limited, the game now runs a lot more smoothly!