A first-hand lesson in software optimization

The player is a striped bass, one of the arch predators in the bay.

The player is a striped bass, one of the arch predators in the bay.

One of my major computer science projects in college was creating an educational videogame for elementary school children called A Day in the Bay. We had eight people on the team, though only three of us (myself included) were programmers. It was a self-directed project, and we pretty much figured out things on our own as we went along. I’m not kidding about that last part — check out the CVS revisions for all the gory details. We not-so-seamlessly morphed our custom game engine through a couple completely different game types as our project evolved, and by the time we completed the final project, the overall structure of the code was rather incompatible with how it was being used.

But despite all of the problems, the most important programming lesson I learned from all of college came out of A Day in the Bay. That lesson was how to seriously optimize software, and it would’ve been entirely impossible to learn in the classroom, or even in a month-long programming project.

When we started writing our game, we were very laid back about it. We developers had gaming-caliber computers, and we only cut back on features when the game started lagging for us. So you can imagine our shock when we first tried testing the game on the many-year-old computers in a local elementary school’s computer lab. Oh, and our game was written in Java. Beginning to see some problems now?

The game was completely unplayable. We’re talking frame rates in the low single digits. We had to heavily optimize the game for performance in a short period of time. We did so by cutting out most of the game’s simulationist features. Our game, as originally envisioned, simulated an entire cross-section of the Chesapeake Bay, including plants, small fish, the larger fish eating them, etc. We had to keep track of thousands of fish and have all of them take actions in real time. We even had a state diagram for each fish which determined if it was running for its life, hunting for food, or just chilling out. Needless to say, it wasn’t working on the school system’s hardware.

So our first optimization was to establish a virtual boundary that was roughly one-and-a-half screen lengths in diameter around the viewable area. No processing time was spent on any of the creatures outside that rectangle. They were frozen, and only simulated when the player swam near them. This optimization wasn’t enough, though — we still had to keep track of thousands of in-game objects, which was overflowing the memory available to us on the classroom computers.

So we cut deeper. We inserted code into our main game loop to delete every object outside of that imaginary bounding rectangle. As the player swam his fish around in the game, the fish that were left behind were wiped out of existence, while a spawning routine created new fish (of the appropriate mix of predators and prey) in the “barren” area that the player was swimming into. At this point we had almost completely given up on the simulationist nature of our game. But the performance still wasn’t good enough.

So we cut deeper still. We further reduced the number of objects that could exist at any one moment to around a couple dozen and made the virtual bounding rectangle tighter still. We unloaded the menu and food web graphics from memory when they weren’t being displayed. We had finally gotten the game running at an acceptable frame rate and in the memory footprint of the classroom computers. We had cut out so much, but the most startling thing was that it played exactly the same. You couldn’t tell the difference between the accurate simulation of all fish in the cross-section of the bay and the outright fake in which fish existed only as long as they remained on-screen. Our original take on the concept was simply overkill.

My experience mimicked that of a developer of the Lord of the Rings console games for PlayStation 2 and XBOX. He gave a talk at our college that focused specifically on all of the programming techniques that were used in the games industry. He spent awhile educating us on the performance optimizations that were necessary to get the game running on the targeted hardware. It all boiled down to “if you don’t see it on the screen, it doesn’t exist”. Run past a group of orcs to escape them? They’re unloaded from memory, only to pop back into existence if you return to the area. The solution was exactly the same as the one we used in our game. Less kludgy, sure. But fundamentally the same. It was good to have our implementation of optimization validated in this way by someone who was a professional in the field.

So my advice to anyone wanting to learn software optimization is this. Write a program of at least medium complexity that runs at a merely acceptable performance level on your computer. Then try to get it running acceptably on lower-end hardware several years old. The techniques you’ll have to develop to get it working correctly will teach you more about software optimization than any class ever could.

5 Responses to “A first-hand lesson in software optimization”

  1. Gregory Maxwell Says:

    This blogpost is useless without pictures.

  2. Cyde Weys Says:

    There’s a picture. You can see how few fish are in the frame — not many more than that are in memory.

  3. MrDolomite Says:

    Very good post. Goes back to what I was taught long ago by my Arthur Andersen-trained boss, “Write it where you are going to run it.”

  4. Ed Says:

    Interesting, I was just reading an article from Guy Kewney in Personal Computer World where among other things he says the following: “The past 20 years have seen the collapse of clever programming” … “For 2 decades we’ve been able to solve programming problems by doubling memory capacity, or clock speed. Now we are running out of that sort of steam” …” More and more of the time we’ll want something small, specialised, cheap, drawing liitle power and doing something specific.” I’ll just add, will the rise of the nano notebooks (like the eee) see the return of specialised and clever programming?

  5. T2A` Says:

    There’s plenty of “clever” programming to be done still — getting programs to play well on any number of cores the target CPU may have is a challenge. Games today have to deal with this already, and the programmers have to figure out how to get their shit to run on one core while also being able to run it with an expected performance boost on four.

    Or so I’ve heard. You wouldn’t catch me anywhere near that kind of thing. I’m way too dumb for that.