Performance Optimization

Airships
2014-02-25 16:35

There are two major rules of optimization: first, only optimize when you have to. And second, measure before optimizing. If you try to be clever and write fast code before you know which code is actually causing performance issues, you are liable to spend a lot of time optimizing code that is not the bottleneck.

A few days ago, I got feedback from my testers that combat ran slowly with many ships. This wasn't surprising, as I had indeed not bothered trying to write fast code until then. The first thing I did was attach hprof, a Java profiler. This gave me a list of functions that took up the most time.

The worst offender, unsurprisingly, was collision checking between ships. This is done in two phases. First, the game checks if the bounding boxes of two ships overlap. This is a very fast way of checking if the ships are even anywhere near one another. If the bounding boxes do overlap, the game then checks if any of their tiles actually overlap.

Two ships with slightly overlapping bounding boxes.

Later on in the collision process, the game needs a full list of all the overlapping tiles, but at this stage a simple yes or no answer would suffice. However, it's easy to turn a list of overlapping tiles into that yes-no answer: just check if the list contains any items. In practice, each time there was a collision, the game would calculate the list of overlapping tiles twice: once to check that yes, there was a collision, then again to assign collision damage to those tiles.

Red tiles: checked, not overlapping with other ship. Green tiles: checked, overlapping.

The fix there was to create two variants of the same code: the first returns a complete list of all intersecting tiles, whereas the second, as soon as it finds an intersection, immediately returns true.

White tiles: not checked. Code stops after first overlap is found.

The worse problem was that in order to check whether two tiles overlapped, the code would create two new Rectangle objects each time. This caused hundreds or thousands of pointless memory allocations a second!

The fix there was even simpler: just switch to a simple function that calculates rectangle overlap straight from the tile coordinates.

These two fixes delivered a serious speed increase to the game, but there were still other issues. The second-worst offender was tile lookup: determining which tile was at a particular point in the grid, say third from the top and fifth from the left. This is a very common thing the game needs to look up and is used in all kinds of places. Unfortunately, the original, simple implementation would loop over the whole list of the ship's tiles to find the right one each time - asking each tile "are you at y = 2 and x = 4?"

Checking each tile in turn to find the one at the right co-ordinate.

To fix this, I added a 2D array of tiles that gets recreated on the fly when the ship gains or loses tiles. Now the game can find the right tile just by indexing into this array.

Indexing into a 2D array (grid) of tiles.

Finally, the third-worst offender: an obscure function called somewhatStaffed, used to figure out if a module has anyone working in it. To do this, it has to loop over the modules' staffing jobs, and for each of them, loop over the ship's entire crew.

The main problem there was that these loops were creating iterator objects - more memory allocation. Switching to a different method of looping fixed this as well.

At this point, the only bits of the code that took more that 1% of total game-time were graphics routines, which is kind of understandable. I could push this kind of game of optimize-the-worst-offender arbitrarily far, but gains beyond 1% are not really worth it unless you are desperate.

Anyway, for now, performance is much improved. As I add things to the game, performance issues may crop up again, but the important thing is to wait for them to crop up and then fix them, rather than trying to anticipate things and making the code needlessly complicated in advance.