Threadloop efficiency

[Arokh]

I'm programming a Game which needs a loop that
works off Events that are placed by different Objects.

I already thought of some approaches and tried some of them,
but I'm still unsure which I should take.

(A little introduction)
Every Building in the game produces events which are stored in an array and
if the time has passed (given by the event) the event should be executed.

Solutions:
1. Every Building has an thread which loops looking for new events to be executed.
At first I wanted to go with this version, but I was afraid that it could too much,
so I made a test where 1000 (timer)threads where made with almost nothing in the thread and
the processor load went up pretty high which so I tried to think of another solution.

2. One thread for every building
Going to the other extreme, with just one thread for every building,
I have the problem that I cannot set different intervals to every buildingkind and some other issues.

3. One thread per buildingkind
So now I think I'm going with this method which should be a good way inbetween.


The real problem that I'm having is that I can create those threadloops in three different ways and
I have no idea which suites my needs best.

1. Create an timerthread (Threading.Timer)
This has the problem that the thread could have nothing to do (no stored events) wasting cpu power.

2. Create an Thread with an endless loop wherein the thread sleeps after going through the stored events

3. Instead of putting the thread to Sleep I thought of ending the thread'S time slice so
that other threads are processed.
This method is the one I'm most interested because it (correct me if I'm wrong)
is able to ajust to different cpu speed lowering the load on the CPU.
I thought with (Threading.Thread.SpinWait) I would be able to do that but
the CPU load went up to 100% even worse than with the Timers and
if I set the iterations very high the movement of the form stutters.
What is an interation in SpinWait exactly?

Dim EventThread As New Threading.Thread(AddressOf EventHandler)
    ...
Private Sub EventHandler(ByVal State As Object)
    Dim RegBuilding As Short
    Dim RegBuildings As Short
    Dim BuildingEvent As Short
    Dim BuildingEvents As Short

    Do
        BuildingEvents = BuildingsDB.Count - 1 

        For RegBuilding = 0 To RegBuildings 'Loop though Registered Buildings
            With PlayerDB(BuildingsDB.Item(RegBuilding).Player).BuildingDB(BuildingsDB.Item(RegBuilding).BuildingID)
            'Point to the actual BuildingObject
                BuildingEvent = .Events.Count

                For BuildingEvent = 0 To BuildingEvents 'Work Off Events of the CurrentBuilding
                    .Events(BuildingEvent).Check() 'Check if it is time to execute Event
                Next
            End With
        Next
        Threading.Thread.Sleep(100)
    Loop
End Sub

Is there any better way to lower the load on the CPU?

 

[MrPaul]

I would advise against SpinWait

What is an interation in SpinWait exactly?

I refer you to MSDN:

SpinWait essentially puts the processor into a very tight loop, with the loop count specified by the iterations parameter. The duration of the wait therefore depends on the speed of the processor.

SpinWait is not generally useful for ordinary applications.

The code SpinWait executes is designed to prevent problems that can occur on computers with multiple processors.

In other words, SpinWait causes the thread to wait, but not yield its timeslice. This is most useful for situations where a state change is likely to occur imminently. I believe it is only really useful in multiprocessor/HyperThreading/etc situations.

I'm curious as to why you think having a constantly running thread which periodically sleeps is preferable to multiple timer threads. I would expect the implementation of Timer is probably similar to this anyway, and either way, if there are no events to process, both approaches will be 'wasting CPU power'.

I suppose what it comes down to is:

1. What is the granularity of the events? (periods in minutes? seconds? milliseconds?)
2. How variable is the granularity?
3. How many types of building?
4. How likely is it to be that there are no events for a particular building?

Finally,

2. One thread for every building
Going to the other extreme, with just one thread for every building,
I have the problem that I cannot set different intervals to every buildingkind and some other issues.

You cannot? With a bit of redesign this would certainly be possible. I obviously can't comment on the other issues.

Good luck

 

[Igor Sukhov]

I refer you to MSDN:

In other words, SpinWait causes the thread to wait, but not yield its timeslice. This is most useful for situations where a state change is likely to occur imminently. I believe it is only really useful in multiprocessor/HyperThreading/etc situations.

I don't think it has anything to do with the ‘hyper threading’ or multi CPU's.

