An accurate form of Sleep()?

[SuperKoko]

do
{
    if (TimeHasPassed)
    {
        GameObject->Cycle();
    }
} while (true);

This code is equivalent to:

do {
  GameObject->Cycle();
  AbominableSleep(frame_time - time_to_compute_the_cycle);
} while(true);

When someone plays a game, they have very little intention of doing much else

Wrong.
They can still compress files in background.
And if they don't, they may not like to see their battery power vanish if they use a laptop computer.

So when you say that I am wasting 'cycles', you are wrong.

No, you are WASTING CPU cycles. If GameObject->Cycle() takes, say, 10 milliseconds and your game runs at 30 fps, then, your program will try to use 3.3 times more CPU cycles than needed.

About what you said about a thread priority boost, that is due to the QueryPerformance functions, they are probably making a kernel call.

No, I was talking about an hypotetical case where someone would manually boost the priority of your process and notice that normal priority processes (e.g. explorer) are frozen forever.

Which means it will actually run SMOOTHER.

If you think that you get an artificial priority boost, then, it's a shame, not an honor.

GUI threads generically do not use many cycles, they wait until an event has been inserted into the queue.

Which is a good behavior.

So I say, why not use as many cycles as I can, considering the importance of GUI applications over console ones.

Because MY COMPUTER IS NOT MONOTASKING.

Assume that my computer is much faster than required for your game.
I compute every frame in 1 millisecond.
Assume that I compress a big file, using as much CPU power as it can, and I run your game.

If your game used Windows Sleep() operation; My compression operation will be very very slightly slowed down. Every 30 milliseconds, it'd loose 1 millisecond.
If your game use this do-while loop, it'd claim that it constantly needs CPU, and my compression operation will be exactly TWICE slower than normal.

That is why I witness no apparent downside in my testing.

Because you use your system like a monotasking system.

Using GetTickCount() previously (which is horrendously inaccurate, it can be off my 1 millisecond)

timeGetTime() has the accuracy of 1 millisecond.

BTW, what is the point of eating all the CPU if you want a fixed frame rate?

In a single CPU machine, only 1 thread can be executing at any one time (although for such a minute time, it seems like everything is going at the same time) so when my thread is using cycles, it's technically not robbing from any other.

You definitively don't understand what cooperation between threads mean.
You're not really stealing, as the system accepts to give you what you ask, but you're asking more than you need.

Suppose there is a big cake.
Two persons want to eat the cake.
But YOU are allowed to take a part of the cake, because the law says so.
However, suppose that you've just eaten for the dinner and aren't hungry anymore to the point that you cannot eat anything anymore.

If you're a good man, you'll say to the two men: "Cut the cake in two and take the two parts. I won't take my part. I'm not hungry".
If you're not a good man, you'll say: "Cut the cake in three and give my part", then, you'll drop your part on the floor and jump with your two feet right on it so that REALLY nobody will ever benefit from it.

This is the game you're playing with the CPU. The CPU is a cake. You shouldn't claim that you need to eat it if you don't.

Games require that code do not take very long to execute in their minute selves, as a whole - the calling of all those functions, etc... must add up to less than the intended cycle time for a frame, otherwise... It will run at a slower framerate than the target.

A proper Sleep() operation in a variable framerate game doesn't prevent that.
Maybe you never played to GlQuake?
This is instructive.

It's not my applications fault - it's the design of the OS.

No. Your application is too badly programmed to have a variable framerate. This is its fault.
BTW did you search MSDN for multimedia timers?

My app in that situation due to the OS's design, is what is keeping the CPU actually doing something.

Mhhh... How do you think that GlQuake is perfectly smooth and yet, don't eat my CPU? Is it some sort of black magic?


Anyway, I feel that the discussion won't go anywhere.

Could you give the name of your application(s) so that I can avoid to ever install it on my computer?

[JamesSchumacher]

Then tell me...

How do you write a game that needs accuracy of better than a millisecond?

WaitFunctions will not help you out.

