Multithreading for Games

At the very minimum, multithreading is essential for fast resource loading as otherwise you'll be stuck with linear processing, which has no chance of utilizing the already slow disk access speeds at full capacity. Once you get to the territory where your scenes require massive per-task processing (physics, multiple occlusion queries, complex sound processing, etc), multithreading becomes the only viable option to maintain a solid framerate at high quality. Generally speaking, the number of threads you have should be equal to the number of processors that are available, each one should be able to process any job (except for certain limitations, eg the draw pipeline being bound to a specific thread whom the context belongs to), your architecture should be conceptually parallel (state/job-based tasks where each task can be processed by any thread). This isn't that difficult to do actually - all you need is a boolean (job ready yet?) response system (no mutexes, critical sections etc.!) backed up by a main loop for job distribution.

As I noted above, fundamentally, for simpler games, if you have any respectable amount of disk access, you, at the very minimum, should have a disk access thread that processes all disk-read jobs and queues completed read jobs for another thread for parallel processing while it processes the next disk read task.

A flag-based response system is based on the concept that any one thread AND ONLY THAT THREAD that is responsible for processing a task within the scope of a particular job can write into the memory space allocated for that particular task (parallel reads can still occur). Once the update completes, the thread sets the completion flag for the task. In the meantime, the main thread keeps polling all pending tasks for completion (by reading a boolean flag) and passes the task on to the next processing phase when the previous one completes. Consider three linearly dependent jobs that are distinct, but cannot be executed out of order:

TASK
job1: read file from disk (thread1)
job2: create alpha channel or whatever (thread2)
job3: copy texture to GPU (draw thread)

All of these steps can be parallelized for multiple load operations. The real benefit kicks in once you realize that job1 can do much faster reads since all reads are more likely to be sequential (other applications less likely to interrupt disk heads) and you're effectively making use of HDD access (which is the slowest link in the sequence) 90+% of the time, effectively winning the time spend on job2 and job3.

Any further parallelization really depends on your game and the complexity you need. Overall I think a task-based system is a simple and elegant solution that will scale automatically the more cores/threads the system has while still having the ability to fall back to a single core/thread if only one is available.

So my question: Do I need to/should use multithreading or is it better without it?

Have you run into a performance wall with single-core, where you simply can't make your game run at interactive frame-rates?

If so, then you need to multi-thread your game. If not, then it might be fun as an academic exercise, but it's far from essential.

Correct multi-threading is hard, it's easy to introduce difficult-to-track-down bugs unintentionally, etc. so don't do it unless you feel there is a distinct benefit to be had.

As I noted above, fundamentally, for simpler games, if you have any respectable amount of disk access, you, at the very minimum, should have a disk access thread that processes all disk-read jobs and queues completed read jobs for another thread for parallel processing while it processes the next disk read task.

I'd say "for simpler games" there's no need for multithreading at all. Unless perhaps on Atoms, but even those are going to run "simpler games" at interactive rates, albeit with some sweat.

Have you run into a performance wall with single-core, where you simply can't make your game run at interactive frame-rates?

If so, then you need to multi-thread your game.

Seconded. Given today's processors, I hardly believe a beginner can saturate them. Of course one can always do things wrong in the first place.

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

Generally speaking, the number of threads you have should be equal to the number of processors that are available[/quote]

[/font]

Actually you may want more threads than cores. Consider a single-core cpu. It can still benefit from having multiple threads, especially if each thread is likely to block on something. If you have a single core, and 4 threads:

- game logic & render thread : constantly runs, 'interrupted' by occasional work in the other threads
- sound thread : will periodically do a 'spurt' of work processing audio every so often. most of the time it's waiting
- network thread : will spend most of its time blocked, waiting on a socket
- file thread: will spend most of its time either waiting for the game to ask to load something, or blocked on a slow disk operation

On a modern OS, when a thread is blocked on something, such as waiting for the disk to read something, the kernel will set that thread aside, and run something in the another thread. The above design already benefits a little bit from having a multi-core processor, but isn't ideal. Since most of the work is still happening in the game logic/render thread, it could be further broken out like this:

