Multithreading Systems by Leveraging Graph Theory
A common ambition in game development is to multithread parts of your game to take advantage of today’s multicore processors. The challenge is that in games, you can have hundreds of different systems that write to and read from data. How do we multithread these hundreds of systems while avoiding race conditions that occur when multiple threads write to and read from the same data? In the example below, we have 4 different systems which don’t seem too hard to multithread, but in real scenarios it will become unmanageable faster than you think.


To add even more complexity, there are usually rules for the order in which systems should be able to run. We use the following:
 Systems that write to data should run before systems that read from that same data. In our example,
PoisonSystem
should run beforeGameOverSystem
andHealthBarSystem
because it writes toHealth
, while the others read fromHealth
.  Systems that read from the same data can run in parallel. In our example
GameOverSystem
andHealthBarSystem
can run in parallel and the same goes forMovementSystem
because it doesn’t read any data the other systems write to.  We want to forbid two systems from writing to the same data because that would mean both would need to run before the other to avoid a race condition and that’s impossible.
Graph theory to the rescue
A graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”. The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge.^{1}
This sounds similar to our problem, doesn’t it? If we start thinking of the problem as a graph where our systems are the vertices and their data dependencies as edges it becomes easier to reason about. Below is what it would look like if we placed our systems in a graph.
To achieve this graph in code we just need to loop over every pair of systems and compare their read and writes. Which results in the following code:


Topological sorting
The careful reader should have noticed that the code does not follow one of our previously mentioned rules:
We want to forbid two systems from writing to the same data because that would mean both would need to run before the other to avoid a race condition and that’s impossible.
This is not great because this is a rule we have to follow to not get race conditions that would crash our entire application. For example if we added a new system called BulletSystem
that also writes to Health
it would result in a cycle where PoisonSystem
and BulletSystem
need to run before the other:
This is where we can leverage a technique called topological sorting:
A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering.^{2}
That solves our issue of not knowing in which order we should run our systems. Additionally, it solves the problem of potential cycles:
A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering.^{3}
Knowing that performing a topological sort will solve all of our problems, we will jump straight away into the implementation! We will implement Kahn’s algorithm^{4}, which is a simple breadthfirst search algorithm. It works by finding all vertices with no incoming edges, adding them to the sorted list, removing them from the graph and then updating the incoming edges of all its connected vertices. This is then repeated until all vertices have been ordered.


If we perform the topological sort on our previously mentioned list of systems we get the following order:


Multithreading the systems
With our list of systems sorted we now have everything we need to multithread the execution of our systems. The choice of library is up to you (you can even use System.Threading.Tasks.Task
if you’d like) but I’ll be using a custom implementation with a few worker threads. The code will differ depending on how you implement the multithreading but in my case it looks like this:


The code above outputs:


Exactly which thread is being used for which system isn’t important in this case, but the order is. MovementSystem
and PoisonSystem
are run in parallel while GameOverSystem
and HealthBarSystem
have to wait for PoisonSystem
to complete. After it’s complete they can both run in parallel on different threads. This means we have accomplished everything we set out to do! The implementation details of the custom job system might become a subject for a future blog post, but that will have to wait.
Thanks for reading!