timeGetTime has a resolution of 1 MILLISECOND.

And the answer to your question is simple - it answers mine as well. Those games? I would bet run something like my loop for a little while, then API::Sleep() to give the other threads more time, then back to what I do.

THAT is how they would do it.

Keeping track of time LESS than one millisecond.

[bitbo]

Hi All!

Here my personal solution which is working in industrial multithreaded environment since several years now:

File PnSleep.h:
class CPnSleep
{
public:
CPnSleep(BOOL bFullResolution = FALSE);
virtual ~CPnSleep();

BOOL Sleep(UINT ms);

protected:
HANDLE m_hEvent;
BOOL m_bFullResolution;
};
File PnSleep.cpp:
CPnSleep::CPnSleep(BOOL bFullResolution):
m_bFullResolution(bFullResolution)
{
m_hEvent = CreateEvent(NULL, FALSE, FALSE, NULL);
}

CPnSleep::~CPnSleep()
{
CloseHandle(m_hEvent);
}

BOOL CPnSleep::Sleep(UINT ms)
{
BOOL bRet = TRUE;
MMRESULT mmResult = timeSetEvent(ms, m_bFullResolution ? 0 : ms/10, (LPTIMECALLBACK)m_hEvent, NULL, TIME_ONESHOT | TIME_CALLBACK_EVENT_SET);
UINT nWait = ms > 42 ? 42 : ms;
UINT nElapsed = 0;
while(WAIT_OBJECT_0 != WaitForSingleObject(m_hEvent, nWait))
{
nElapsed += nWait;
if(nElapsed > ms)
{
bRet = FALSE;
break;
}
}
timeKillEvent(mmResult);
return bRet;
}

bFullResolution:
A resolution of 0 indicates periodic events should occur with the greatest possible accuracy. To reduce system overhead, however, you should set bFullResolution = FALSE.


Any comments are welcome !

Why 42 ? Please find the answer at:
http://en.wikipedia.org/wiki/The_Ans...and_Everything

Bye, bitbo

[SuperKoko]

I would bet run something like my loop for a little while, then API::Sleep() to give the other threads more time, then back to what I do.

No.
They don't loose CPU cycles they don't need.

They do something like:

Time t1=GetAccurateTime(); /* internally use QueryPerformanceCounter ONCE */
/* assume that the Time object has overloaded operators */
for(;;) {
  Time t2=GetAccurateTime();
  Time tdiff=t2-t1;
  if (tdiff < 1/max_fps) ::Sleep((1/max_fps - tdiff).toMilliseconds()); /* This DOES NOT need to be accurate... as far as it waits less than 2*(1/max_fps-tdiff) and more than (1/max_fps - tdiff)... The game will still have the max frame rate */
  if (tdiff > 1/min_fps) tdiff=1/min_fps;
  t1=t2;
  ComputeFrame(tdiff); /* tdiff is the time difference between two frames to be taken in account for movements of entities */
}

To get a smooth game, max_fps should be set to something like 80 or 90 (ideally a user setting as in Quake II and Quake III). Setting a higher max_fps is useless as it would be higher than the screen frequency.
Or there may be a different frame rate for the physical computations and the visual computations, in that case there should be two max_fps and min_fps values.

How do you write a game that needs accuracy of better than a millisecond?

Using QueryPerformanceCounter, but calling it only ONCE for every frame.
QueryPerformanceCounter(), timeGetTime(), GetTickCount()... All these functions eat very few CPU cycles if they're only called ONCE.
GlQuake use QueryPerformanceCounter(). Quake II uses timeGetTime().

