Multithreading - The Future of PA and Titans
@sorian is back working on server simulation performance with multithreading this month and we have a technical update to share on his work for the next update.
Two years ago I was given the opportunity to continue work on my baby, Planetary Annihilation, for the 99377 Performance Update. My primary focus was attempting to improve performance by multithreading parts of the simulation. My initial focus was on areas of the simulation where I thought it would be easiest to do things in parallel. The most natural separation was based around planets.
Since navigation and physics are typically the worst performance offenders, separating updates by planet seemed like a good plan. Their updates tend to only act on a single entity. Initial testing blew up spectacularly, as I expected it would. Fortunately, there were not many areas of contention between threads and a performance win was born.
So, now that I am back, you may be wondering what I am working on now. I’ll be continuing right where I left off! This time I am digging further into the sim to see where I can split large groups of tasks over threads to speed things up. Early this week I was focused on the physics update. I figured, since we should only be looking at two unique physics objects at the same time, it should be possible to thread this.
Well, I was right and wrong. There were the usual small issues to fix, but threading the physics update revealed a larger issue. The physics system utilizes an HGrid (described as a loose octree) to find potential entity overlaps using a function called buildPairs. It turns out that there is no guarantee that the vector of pairs that we get back does not contain duplicates. Under normal operation this isn’t a huge issue, as this is a single call that immediately returns and it was just being done thousands of times more than it needed to be. However, when you throw threading into the mix it gets ugly. Fixable, but ugly.
I have also started work on restructuring the sim tick a bit to allow the navigation and physics updates to happen alongside other updates. Right now I have it running alongside the economy update, but the economy update is only a small part of the overall update, so not much of a win there yet. I am hoping to split some of the plan steps (our sim has plan, execute, and record steps for entities) out into a group that can also run at the same time as the navigation/physics update.
For the navigation system, I have been mainly focusing on the epic number of allocations the navigation system does during voxel integration. I have a new system in place that saves off vectors of cost cells (the objects the integrator makes tens of thousands during voxel integration) for reuse. The integrator is also doing a better job of allocating in blocks instead of individually. On the multithreading front, the navigation system has proven to be quite difficult. There are so many little acceleration features and so much lazy loading that is simply prevents multithreading without a significant amount of work.
So, what’s next? There is still more work to be done with navigation, there is still the sim tick stuff to be investigated, and some AI updates as well (of course), starting with a much needed performance pass. And that doesn’t even get into other fun stuff like modern toolchain and Coherent GT updates.
Mike “Sorian” Robbins