• Create Account

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

18 replies to this topic

### #1IceBreaker23  Members

Posted 06 February 2012 - 08:15 AM

Hi everyone!

Is multithreading nessecary for real time 3d games, because I´ve always done it in the way to call update and paint in a loop without threading.

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

### #2irreversible  Members

Posted 06 February 2012 - 08:47 AM

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.

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.

### #3swiftcoder  Senior Moderators

Posted 06 February 2012 - 09:08 AM

POPULAR

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.

Tristam MacDonald - Software Engineer @ Amazon - [swiftcoding] [GitHub]

### #4MaxDZ8  Members

Posted 07 February 2012 - 02:14 AM

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?

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.

Previously "Krohm"

### #5carangil  Members

Posted 07 February 2012 - 06:06 PM

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

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)
-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.

### #6Hodgman  Moderators

Posted 07 February 2012 - 06:39 PM

@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.

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.

### #7InvalidPointer  Members

Posted 08 February 2012 - 12:26 AM

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?
clb: At the end of 2012, the positions of jupiter, saturn, mercury, and deimos are aligned so as to cause a denormalized flush-to-zero bug when computing earth's gravitational force, slinging it to the sun.

### #8Ashaman73  Members

Posted 08 February 2012 - 12:35 AM

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).

Ashaman

### #9Hodgman  Moderators

Posted 08 February 2012 - 01:01 AM

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, Sleep(0) is allowed to immediately return instead of sleeping for a tick (which is usually bad), if thread priorities allow for it.

### #10Ashaman73  Members

Posted 08 February 2012 - 08:22 AM

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) ?

Ashaman

### #11SimonForsman  Members

Posted 08 February 2012 - 08:30 AM

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) ?

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.

I don't suffer from insanity, I'm enjoying every minute of it.
The voices in my head may not be real, but they have some good ideas!

### #12Hodgman  Moderators

Posted 08 February 2012 - 04:40 PM

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 timeBeginPeriod/timeEndPeriod 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 timeGetDevCaps to find the system's minimum value, instead of using a hard-coded 1.
Also, despite the bad guarantees for how long a Sleep(1) 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).

### #13skytiger  Members

Posted 09 February 2012 - 07:48 AM

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

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.

### #14ill  Members

Posted 12 February 2012 - 12:09 PM

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.

### #15RobinsonUK  Members

Posted 12 February 2012 - 01:48 PM

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.

### #16ill  Members

Posted 12 February 2012 - 03:25 PM

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...

### #17InvalidPointer  Members

Posted 12 February 2012 - 09:35 PM

POPULAR

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
clb: At the end of 2012, the positions of jupiter, saturn, mercury, and deimos are aligned so as to cause a denormalized flush-to-zero bug when computing earth's gravitational force, slinging it to the sun.

### #18RobinsonUK  Members

Posted 13 February 2012 - 06:58 AM

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.

### #19InvalidPointer  Members

Posted 13 February 2012 - 11:47 AM

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.