BTW: Calling QueryPerformanceCounter() doesn't change the thread priority. If you need to change the priority call SetPriorityClass().
However, doing things such as an empty loops (if others program don't behave badly, unlike yours) has an effect on the probability that your thread is currently executing when you need something.

Analogy with the cake:
Assume that there's a big unlimited cake, but only one person can eat a piece of it at a time, because it must respawn.
Everybody (EXCEPT you) is nice and eat the cake only when he needs to.

Anybody gets the right to eat some part of it. However there's a queue to the cake.
To limit (but not totally prevent) abuses, nobody can eat the cake more than twenty seconds UNLESS he's the only one in front of the cake.
So, for example, if there're three persons on the queue and all of them need to eat the cacke 60 seconds, the first one will eat it 20 seconds, than the second one, than the third one, and back to the first one. There'll be 3 cycles before everybody gets the cake he needed.

Now, YOU noticed that very few people eat the cake TODAY... Most of the time, the queue is empty. Nobody eats the cake at all!
You noticed that, sometimes you need to eat the cake... But, sometimes (e.g. 10% of the time), there's somebody in front of the cake and you need to wait between 1 and 3 seconds that he finishes his part of the cake (because most people don't need 20 seconds to take their part of the cake), then, you eat your part.

Then, you had the idea of camping in front of the cake... Now, if somebody come (which happens sometimes), you'll not give your place before some time (between 0.00000000000000001 second and 20 seconds: Note that you have absolutely NO guarantee about the duration of this time... You just have a high probability (95%) that it be larger than 1 second) since you're currently in a time slice so that, if you need the cake at this exact time, you'll get it immediately instead of waiting for 1 to 3 seconds.

First, notice that your behavior is already bad for other people (who are much more numerous than you): Instead of getting immediately their part of the cake 99% of the time (with 1% of probability of having to wait for the queue), they'll wait 1 to 20 seconds in average.

Secondly, if OTHER people become evil like you, they'll all camp in front of the cake to get as much "cake time" they can. Then the queue will become huge all the time (say 100 persons), and you'll get the cake only 20 seconds every 100*200=20000 seconds. In other words, you'll WAIT lots more than needed.

Queues work, because only people who need the service provided at the end of the queue use the queue.

If everybody went to the every queues: "Just in the very improbable case I need the service when I get to the end of the queue", then, queues would become much less efficient.

[SuperKoko]

UINT nWait = ms > 42 ? 42 : ms;

Why do you block on WaitForSingleObject at most 42 milliseconds? To be in front of the cake more time? Being in front of the cake once every 42 milliseconds is probably insufficient, anyway.
If you want to... Then, at least, you should play this trick only the 42 last milliseconds of a wait operation.
e.g. If you wait 100000 milliseconds, then, do a WaitForSingleObject for 100000-42 milliseconds, and then, a second WaitForSingleObject for 42 milliseconds.
Anyway, I don't think that it'll work better than WaitForSingleObject(m_hEvent, INFINITE).

nElapsed += nWait;

Don't do that. Biais will be added up. i.e. If in average, WaitForSingleObject returns one millisecond before than the wait time, for 4200 milliseconds, you'll wait 4100 milliseconds in average.
Moreover, absolute inaccuracies (random variations around the wait time, not biaised on a particular side) will approximatively grow as the square root of the time you wait instead of being constant.

You should rather compute the time difference between the base time and the current time at every iteration:

DWORD time0=timeGetTime();
while(WAIT_OBJECT_0 != WaitForSingleObject(m_hEvent, nWait))
{
if ((timeGetTime() - time0)>ms) {bRet=FALSE;break;} /* warning: Will probably return FALSE easily... I'd rather return TRUE than FALSE... */
}

Instead of a while loop, try that:

bRet = WAIT_OBJECT_0 == WaitForSingleObject(m_hEvent, INFINITE));

If you want to get a time slice immediately (which may be quite unfair unless your app controls device drivers and has to be a real time app), you may call SetPriorityClass() to set a HIGH_PRIORITY_CLASS.
In that case, when at the millisecond the event is occurs, Windows will STOP normal priority processes even if one of them is in a CPU intensive loop, and immediately give the time slice to your program, and won't give the CPU back to the normal priority process before you enter in a blocking call again (e.g. WaitForSingleObject).