SpinWait does not cause system to switch to the kernel mode hence saving lot of precious CPU ticks required for transition from user mode to kernel mode. Of course if only pays off in the situation when only small delay is required. Therefore, consequent calls to Thread.Wait could potencially void any performance benefits gained by remaining in user mode.

The Win32 "critical sections" employ the similar waiting strategy trying to wait in the user mode first.

 

[PlausiblyDamp]

Could you not create a single timer which runs as a 'heart beat' and is the minimum amount of time between 'events', when each heart beat occurs check which events need raising and raise them.

Alternatively, depending on the style of game, you might have a very tight game loop anyway - as part of this loop check for events to raise and raise them.

 

[MrPaul]

I don't think it has anything to do with the ‘hyper threading’ or multi CPU's.
SpinWait does not cause system to switch to the kernel mode hence saving lot of precious CPU ticks required for transition from user mode to kernel mode.

As I understand it, on a non-multiprocessor CPU, not switching to kernel mode would mean no other threads could be scheduled and therefore any resource being waited on would not have a chance to be released. Hence why it's only really useful on systems capable of real multithreading. At least that is/was the case with the corresponding functions in the Win32 platform API.

 

[Arokh]

Ok to explain the problem better I will give some details
of how the game sould work.

I want to program something like a browser game (like War of Galaxy Icewars etc.)
without the browser part , instead having a client which connects to the server.

So I started to program the Server part.
First I wrote the Classes of the buildings like (Lumberjack etc.) and
went into more detail letting the workers in that building be given tasks by the Building Class,
like going to wood, cut wood, go back, return it to the stockpile (think of Settlers 1 or Stronghold).
I want to realise that by those events which are raised when specified time passed and
then adding new ones according to the situation.

Since I want to be able to handle many players (Like those browsergames), the number of buildings could get very high.
That has led me to the question of how many Eventsloop I need.
As I said in the first post first I wanted to give each building such an EventLoop but
I figured that could be a little to much.

So the other options are:
Having one big timer
Having a timer for each buildingkind,
which I figured is best because that enables me to use more than one processor.
But I really don't know if it is needed to be able to run it on more than one processor since
I don't know how much power the program will need.

To answer MrPauls questions:
1. That is something which I don't know myself
since I don't know how much power the program will need in the end.
But since the users will theoretically increase more and more
I will have to increase the granularity.
To keep things short:
I want to have a short period but also I want to ensure
the program doesn't make the PC unusable since there are other things running on it.
Therefore I thought ending the (EventLoop) Threads TimeSlice would solve all the problems
since it does only the things it needs to do and then goes on to the other threads
which is then like a dynamic timer, or so I think/thought

2. As above

3. I don't know that myself since I want to be able to add more and more buildings later on but
for now I think it will be something like 20.
But the player will be able to build the same building countless times
of course this will be limited by the needed resources etc.

4. Well the player will be able to set a building to hold but
in that case I will stop the (Eventloop) Thread also.
But there will be buildings which will have very different eventcounts.

PlausiblyDamp:
Well of course I could do that.
I just don't know which way is the better way to go.
The only downside I know if I do it all in one timer is that
I lose the abillity to run the program on more than one CPU efficiently but
other than that I'm pretty open to suggestions (If one timer is the better way I will go along that way then).
I want to raise events (Goto BlaBla | Arrival on 15:00 25.07.06 to give the basic idea) when
the specific time is passed, in a way which uses resources as less as possible.

