Optimization wonderland extravaganza

Nice, so in short this means less laggy games when a couple of people ore AI spams an armie.
I like it cant wait for the next update i hope the performence is in it

always interested in the nitty gritty details.

Really great read. Thanks for taking the time!

Looking at the second chart of the current parallel-ization, it looks like the majority of the animation updates is done 4-5ms before the render begins. You say that all of the rendering depends on all of the update, but is that strictly true? Would it be possible to begin rendering some of the completely-updated entities/collections before the update-cycle is complete?


Alternatively, what about starting the next update cycle in a thread halfway through the rendering? If the rendering depends on the previous update, would starting the update cycle earlier (perhaps even halfway through the previous frame) help cut huge amounts of time off the entire loop?

This is one of the things that has always made me wonder. If it will ever be possible for either games to be written in a way that they will use what cores is available without all the fuss, or even better that CPU's like say GPU's will just split the work into however many cores or threads as the system has.

Its probably because i dont have a clue about this. But it just seems odd why there isnt in general i mean, being put more effort into making it easier for game developers to use multi cores. I mean at some point in the future, i would imagine CPU would have 10-20-30-40 cores. and it sounds like its already a damn nightmare making games run on 4 cores.

I suppose this topic is about client-side performance improvements and it's can't simulation faster, but might be I'm wrong?

This is really one of the biggest problems in software engineering right now. It is probably not possible to get a compiler to efficiently split a single-threaded program into a multi-threaded one without any bugs. This sort of program really needs to be written by an experienced programmer or it just won't work.

In addition to that, there is also another problem. Think of each thread as an assembly line in a factory. You can build a car faster by having one assembly line for the frame and another for the engine, but eventually you need to merge the lines together and actually put the engine in your car. In this scenario, you can keep splitting off more tasks into their own assembly line only down to a certain level. Eventually it gets to a point where you're better off just doing more things in one line than trying to do something small and then keep merging it back together. Even worse, there are things that just can't be done on a parallel assembly line at all. It doesn't make a lot of sense to set up the electrical wiring on this car before the frame is finished, for example.

This all means that there is really going to be a point where adding more cores to a computer stops producing favorable results. You will still benefit if you are trying to run several totally separate programs at once or if you want to do something highly parallelizable like video encoding, but not really for games.

Quite simple to explain actually

As you may know, modern CPUs are superscalar, that means even a single core has multiple instances of various components so it can execute multiple instructions (from the same thread!) in parallel. This works very well if the compiler managed to keep side effects between "neighbored" instructions low since the CPU core can detect that and start scheduling them in parallel to the different resources.

Hypertthreading comes into play when the compiler failed, that means if the code happens to be organized in such way that not all resources of a specific type are fully used. (Either that, or because a different thread has a different work load which can use DIFFERENT resources, e.g. one thread using the FPU for floating point arithmetic, the other one using the ALU for integer arithmetic.) So Hyperthreading attempts to fill the idle resources with instructions from the other thread.

Works quite well if this can increase the usage of a specific resource type (e.g. integer units). Doesn't work at all if the one thread is already hitting the limit on a specific resource type, because in that case Hyperthreading will have to cut back resource allocation by the first thread in favor of the second thread.

So you now have suddenly 2 threads, each running at half speed. Hence the 50% CPU usage prediction for Hyperthreaded systems.

Btw.: Works slightly different with AMDs modules. They behave very different to Intels Hyperthreading for SOME instructions (since the corresponding resources are shared module-wide) while for other instructions each core (there are 2 cores per module) has it's very own resources. So it can sometimes outperform Hyperthreading, and sometimes it suffers the very same problems.

It is not THAT difficult. The Intel compiler for example can do parts of the parallelization for you even without any changes to the code. It can do that, because it has a good understanding of access patterns to the main memory so it can auto-detect code sections suitable for parallelization.

And then there is also frameworks like OpenMP (compatible with VC, GCC and Intel compiler, but not with Clang yet) which make parallelization a breeze.
Most important: OpenMP is very efficient, you can already gain a huge performance plus from parallelizing comparably SMALL work shares. Automatically parallelizing a for-loop with only a few hundred iterations and only a dozen floating point operations per iteration already scales almost perfectly.
That's quite important, since small work shares are far easier to parallelize than big ones. Issue is mostly race conditions which can only be avoided by smart access patterns and defining critical sections (sections where only one thread must ever work). Planing this for small sections is quite easy with some practice. Finding suitable patterns and identifying critical sections for larger chunks of code is a nightmare.

