• Recent Tutorials

  • Tripping The Class Fantastic: Multi-threading Part 1

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

    Code:
    x:=100/factor;
    Possible divide by 0? Now throw into the equation...

    Code:
    fFactor^:=0;
    for loop:=low(fData) to high(fData) do
      fFactor^:=fFactor^+fData[loop];
    *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.

    Comments 6 Comments
    1. chronozphere's Avatar
      chronozphere -
      Fantastic articles athena. I will definitely read 'em all.

      Multithreading still scares me a bit and the only way to overcome that is by rolling up the sleeves haha... I would like to use them in my engine, to separate rendering and audio from the rest of the code.

      I really need to write an article too btw. There aren't that many and new site does a good job at presenting them.
    1. WILL's Avatar
      WILL -
      Quote Originally Posted by chronozphere View Post
      I really need to write an article too btw. There aren't that many and new site does a good job at presenting them.
      Feel free! We need a lot more beginner articles. Either an introduction to a specific API or a completely non-API specific article about the basics of game programming.
    1. AthenaOfDelphi's Avatar
      AthenaOfDelphi -
      Thanks

      It's not quite as scary as it may seem at first... although I speak from the point of view of someone who nearly got fired because the first time they used multi-threading was in a business critical application which kept crashing because I messed up

      After that, no programming problem has ever seemed quite so scary
    1. code_glitch's Avatar
      code_glitch -
      nice stuff. i have written one slightly less popular article as it would seem but am working on another as will would tell you with the newbie-frindly project or something
    1. Dan's Avatar
      Dan -
      AthenaOfDelphi,
      Do you have any comments on suspend and resume procedures being deprecated starting from D2009. Since you are using these methods in your examples it may confuse some people because stuff normally gets deprecated when better ways of doing things become available.
    1. AthenaOfDelphi's Avatar
      AthenaOfDelphi -
      Dan, apologies for the delay... well, what can I say... I didn't realise they were deprecated, certainly my compiler doesn't complain about anything (I get the feeling from reading one or two articles it should complain).

      Whilst I understand the theories I've read, I can honestly say I've (a) never used the suspend/resume mechanism for synchronising threads and (b) never had any problems using suspend/resume. I generally use it for job processing type scenarios where the thread put's itself to sleep until it is needed. Replacing these calls with an eventing mechanisms (wait_for_single_object IIRC) shouldn't be too much of a problem. Something like this:-

      Code:
      unit classSuspendableThread;
      
      interface
      
      uses
        sysUtils, classes, windows;
      
      type
        TSuspendableThread = class(TThread)
        protected
          fWakeUpEvent        : THandle;
          fSleeping           : boolean;
      
          procedure goToSleep;
        public
          constructor create(createSuspended:boolean);
          destructor Destroy; override;
      
          procedure terminate;
      
          procedure wakeUp;
      
          property sleeping:boolean read fSleeping;
        end;
      
      implementation
      
      constructor TSuspendableThread.create(createSuspended:boolean);
      var
        temp    : string;
        nameBuf : PWideChar;
      begin
        inherited create(createSuspended);
      
        temp:='WUE-'+intToHex(self.ThreadId,8);
        nameBuf:=strAlloc(length(temp));
        strPCopy(nameBuf,temp);
        fWakeupEvent:=createEvent(nil,false,false,nameBuf);
        strDispose(nameBuf);
      end;
      
      destructor TSuspendableThread.destroy;
      begin
        closeHandle(fWakeupEvent);
      
        inherited;
      end;
      
      procedure TSuspendableThread.terminate;
      begin
        TThread(self).terminate;
      
        if (fSleeping) then
        begin
          wakeup;
        end;
      end;
      
      procedure TSuspendableThread.wakeUp;
      begin
        if (fSleeping) then
        begin
          try
            setEvent(fWakeupEvent);
          except
          end;
        end;
      end;
      
      procedure TSuspendableThread.goToSleep;
      begin
        fSleeping:=true;
        waitForSingleObject(fWakeupEvent,INFINITE);
        fSleeping:=false;
      end;
      
      end.
      This class works, call 'wakeUp' instead of resume (although resume, or it's replacement start would still be needed if you created it suspended). You will of course note that the 'gotoSleep' method which replaces suspend is now protected. Calling it from anywhere other than the execute method will hold the calling thread.

      This solution is far from perfect. The Windows API calls keep a count of suspends and resumes which this class does not. I suspect there are numerous ways of solving the puzzle and your solution will depend very much on usage.

      Do I think deprecating them is a good idea... it would be a cold day in hell if I said yes. They are legitimate mechanisms for controlling threads (and as I say, ones I've used myself on numerous occasions with no problems). So, I've just gone looking for an answer. I think this excerpt sums it up nicely (taken from this article by Peter Richie):-

      For time eternal there has been a way to suspend (and by association resume) another thread. It wasn't until .NET 2.0 that someone took leadership and conceded that suspending another thread is not a safe thing to do. .NET 2.0 deprecates System.Threading.Thread.Suspend() and Resume() (although, Resume() isn't dangerous by association...).

      Basically, Suspend() has no care that the thread may actually be managing one or more complex invariants that can't be changed atomically. Normally with complex invariants synchronization is used to ensure while one thread is modifying the individual components of an invariant another thread doesn't try to access it. This is important because the validity of an invariant is rarely atomic; meaning changing an invariant may take several steps and may be in an unknown or invalid state between the first and the last step (a date is a good example, setting the day and month is two steps; until both steps are complete the date might be invalid). Suspending a thread circumvents the synchronization primitives and cuts the thread off at the knees.
      Basically, calling suspend from outside a thread is bad... well all I can say is "there's a suprise". I've never done it and I wouldn't encourage you to do it for the reasons Peter gives.... the caller of suspend has no idea about the status of the thread. So, maybe a better solution would to have been to change visibility of the suspend method so that it was only accessible to the thread itself.

      Who knows, but I certainly don't agree with removing them as it's going to mean we have some changes to do at work when we finally port to an up to date Delphi version.