Theorically, you could also call SetPriorityClass with HIGH_PRIORITY_CLASS immediately before WaitForSingleObject and with NORMAL_PRIORITY_CLASS immediately after WaitForSingleObject, so that you immediately get the time slice when the wait operation finishes, but, you won't have any guarantee that your time slice will lasts more than 5 nanoseconds... In other words, it makes little sense.

[CBasicNet]

Then tell me...

How do you write a game that needs accuracy of better than a millisecond?

Keeping track of time LESS than one millisecond.

Since when is your sleep has accuracy of better than a millisecond? Your sleep accuracy depends how much time your work item, which you execute in your sleep function, complete its work. If your work item use more than a millisecond, then too bad for your game! Let's say your work item use 0.55 millisecond, on the second loop it would exceed 1 millisecond, oops not accurate anymore. If the fps is less than 60 fps on a particular PC without the need for sleep, your work item don't get to execute, and your game is screwed because it is hardcoded to run everything in 60fps exact, not less. Your game is assumed to run on a PC which can run it faster than 60 fps, so that your sleep/wait code can work. What if your work item don't get to execute? Is it okay? If it is okay, then it is something isn't worth doing. If it is worth doing, start a thread to do it, rather than do it in your sleep.

[CBasicNet]

Then tell me...

How do you write a game that needs accuracy of better than a millisecond?

WaitFunctions will not help you out.

timeGetTime has a resolution of 1 MILLISECOND.

And the answer to your question is simple - it answers mine as well. Those games? I would bet run something like my loop for a little while, then API::Sleep() to give the other threads more time, then back to what I do.

THAT is how they would do it.

Keeping track of time LESS than one millisecond.

It is not accurate anymore if you use ::Sleep(). In your scheme, if you only utilise ::Sleep() for period longer than 1 millisecond, then your scheme is only accurate for period less than 1 millisecond.

[JamesSchumacher]

Since when is your sleep has accuracy of better than a millisecond? Your sleep accuracy depends how much time your work item, which you execute in your sleep function, complete its work. If your work item use more than a millisecond, then too bad for your game! Let's say your work item use 0.55 millisecond, on the second loop it would exceed 1 millisecond, oops not accurate anymore. If the fps is less than 60 fps on a particular PC without the need for sleep, your work item don't get to execute, and your game is screwed because it is hardcoded to run everything in 60fps exact, not less. Your game is assumed to run on a PC which can run it faster than 60 fps, so that your sleep/wait code can work. What if your work item don't get to execute? Is it okay? If it is okay, then it is something isn't worth doing. If it is worth doing, start a thread to do it, rather than do it in your sleep.

The idea in this Sleep() is not the implementation here in the timing method of milliseconds, that can be modified.

The idea in accuracy is choosing what the accuracy level is. That can be changed very easily.

void SleepInMicroseconds(unsigned long long dwMicroSeconds)
{
    const unsigned long long nTicksInSecond = GetTicksInSecond();
    const unsigned long long nTicksInMicro = nTicksInSecond / 1000000;
    // etc....
}

See the documentation for QueryPerformanceFrequency. It's the function to query the tick frequency of the high resolution counter of the system if one exists. All newer systems will support a high resolution counter.

[Arjay]

The idea in accuracy is choosing what the accuracy level is. That can be changed very easily.

What good is the accuracy if the loop can't complete within the time period? Earlier your responses were to defend code that spun stating that you needed to use the available processor power, because "why not use it?" to paraphrase. Do you still believe this is a good idea?

[JamesSchumacher]

What good is the accuracy if the loop can't complete within the time period? Earlier your responses were to defend code that spun stating that you needed to use the available processor power, because "why not use it?" to paraphrase. Do you still believe this is a good idea?

If the application is the only thing running OR the other apps in the background have no worker threads... Then yeah.

There is also another reasoning behind this technique, however it's not loop related.

Consider the following:

class GameTimer
{
public:
    GameTimer(void (__stdcall * Callback)(),unsigned long milliWait) : CallbackFunction(Callback)
    {
        TicksInSecond = GetTicksInSecond();
        TicksInMillisecond = TicksInSecond / 1000;
        MillisecondsToWait = milliWait;
        TotalTickWait = TicksInMillisecond * milliWait;
        PreviousTicks = 0;
        CurrentTicks = GetCurrentTicks(); // so we do not mess up on PreviousTicks
        TicksPast = 0;
    }
    ~GameTimer()
    {
    }
    // The following will be called by GameObject->Cycle()
    void Cycle()
    {
        PreviousTicks = CurrentTicks;

        CurrentTicks = GetCurrentTicks();

        const unsigned long long nDifference = CurrentTicks - PreviousTicks;

        TicksPast += nDifference;

        if (TicksPast >= TotalTickWait)
        {
            (*CallbackFunction)();
            TicksPast = 0;
        }
    }
private:
    void (__stdcall * CallbackFunction)();
    unsigned long long TicksInSecond;
    unsigned long long TicksInMillisecond;
    unsigned long long MillisecondsToWait;
    unsigned long long TotalTickWait;
    unsigned long long PreviousTicks;
    unsigned long long CurrentTicks;
    unsigned long long TicksPast;
};

The idea here is that whenever the GameObject->Cycle() method is called, it will run through it's timers in a collection and call each timer's own Cycle() method.

[Arjay]

If the application is the only thing running OR the other apps in the background have no worker threads... Then yeah.

This statement implies that it should matter if any background application have more than one thread. Do you think the OS cares if it's scheduling 1 app with 9 worker threads or 10 separate single-threaded apps?

[JamesSchumacher]

This statement implies that it should matter if any background application have more than one thread. Do you think the OS cares if it's scheduling 1 app with 9 worker threads or 10 separate single-threaded apps?

Actually, yes it does... That's what the SetPriorityClass() (I think that is the one) function is for. Setting the PROCESS PRIORITY.

And it's all solved simply by this:

**************** README ****************

ETC........................................................................

NOTE: It is highly recommended that you run
this game without any other application running.

The point of the matter is this... Say I want 50 fps in a 2D game, that is not asking very much. Okay... A Windows API media timer would probably work great right here as each frame has .020 seconds in between. For a 2D game, 100 FPS wouldn't be asking much... (PROBABLY)

The point of the matter is this...

In a full hardcore 3D game in which I would want the processor, I would do what I described above and just note to the end user for performance purposes run the game with no other applications in the background.

In a 2D game? Multimedia timer would be great.

[Arjay]

Actually, yes it does... That's what the SetPriorityClass() (I think that is the one) function is for. Setting the PROCESS PRIORITY.

Actually, this has nothing to do with my question. I asked whether you believe the OS schedules threads in an app with 9 worker threads differently than it schedules 10 separate single-threaded applications. Just to be clear all threads in all apps have normal priority.

Can you answer the question (without going into an irrelevant game discourse)?

[JamesSchumacher]

Actually, this has nothing to do with my question. I asked whether you believe the OS schedules threads in an app with 9 worker threads differently than it schedules 10 separate single-threaded applications. Just to be clear all threads in all apps have normal priority.

Can you answer the question (without going into an irrelevant game discourse)?

Technically speaking? They are arranged in pretty much the same manner. The data is stored in (what else) a priority queue. Which can be implemented as doubly linked list, or as a vector storing pointers to data structures.

BTW... The Windows thread scheduler uses TWO values to determine how often a thread gets a slice, and for how long.

[Arjay]

BTW... The Windows thread scheduler uses TWO values to determine how often a thread gets a slice, and for how long.

In reality the algorithm used to determine thread scheduling can change (and does change) between versions of the OS. It's much better not to make assumptions about exactly how the scheduler functions, but rather to code it up more of like "I don't know how long my thread time slice will be or whether I'll get the complete time slice". The idea to use the maximum amout of CPU available in order to achieve better accuracy is flawed because your thread can be preempted at anytime.

At any rate, since you haven't answered the question in the last couple of posts, it's unlikely I'm going to get a direct answer.