-Render thread (just 1. OGL doesn't like threads, DX might not either)
-file thread (just 1; don't thrash the disk)
-network thread (1 per socket, but the client will probably only have 1 socket open anyway)
-sound thread (just 1)
-game logic thread (1 or many)

There is a bit of a difference now. Before the game logic & render thread alternated between advancing the game state, and rendering. You could just lock the game state, and take turns processing the next gamestate and rendering. At a first glance, it doesn't need any better than just having them share a thread, except with multiple cores, you could alternate between having 4 cores process 4 game state threads, and then have 1 core render, 4 cores process game state, and 1 core render, etc. This starts to reap the benefits of having multi core; but now what are the other cores doing while you are rendering? Probably not much. This is the point where you have to do one of two things: 1) break the game state into pieces, so you can start rendering one part of the gamestate while you begin to compute the next part or 2) double-buffer the gamestate (or at least just the parts that affect rendering), so that you can have 3 cores processing the NEXT game state while you have the 4th core render the PREVIOUS gamestate.

But, given the scope of most hobby projects, just breaking out super-slow things (like disk access), and the most bottlenecked calculations (physics etc) into seperate threads will give you the most benefit with the least effort (and bugs), which is more important than trying to achieve 100% cpu temperature.

@OP - if you're just a hobbyist learning how to make 3D games, I would not recommend trying to make a multi-threaded one first. It adds a lot more things to learn, and probably isn't necessary unless you really, really need 100% CPU utilisation from a quad-core...

Actually you may want more threads than cores. Consider a single-core cpu. It can still benefit from having multiple threads, especially if each thread is likely to block on something. If you have a single core, and 4 threads:
- game logic & render thread : constantly runs, 'interrupted' by occasional work in the other threads
- sound thread : will periodically do a 'spurt' of work processing audio every so often. most of the time it's waiting
- network thread : will spend most of its time blocked, waiting on a socket
- file thread: will spend most of its time either waiting for the game to ask to load something, or blocked on a slow disk operation

Generally speaking, your threads should not be likely to block on things. You should use non-blocking file-system and networking APIs, which removes the need for them to have their own threads (at a low level, these things are implemented asynchronously, using efficient methods such as DMA etc. The blocking APIs are a wrapper around things that are natively asynchronous, so if you then wrap up the blocking APIs with threads to make them asynchronous again, you've succeeded in adding two redundant layers of inefficiency to an operation that cancel each other out for zero benefit).
Also you usually don't create your sound thread yourself; it's usually created internally by your sound library and controlled via a non-blocking API.
So this just leaves the need for you to create your logic/rendering threads, which should simply just be your "one-thread-per-core general job/task processing" threads, which can run any logic/rendering/etc job (with rendering-submission jobs restricted to a specific thread if required).

On a modern OS, when a thread is blocked on something, such as waiting for the disk to read something, the kernel will set that thread aside, and run something in the another thread.[/quote]On windows, it also (by default) wont wake that blocked thread up for at least 15ms, even if it only needs to block for 0.5ms, which isn't very good for a real-time system, hence you should avoid blocking.

At the very minimum, multithreading is essential for fast resource loading...you have any respectable amount of disk access, you, at the very minimum, should have a disk access thread that processes all disk-read jobs and queues completed read jobs for another thread

As above, just use the OS's native asynchronous file APIs. You only need a background loading thread if you've got long-running post-load CPU work to do, such as LZMA decompression or XML parsing.

On windows, it also (by default) wont wake that blocked thread up for at least 15ms, even if it only needs to block for 0.5ms, which isn't very good for a real-time system, hence you should avoid blocking.

This is really more for my sake than anything, but I was under the impression that this tidbit only held for explicit calls to Sleep(), and things like WaitForSingleObject() and friends can potentially be more responsive?

Beside everything which has been said, there're two things I want to add.
1. Even with a single core CPU you already use a multicore system, that is CPU + GPU. You can utilize this by filling up the command queue of the GPU and then do some other tasks on the CPU. Until you don't use up this buffer (GPU is running, while CPU is idling) you don't need any multicore support (beside resource processing/loading).

2. When you want to add multicore support, you should start with it first. It is incredible hard to add multicore support later, some design decisions can easily steal the show (after writing 1000s of lines of gamelogic code in a scripting language like lua, it is somewhat demotivating to see, that lua doesn't support multicores in a single VM).

This is really more for my sake than anything, but I was under the impression that this tidbit only held for explicit calls to Sleep(), and things like WaitForSingleObject() and friends can potentially be more responsive?

It doesn't matter how you transition a thread into a sleep state - once in that state, the kernel's scheduler won't come around and poke it back into a ready state until the next scheduling cycle, which defaultsto15ms on windows IIRC.
I actually should've said "up to 15ms", because if you go to sleep right before the next tick, you'll get woken up quickly (i.e. somewhere between 0ms to 15ms). However, if there's too many threads, a ready thread might not be chosen to execute in any given 15ms tick, other threads can cause starvation. After a thread has starved for 3-5 seconds, the kernel will give it a priority boost to ensure it gets to run for at least one tick. So any time you block (with default settings), you're sleeping for a best case of 0-15ms, and a worst case of ~4 seconds.

On a side note, [font=courier new,courier,monospace]Sleep(0)[/font] is allowed to immediately return instead of sleeping for a tick (which is usually bad), if thread priorities allow for it.

It doesn't matter how you transition a thread into a sleep state - once in that state, the kernel's scheduler won't come around and poke it back into a ready state until the next scheduling cycle, which defaultsto15ms on windows IIRC.

Hmmm.. I use Sleep(1) in my multicore support code, after reading more about this topic it seems, that you can utilize the timeBeginnPeriod/timeEndPeriod to increase the timer resolution. As far as I understand, this will affect the whole OS (OS will take the highest resolution). Therefore I would try to encapsulate the sleep like this:

timeBeginPeriod(1);
Sleep(1);
timeEndPeriod(1);

Is this a bad idea (too much overhead, slowing down the OS) ?

[quote name='Hodgman' timestamp='1328684518' post='4910803']
It doesn't matter how you transition a thread into a sleep state - once in that state, the kernel's scheduler won't come around and poke it back into a ready state until the next scheduling cycle, which defaultsto15ms on windows IIRC.

Hmmm.. I use Sleep(1) in my multicore support code, after reading more about this topic it seems, that you can utilize the timeBeginnPeriod/timeEndPeriod to increase the timer resolution. As far as I understand, this will affect the whole OS (OS will take the highest resolution). Therefore I would try to encapsulate the sleep like this:

timeBeginPeriod(1);
Sleep(1);
timeEndPeriod(1);

Is this a bad idea (too much overhead, slowing down the OS) ?
[/quote]

Even if you change the timer resolution you still won't have any guarantees that a thread will wake up on time, (If you also boost the thread priority so it is higher priority than everything else on the system then it most likely will wake up on time though), only call timeBeginPeriod once early in the application:

(from msdn.microsoft.com)
Use caution when calling timeBeginPeriod, as frequent calls can significantly affect the system clock, system power usage, and the scheduler. If you call timeBeginPeriod, call it one time early in the application and be sure to call the timeEndPeriod function at the very end of the application.[/quote]

timeBeginPeriod(1);
Sleep(1);
timeEndPeriod(1);
Is this a bad idea (too much overhead, slowing down the OS) ?

In my experience, it seems to be fairly common practice to call [font=courier new,courier,monospace]timeBeginPeriod[/font]/[font=courier new,courier,monospace]timeEndPeriod[/font] in your main function (i.e. applying the increased scheduling precision for the entire life of your program). N.B. you're also supposed to use [font=courier new,courier,monospace]timeGetDevCaps[/font] to find the system's minimum value, instead of using a hard-coded [font=courier new,courier,monospace]1[/font].
Also, despite the bad guarantees for how long a [font=courier new,courier,monospace]Sleep(1)[/font] will last on Windows, there aren't many other good options if you have to put a thread to sleep -- e.g. if you've got two threads sharing one core, you'll have to sleep them at some point (especially if their priorities are different - in which case one could be starved until it get's it's priority boost after 3-5 seconds of starvation).

There is a simple two-threaded approach that gives a large performance gain for very little work.

Use 1 thread for Drawing and 1 thread for Updating.

Because Update() can never communicate with the DirectX Device
you need two intermediate buffers per component (I call it DrawState)

var drawState = new DrawState[2];

Then you only need to synchronize the switch between blocks ... I use a array index:

lock { updateIndex = 0; drawIndex = 1; }
or
lock { updateIndex = 1; drawIndex = 0; }

and each Component accesses its DrawState like so:

Draw() { drawState = state[drawIndex]; }
Update() { drawState = state[updateIndex]; }

Once you have implemented this it can be trivial to add more threads to the Update() side

To summarise:
Update() only writes to one DrawState object
Draw() only reads from the other DrawState object
Every frame you switch / flip / toggle between the DrawState objects

I don't see the point in writing some games as single threaded and some as multithreaded when you can use this technique for all games.

Here's a really good article that answered a lot of questions for me. Also I really suggest you use Intel Thread Building Blocks since they implement a lot of stuff you need like a task manager and lockless data structures.

Designing the framework of a parallel game engine

I'm still working on my engine but my idea so far is to have separate threads for the game logic and the rendering and audio. Then each thread spawns tasks each update. The rendering happens completely asynchronously from the game. I've never really been strong on the whole Model View Controller idea especially in games, but I ended up going with that kind of model naturally without even trying. The game thread has a controller that updates the entities, which are like the model. Then the renderer is like the view and has scene nodes that get updated by the controller.

Also PhysX 3 uses this kind of task based system which fits naturally into the multithreaded task processing architecture I'm going for.

I've been thinking about this a lot recently after watching the GDC presentation by the guys who wrote Civ V. As many have pointed out above, task based systems are best because they are more scalable. I can kind-of understand how you'd do it for a game like Civ, which seems to me to be very well tailored from a processing point of view to multi-threading. But when it comes to processing more complex structures, like the entities in an Octree, I keep finding blocks where the code will end up becoming serialised regardless of threading. That is you break the tree up into little processing blocks and dispatch them to various threads, but at some point you have to complete the circle and update the structure to a newer version. As soon as you start locking various data structures in order to apply updates, you're losing the benefits of threading. Worse, you can find yourself losing cache coherence and make performance worse rather than better.

As far as Civ was concerned, the moral of the story is to profile the application and various ways of doing things. I'm not sure you can write scalability like that in a generic way. Rather, it has to be done on a case-by-case basis, perhaps with constructs like `parallel for' and so on.

You basically have all entities in the game update as separate tasks each game loop cycle. There should be no locking at all since they are all independent of each other. They tell a central object about their updates, which has a lockless queue on it to prevent too much slowdown on a shared resource.

When all entities have updated at the end of the game loop, the central object notifies all entities that care about those entities about the changes. It also updates the visual side representation of the objects saying this object is now at this position and so on...

But when it comes to processing more complex structures, like the entities in an Octree, I keep finding blocks where the code will end up becoming serialised regardless of threading

You're Doing It Wrong™

Instead of shoehorning parallelism into an already explicitly serial design (trees and linked lists in general are inherently serial data structures; there's no effective way to traverse them in parallel without the threads stepping on each other's toes. Before you ask, skip lists are cheating/hacky) ask yourself if there are any alternative approaches that would instead scale well in a more threaded environment. As DICE found out when building their visibility system for Battlefield 3, the 'dumb' approach can certainly end up a lot faster than clinging to a conventional 'smart' solution simply because that's the way it's been done previously. Data is, ultimately, king

I don't see a problem with traversing a tree in parallel. Updating it with new state is the issue of course. With "lock step" threading I can see how it would work. Jobs run, store their results, all results are applied to the tree at the end. I'd be sceptical about the resulting performance improvements of course. Anyway will check out the BF presentation later.

I don't see a problem with traversing a tree in parallel. Updating it with new state is the issue of course. With "lock step" threading I can see how it would work. Jobs run, store their results, all results are applied to the tree at the end. I'd be sceptical about the resulting performance improvements of course. Anyway will check out the BF presentation later.

On the surface, yes, you're bang on the money. You can certainly have multiple threads be traversing the 'physical' tree in memory without incident. Actually doing work on it, however, is a bit murky. Consider the case of arrays for a moment. You can do a blanket segregation at the beginning, maybe partitioning the whole thing out into n chunks (where n is defined as being at or around the number of physical processor cores on the target machine for simplicity's sake) and then have all your threads go in guns blazing. If your computations are otherwise embarrassingly parallel or you're doing some super scheduling cleverness, you can actually get away with no additional synchronization; threads can just do computation without ever needing to interact with one another. You can actually handle array modifications in a similar way by trying to provide some upper bound on work that each thread would do, segregating output slots ahead of time, then having all threads write their (potentially variable-width) output within that set of bounds. You can then coalesce everything in later (possibly also parallel) passes over that data-- this is actually a fairly common approach (though not often directly seen) used in graphics and it actually has a name: stream compaction. There's quite a bit of research dedicated to doing this effectively and I'd suggest some Google-fu if it sounds interesting, as it's a very broad topic mostly outside the scope of discussion.

So, bringing that massive (bi)tangent back to heel, we're back with the idea of work distribution for arrays vs. trees. This is actually somewhat more subtle, but the speed advantage of trees for searching comes directly from their hierarchical skipping of regions based on previous sorting. Since we're in a hierarchy, we don't actually know what region(s) we need to search next until we run the current set of computations; this really, really kills the parallelism factor since it introduces hard synchronization points, and frequently. You can task multiple queries through the structure and see some speedup there, but it's still the same sort of 'bolted-on' concurrency dead end as things like a 'physics/render thread.' It helps in edge cases, but it's very likely those edge cases won't be a limiting factor or even present at all for most of your processing time. As an example, parallel view queries won't help you if you only have one camera, but parallel queries in of themselves will benefit one camera or 10,000 equally.