carryingSuccess

Desktop Tuesday: Performance Improvements

Hey Everyone, Stephanie here. Tom is out of the office today, but rest assured that the whole team is working hard to get Alpha 11 into your hands as soon as possible.

For those of you who have been following along, you’ve probably noticed that A11 is shaping up to be a bit of a bear. Our original goal for this release was to add some features that we as a team have been looking forward to writing for some time. Feedback from all of you, however, especially in the wake of our Steam Early Access release, gave us concrete examples of the many ways in which the game fell short of the stability, performance, and scalability goals we had for it. Armed with your crash reports, save files, error screenshots and hardware configurations, we made a list of improvements we hoped would make the game run smoothly on as many of your machines as possible. We stuffed all the self-contained fixes into A10.5 updates, and pushed all the big, risky, game-changing ones into A11. Here are the top three, in ascending order of complexity:

Performance Improvements: Score Service

Many of you wrote to tell us that after 20+ days of in-game play, Stonehearth would start to stutter every few seconds, making progress impossible. When we loaded up the giant save files you sent us, Chris (and Tony) realized that the stutter happened whenever the game was trying to compute your score (net worth, happiness, food, etc.).

The inventory system in A10 and earlier did not account for buildings, placed furniture, and most of the stuff on the ground. In order to get a sum total of everything that might contribute to your score, we periodically iterated through everything you could see, checked if it “belonged to you” and if so, calculated how much it was worth. Since the score for some of these items depended on other items, this meant touching every item not just once, but as many times as there were items that were dependent on it. We would do this every 10 in-game minutes, which is about every 30 seconds at 1x speed, and faster at faster speeds. (For any of you who are or will be Stonehearth modders, note for posterity: touching every single item in the game, and some number of their dependent items, is incredibly slow and inefficient. In programmer-speak, this is an operation of n-squared, where n is the number of objects in the game. In non-programmer speak, if you have 100 in-game items, and they all depend on each other, you’d be touching 100×100 items, or 10,000 items, every 30 seconds. End-game saves have significantly more items than 100 items, so… learn from our oversights!  Don’t do this.)

To fix the stutter, Tony re-wrote the score service such that every object in the world instead tells the score service about itself when it enters or leaves the player’s possession. This means that if you have 100 items, each of them updates the score service once or maybe twice, in its entire existence. Instead of 2,000 updates a minute, we’re down to 100-200 updates over the lifetime of those objects. Woo!

Side effects and implications: Writing code is always about tradeoffs. Speed, as above, often comes at the expense of simplicity. Systems that are easy to read and maintain are often not systems that run really fast. The original mechanism for score allowed us to write all the ways in which we wanted an item to contribute to score in one place. This was really simple to write/understand/debug, but extremely expensive to compute, since we had no way of knowing which functions applied to which items, and so had to call functions on all items we could see. In the new way, a developer of a service needs to find all the ways in the world that their contribution to score can change, and tell the score service the new value of the score whenever it does so. It is really fast at runtime, but may be more difficult for things which have changing score requirements (for example, the value of a building changes as hearthlings build more of it).

The new score service is definitely an improvement over the old one! But it means that everyone has to be diligent about potential score bugs whenever they’re changing any system that contributes to score.

Other side effects: Score currently determines citizen immigration. The new score service uses slightly different equations to calculate the net worth of things. As a result, we will continue to tweak the net worth requirements for immigration, as well as the gold values for different crafted objects. (Many thanks to Yang for finding and fixing a ton of bugs in this area: both gameplay, correctness and otherwise.) Expect some gameplay bumpiness, and let us know how immigration is working out for you as you playtest A11 with us.

Rendering and the CPU Cache

Chris is really your man for describing this major improvement, but the short version of this story is that in addition to score-related stuttering in large games, Chris also discovered a huge inefficiency with how we were reading in and rendering items in game. To render an item, the Stonehearth program loads information about that item from where it is stored in memory. The hard drive is the slowest kind of memory, RAM is faster, and a computer’s CPU is actually equipped with a series of caches (L1, L2, L3) that can act as even-faster memory as well. When the CPU sees that we’re reading in data, it automatically stuffs that data, and all the data near it, into its caches, under the assumption that data tends to be stored in a contiguous manner, and that stuff that’s near the thing you just asked for will probably be relevant in the near future. (In the real world, this is why library books tend to be categorized by topic, in addition to author’s last name; if you’re studying The Mongols, and you find one book about them, you want to be able to look on the shelf nearby and see other books that might be useful.)

Chris noticed that when Stonehearth was rendering, it was effectively reading from random locations in memory, obliterating the CPU cache every time we wanted to render an object. As with the score service, this was fine on fast machines and in the early game, but on older machines, and in the late game, the lag became quite noticeable. To fix, Chris has reorganized our data into “nice contiguous chunks” making us very effective at taking advantage of the CPU cache.

You should notice this as a significant improvement in FPS and performance in the late game.

AI Efficiency and Backpacks

What could be more complicated than a brand new service and memory organization improvements? Why, improving the efficiency of our AI, of course! One last thing we noticed about really large save games is that your workers spend a significant amount of time hauling stuff from one end of town to another. To fix this, some of you have started to use the loot command on stuff you already own, since that forces hearthlings to put things into their backpacks so they can carry multiple things at once. Tom thought it might be nice if we could make this the default behavior for restocking tasks, so that everyone could be automatically more efficient.

Because our AI system is very powerful and very fast (see my comment about speed/simplicity above) this of course, was about ten times more challenging than we expected it to be. All of our actions are written independently from one another; having people suddenly stashing things instead of hauling them created a rash of issues: suddenly hearthlings were standing still, or never restocking, or generally getting stuck. Restocking is lower priority than other tasks, but the pathfinder for picking up items near oneself finishes faster than the pathfinders for most other tasks, so people put stuff (like tools and weapons and food) into their backpacks, and don’t know how to take those things out again, for promoting/eating purposes. Moving “restock” to be higher in the priority queue led to people picking up food to eat, restocking it immediately, and starving to death. Furthermore, the backpack is a storage item, and attempting to account for its contents in the inventory, while making the planned inventory changes meant for A12, led to new and cool bugs in the placement UI, the store, and the crafters (who will also be changing a lot, very soon). The whole team has been banging on this fallout for a few days now; expect improvements soon and mild turbulence in the interim.

I presume you read this blog on Tuesdays because you are curious about what it’s like to build a game. Well, I guess today’s story is that sometimes game dev (as in all worthwhile things) is two steps forward, one step back. But though the game is a bit buggy at the moment, we are definitely committed to making it run better and faster for everyone. None of us would rather be doing anything else, and we’re very lucky to know that you’re along for the ride with us.

(As an aside, improvements like the ones detailed here would be basically impossible without all of you getting on the Early Access train with us. We six engineers have a very limited set of hardware/software/playtest environments. Every time one of you shows us a bug we’ve never seen before, and every time you send us a complex save/error/log, you directly help us make the game better for everyone else. Many, many, many thanks.)