Also just out of curiosity when start a new thread and let it Loop endlessly
which handles the Events and then tells the thread to end its TimeSlice.
How high will be the CPU load (Presumed the handling of the events doesn't take much time)?

 

[Igor Sukhov]

As I understand it, on a non-multiprocessor CPU, not switching to kernel mode would mean no other threads could be scheduled and therefore any resource being waited on would not have a chance to be released. Hence why it's only really useful on systems capable of real multithreading. At least that is/was the case with the corresponding functions in the Win32 platform API.

I can't agree. Obviously, multi CPU's boxes utilizing several processors are better suited to handle "wait scenarios", but the actual benefit of WaitSpin (saving time not going into the kernel mode) function (and the Win32 functions used to implement that it) doesn't require machine to have several CPUs.

 

[snarfblam]

Back onto topic...

How is this game meant to be run. There are games like minesweeper where it is important to utilize as little CPU power as necessary, and there are games like Unreal Tournament where the need to share CPU power with other applications is minimal. If your game is more along the lines of the latter, I highly recommend using a solution along the lines of PD's "heartbeat". A great heartbeat is the monitor refresh rate, where you examine the amount of time that passes between each refresh and perform logic accordingly (for each timed event, you examine how much time has passed and determine if the "deadline" has passed yet, and if so, perform said event). If you want the advantages of multi-threading, you can always dispatch tasks to worker threads.

 

[Arokh]

The server part, which I'm currently programming,
is only a process which runs in the background (like a dedicated server)
with no forms or something like that.

Although the PC where I plan to let the server run on is mostly used for data storage,
it is also sometimes used as a media center (playing Video files on TV).
So my aim is to create a program which does not use up all CPU resources.

So I'd rather not have something like Unreal Tournament,
but I can't expect it to be something like Minesweeper,
because it just waits for userinput until it does something.
In my case it will recieve input from the clients which connect to the server,
executes the commands (like building a Lumberjack) and the server will play itself
(letting the Lumberjack doing its job) without needing the client to do anything,
but the client can always destroy, stop etc. the building.

But I guess going with one timer is still the better choice.

So now my other question, if I run one big timer which desing do I chose to create it:
Go with a fixed Timer (Threading.Thread.Timer) or create a simple new thread
with an endless loop and let it pause after every iteration of the loop.

I also want to try the way I said in my previous post (last 3 lines).
Is there anyway to end a timeslice of a thread?

 

[MrPaul]

Thread.Sleep

System.Threading.Thread.Sleep(interval).

Specifying an interval of 0 causes the thread to relinquish the remainder of its timeslice to any other threads/processes which might be waiting. From experience I have found that this can cause CPU use to max out, as the thread is continuously rescheduled when there are none waiting, so sometimes I use an interval of 1.

Good luck

 

[Wile]

I think there is one question that has a big performance on the server side (and client side) of the game:
How much of the game will be handled server side?

If I take the settlers example:
After placing a structure you can balance the load between client & server a bit. Putting everything server side:
-Server keeps track of the animation (so it triggers the 'walk to tree', 'chop tree', 'walk back to building' animations) the server can also update the wood resource update at the correct moment. This has the advantage that it is quite hard for players to cheat as the server determines the amount of resource a player has.
Or you can let the client side take care of most of the work.
-Server only knows about the structure, but lets the clients do all the calculation. This means the client side will trigger the correct animation, update the resource count, etc. Disadvantage: easy to cheat. Advantage: a lot less communication between client & server, load on server is much less.

You can play around with this balancing (server side vs client side) a lot to optimze performance, for cpu (client & server side) and bandwidth requirements.

To make sure you dont overload the system to much, I would go with the solution from Plausiblydamp. Have a 'heartbeat' timer at say 25 msec (that gives you 40 updates per sec, more than enough for AI, triggering animation, etc.). It will check each building/person/item to see if something has to be done. Most things should be able to very quickly check if they have something to do.
It isnt hard to make an overload protection for this mechanism either: if one timer pulse is till running while the next is triggered, prevent the 2nd from checking every object. If this protection is needed often you'd better look into changing the updatefrequency and the work performed during an update.

 

[Arokh]

Most of the Work will be done by the server, because it is needed that way.

Maybe I should have said it a bit clearer:
The server will continue the Game even if no clients are connected.

A user can register himself by the server,
the user gets a starting point and can begin to build his own "empire".
The time needed to build something can exceed days,
but the user is not needed to be connected to the server to
let the building to be build successfully.

So to say the game I want to program play over a very long period of time but
also the game isn't meant to be to take full attention of the user but
something you can log on as you please.

 

[PlausiblyDamp]

For activities that last minutes or hours then a timer of 20 or 30 seconds would probably be enough, rather than needing to provide accurate figures every second or less the clients could either only update when the event is raised or potentially interpolate figures from averages provided by the server - if the client figures are slightly out then the next real update would correct this.

Client side animations would therefore be more of an illustration of server side events rather than an actual, 100% accurate display of them. e.g. using your mining example the figures could be seen walking to and from the mine but the actual timing of when the resources are updated isn't tied into this display.