Multi-threading Part 1

Welcome to another of my articles. This time its multithreading. A topic which seems to fill a lot of programmers with dread, but if used properly it can produce some great results. Traditionally it was the realm of high end servers with multiple CPU's, but with the big two now producing multicore chips that are accessible to gamers, this is a topic which will soon become something every games developer should be considering.

Just in case you don't know what a thread is, the definition I like to use is one of those annoyingly recursive IT definitions... a thread is a single thread of execution within your application. I'm not going to go into the details of multithreading such as time slicing etc., so if you really want to know about the nuts and bolts, check out this Wikipedia page on multithreading.

What I am going to do however is show you how to implement threads with Delphi and provide some details about the things you need to be considering when writing multithreaded applications.

But to get started, lets consider when and why you might want to make your application multithreaded. As an example, I'm going to use our competition entry from the PGD Annual Competition 2006. The basic concept of our entry was to build a game engine that could be used to make 2D top down tiled games... kind of retro RPG style. To make it flexible it had event handlers for practically everything, these were Delphi Web Script II scripts, and for the enemies, it had an A* path finding system.

There was obviously more to it, but these are the two items of importance for this article.

First, lets look at the scripting of the event handlers. In the early stages, comments were made about the event handling. The renderer would block while a script was being executed. Of course, this was going to happen because everything was running inside the main VCL thread, so when we moved (a process handled by our main TDXTimer) we might run an event handling script. Because our main TDXTimer also handled the rendering, everything stopped until the script had finished. This might not be a problem in certain situations, but in ours it was a huge problem. Some of the things we wanted to do within our scripts was to change the visibility of the player, change the players location and to change the state of map cells. Of course, we did all that, but the player only ever saw the final result. As a consequence, some of our work was effectively lost since the player never saw it.

To fix this, I decided that the scripts should be executed by a seperate thread. When I needed to run a script, I stopped the state of the game changing in response to player input and then dropped a pointer to the compiled script into a queue in a script executor. It then ran the script in a seperate thread leaving the main VCL thread free to handle the rendering etc. So, when the script made a change to the state of the player or the game, the player could see the results as the renderer was free to run. When all the scripts in the queue had been executed, the player was once again able to influence the state of the game.

That sounds like a complicated way of achieving this, but it worked really well, and the performance of it was very acceptable on my humble Athlon 800. The A* path finder was a more sophisticated system. It provided three different queues. Low, medium and high priority. When an enemy needed a path, it would submit a path request to the pathfinding thread, along with a callback handler. The pathfinder was able to suspend itself if there were no path requests in its queues (thus saving scheduling time), if it was suspended when the path request was made, it was kick started by the request. It then checked its queues and began processing the jobs, finding paths (or not) for each request on a first come first served priority basis. When it completed a path, it would run a callback that came in with the job request. The path was passed back to the object that requested the path as a parameter of this callback.

Again, it sounds complicated, but it worked really well and, like the script executor, its performance was more than acceptable.

So why is multithreading a good idea?

I suspect a lot of people would say, its not a good idea either because of the apparent complexity multithreading implies or because to get the most out of it, you need to run multiple cores. But as I've already mentioned, multicore machines are cheaper than they ever have been. The masses now have access to technology that was once the domain of the high end server. So suddenly, we find ourselves in an age where we can gain great performance benefits from this.

If you write your game as a standard single threaded application, then running it on a multicore machine will make no difference to the overall performance of the game (you should notice some performance increase as the OS shares other tasks across the multiple cores, but the game itself will not benefit from this). If on the other hand, you take the time and do a good job of making your game multi-threaded, you shouldn't notice too much of a performance hit when running it on a single core machine, but run it on a multicore system and you should notice a good performance increase as the OS makes the most of the extra cores, and as a consequence your threads get more clock cycles.

So whats a 'good job' in multithreading terms?

Well that depends on context. The browser based game I run requires a whole bunch of calculations to be performed every hour in order to make time pass in the game universe. In this context, a good job is making sure that the two CPU's in the server that runs it are running at 100% the whole time this process is running (this server actually spends most of its life doing nothing, idling at 0% utilization). Only then can I ensure we have the fastest completion times as I know that the two processing threads I spawn are running concurrently, one each on the two cores.

In the context of a client side game, it requires something different. In server side applications (like the one I described), it probably doesn't matter too much if other processes suffer when your application is running since the client probably won't see this. But, when multithreading a client application, you must take steps to minimise the chances of single core machines noticing slow down whilst threads other than the main VCL thread are executing, but thats relatively easy to achieve by ensuring that processor intensive threads (such as pathfinding) relinquish control of the CPU periodically or run at a lower priority than your main thread (or both). Since these measures are controlled entirely by software, its easy to adjust them when running on a multicore machine.

Finally, before we get into some code, one of the things that causes alot of problems for people who are new to multi-threading is resource protection. Consider the implications of this code...

Possible divide by 0? Now throw into the equation...

*deep breath* If execution (by a seperate thread) of the second code fragment stops after fFactor^:=0; (as could potentially happen on a single core machine), or both code fragments are running simultaneously (on a multicore machine) and it just happens that x:=100/factor is executed after the fFactor^:=0 but before the loop starts and fFactor is indeed a pointer to the factor variable from the first segment... *boom*

Ok, not quite boom, but you get the picture. This is where resource protection comes in. More of that later... for now, lets look at a basic thread.