As a user who falls into the "knows enough to be dangerous" category, I'm proud of myself for understanding some of the words in your post.

Thanks for the update!

Thanks for the cake, its delicious

As I have actually written a (simple, rather silly) multi-threaded game, I'll use it as an example of some of the nightmares that can occur.

The game was a text based "shoot down the saucers" game, where saucers spawned on the top of the screen and tried moving across, while the player controlled a rocket launcher on the bottom of the screen to shoot it down, all while the saucers would drop bombs randomly on the player.

Every single saucer, rocket, and bomb was its own thread, along with a few others. Every single one of these threads was asynchronous, meaning there was no global timer keeping things in sync, you fired a rocket, it would have its own timer, as would each saucer etc.

These means they are all doing their own collision detection and updating to the screen etc.

Because of this, you never know exactly when something is going to happen relative to anything else, and if something conflicts, horrible things can happen. For example, if you are halfway through updating a saucer position, and a rocket decides it wants to update, it could start printing really weird things all over the place (like turning the rocket into a saucer, often leaving random bits of text everywhere).

This is where the mutexes varrak mentioned come in. Mutex stands for mutual exclusion (ya, computing scientists have weird ways of making names), and is used to block a thread from interrupting another thread in a critical section (code that must be completed in its entirety before anything else can use those resources).

So back to the game example, I had a mutex lock for updating the screen, every time a thread wanted to update the screen, it would request a lock, and if it was unlocked before, it is locked and execution proceeds. once done, you unlock it (if you forget to do this, your screen will just freeze up, as nobody else will be able to access the screen update).


You can probably start guessing why this can't be done totally automatically. The computer has no sure fire way of identifying a program's critical sections. While it may be able to guess that posting stuff to the screen would be one, other things, like collision detection, is not so simple, as there is no way for the compiler to detect that it is a critical section, and not just a standard loop. (along with the other reasons mentioned above by cptconundrum)

While sorian's AI may some day surpass us puny humans, until then, it requires a human to make these decisions.

You should really try again with OpenMP. (Unless you really shouldn't handle objects as individual threads! Threads should also work on a shared data set, unless you have very good reasons not to, such as deferring a network thread or alike.)
Stuff like manual management of mutexes is hidden away very well and parallelizing is as simple as adding pragmas, so no risk of forgetting to unlock a mutex. Also makes is very comfortable to swtch between parallel / single sections frequently, which also isn't exactly recommended when using blank Posix/Win-API for threading due to performance overhead when done wrong.

Plus: You can run the entire code with parallelization switched off so you can get a reference implementation. Very helpful for debugging race conditions by comparing intermediate results.

It was for a university assignment, written in C with posix threads. We weren't given the choice to use any such fancy libraries.

Otherwise, I'm all for using libraries like that, no point reinventing the wheel.

In the pre-hyperthreading era, you could only be doing as many tasks (i.e. threads) at once as you had cores for. If whatever you were doing had to wait on something, the core basically did nothing while it was waiting, which is inefficient.

With hyperthreading, the processor pretends to have twice as many cores as it actually does. This means that each physical core can be assigned two tasks at once and whenever it gets stuck on one of the tasks, it can switch right over to the other instead of being idle. This gets you a little bit more efficiency when there are a lot of tasks going on at once.

When you have a bunch of really intensive tasks, which is often encountered in games and enterprise applications, there is very little time in which a task has to wait on things and therefore there's no "slack" to take advantage of to switch to another task. In other words, at 50% processor utilization, all of the underlying physical cores are fully utilized.

Unlikely. There are small scale ways of recognizing opportunities for parallelization (e.g. auto-vectorization, MapReduce, etc.) but the most effective way to speed up software has always been selecting the right architecture and the right algorithms and making the right trade-offs and that requires a human mind.

If you'll forgive a silly question....

Given that chronocam gives the game a concept of multiple points in time rather than a single mutable state, why did you choose to focus on breaking up a single frame rather than handing a frame to each processor and cycling through them? The lag time shouldn't be much worse than the current single-core performance, I would think.

Yeah i figured as much, but at least i did learn a few things. Thanks for the long responses

Its a real shame it takes so much work to make game use all the cores. but its definitely worth it.

Its probably also a good thing that CPU then wont go all crazy and have insane amount of cores. that would be programmer hell from what i understand.

So, the data isn't stored on the client? If you go back in chronocam, it has to redownload everything again?

Intel is making the first desktop octacore hyper threaded, have fun game programmers! It's your dream!