Recently I had to write some code that ran once every second. It turned out to be harder than I thought.
The easy way / lazy way / way many programmers would do it if they can get away with (way) is:
while (true)
{
doJob();
Sleep(1000); // Sleep for 1000 milliseconds
}
this roughly does the trick. It will call the doJob() function, Sleep for one second, then repeat. Still this is not perfect code if you want to keep your code synchronized to another clock (typically the computer’s internal real-time clock, which runs in hardware and is crystal-controlled, making it very accurate). Let’s imagine the doJob() function above actually controlled a real, physical clock with hands, and moved the mechanism ahead by one second. With the above code it might appear to show the correct time for a while but soon it would drift behind and start to show the wrong time, because the doJob() function itself takes some time to complete (then there’s a 1000ms sleep), which means the entire loop takes more than 1000ms.
I faced a similar problem in my program and my first (naive) attempt to put it right was to do this:
while(true)
{
int startTime=GetSystemTime();
doJob();
int endTime=GetSystemTime();
// Sleep for 1000 milliseconds less the time taken for DoJob()
Sleep(1000 - (endTime-startTime));
}
Here I have captured the computer’s internal clock’s time (in milliseconds), once before the call to doJob() and once after it, I then only sleep for the remaining milliseconds left in the 1000, so if (endTime-startTime) equates to 34 that means doJob() took 34 milliseconds to execute so if I subtract 34 from 1000 I get 966, so that’s all I have to Sleep() for then my loop always runs in exactly one second, right?
I wish. That’s what I thought too and while it’s a good improvement over the last code snippet, it’s still not perfect and the clock will still start to drift behind after a while. The above code may keep the correct time for several days or even years on a fast enough computer but on a long enough timescale it will always drift out of sync because the time spent executing the GetSystemTime() function is not being accounted for, as well as the time in between each line! Yes there are tiny time gaps between each line of code, not to mention the time going from the end of the loop back to the beginning.
With each iteration of the loop all these unaccounted-for bits of time sum up to exactly the amount of time the timer drifts out by.
So that didn’t work….
The next bright idea I had was to read the system time at the beginning of each loop and compare it with the time the last time the loop ran, I could then figure out exactly how long the loop took each time, then subtract 1000 from that number to get the number of milliseconds over-time the last loop ran, which I could then deduct from the next loop.
For example if the loop takes 1015 ms to run at time A, that meant it took 15ms longer than it should, so to remedy this and get the clock ‘back on track’, I would sleep for 15 ms less the next time. That way any disparities in timing are always accounted for in the next loop and over time the clock should stay in sync with the system clock (give or take being a few milliseconds out each second), but it would never drift any more than this even if the program ran for a million years.
I think I’ve cracked it! I’ll code it up:
// Let's pretend the loop ran once and it took exactly 1000ms
int lastTime=GetSystemTime()-1000;
while(true)
{
time=GetSystemTime();
// number of milliseconds the last loop took
int loopMillis = time - lastTime;
// save the value of time for the next loop
lastTime=time;
// discrepancy between the amount of time the loop ran vs. the
// amount of time it should have took
int overtime = loopMillis-1000;
doJob();
// number of milliseconds the job took
int jobMillis = GetSystemTime() - startTime;
// Sleep for 1000ms
// less the time the job took
// less the time lost in the last loop
Sleep(1000 - jobMillis - overtime);
}
I honestly thought I’d cracked it and naturally I was horrified when I ran this code and found it was still inching forward losing about a millisecond each second, meaning after about 15 minutes my clock would already be lagging behind by one second.
I took pen and paper and scrawled down some notes tracking what happened over a few loops
Loop Aimed runtime (ms) Measured runtime (ms) Discr.
--------------------------------------------------------------------
1 1000 1006 +6
2 994 997 -3
3 1003 1005 +5
4 995 996 -4
5 1004 1007 +3
6 997 999 -1
I soon saw what was wrong. In the first loop the program naively aims at running in 1000 ms, so if doJob() took 100 ms, it will Sleep() for 900 ms. At the start of the second loop, it checks the system time and subtracts the lastTime variable to get the (more or less) exact amount of time the first loop took, which was 1006 ms, meaning the first loop took 6 ms longer than we wanted. Because we’ve already gone 6 ms into the next loop’s time, we need to delay for 6ms less so the Sleep() function will run 6 ms less than it would have normally to try get our clock back on track. However in the next loop (loop number 3), the measured time for loop 2 is 997 ms, which is 3 ms more than the aimed runtime.
You see what happened? We were trying to reclaim the 6 ms lost in the first loop by running the second loop for 6 ms less, but the second loop added on 3 ms of its own, so effectively we were only able to reclaim 3 ms. It’s like loaning somebody €6 and then they pay you back €6 but immediately borrow another €3. Then they borrow €2 from you but only pay you back €1. The net effect is you’ve have €4 stolen from you, which is exactly what the above table shows. There has been 4 ms ‘stolen’ from the correct time leaving the clock behind by 4ms.
Soon after this I figured out the correct way to do it.
Loop Aimed runtime (ms) Measured runtime (ms) Discr.
--------------------------------------------------------------------
1 1000 1006 +6
2 994 997 -3
3 997 999 -1
4 998 999 -1
5 999 1002 +2
6 997 999 -1
This table is the same as the first table with one difference: In the first table each discrepancy was subtracted from the base value of 1000. In this table the base value is only used once (the first loop) and in each subsequent loop the aimed runtime floats around this base value.
After the first loop (which went 6 ms over time), the aimed runtime is reduced to 994 ms, optimistically hoping that the loop will take exactly that amount of time to run, but it doesn’t. It takes 997 ms. 1006+997=2003, so after 2 loops we’re still out by 3. The discrepancy here also happens to be 3 so we add that to 994 to get 997. We run the loop again and it takes 999 ms which gives a discrepancy (or deviation) of -1 from the ‘correct’ value of 1000. This deviation is subtracted from 997 to give 998. Adding up all the discrepancies in the first table, we get:
6 + (-3) + 5 + (-4) +3 + (-1) = 6
And in the second table, we get:
6 + (-3) + (-1) + (-1) + 2 + (-1) = 2
That means the first table is over by 6 but the second is only over by 2. A significant improvement. Take a look at the second table. See the way the aimed runtime kind of naturally reduces itself to a number 2 or 3 ms below 1000, in order to try and make the overall runtime come out at around 1000? Now take a look at the first table. The runtimes are fluctuating wildly between ~996 and ~1003, it doesn’t seem to know what it’s doing!
Here’s the improved clock code
// Let's pretend the loop ran once and it took exactly 1000ms
int lastTime=GetSystemTime()-1000;
// We desire a delay of 1000ms for the first loop but this value will fluctuate and
// on average will be slightly less than 1000 will be necessary to compensate
// for timing overheads
int necessaryDelay=1000;
while(true)
{
time=GetSystemTime();
// number of milliseconds the last loop took
int loopMillis = time - lastTime;
// save the value of time for the next loop
lastTime=time;
// discrepancy between the amount of time the loop ran vs. the
// amount of time it should have took
int overtime = loopMillis-1000;
// Adjust the delay by a bit
necessaryDelay -= overtime;
doJob();
// number of milliseconds the job took
int jobMillis = GetSystemTime() - startTime;
if (necessaryDelay-jobMillis < 1)
continue;
// Sleep for the (estimated) necessary delay time
// less the time the job took
Sleep(necessaryDelay - jobMillis);
}
This code should stay in perfect sync with your computer’s internal clock no matter how long you run it for. I even added a bit of code to protect against the Sleep() function being called with a negative parameter, instead causing the loop to continue immediately, such being the case if a particular job took longer than expected and exceeded the necessary delay.
In fact this code is tolerant to massive interruptions. Even if a particular doJob() takes a huge amount of time (like 60 seconds),or your computer is just running ultra-slow, or has been hibernating, the necessaryDelay variable will plunge into negative territory causing the continue statement to execute for the next 60 loops until the clock catches up with the system clock. Using our analog-clock analogy, it’s like the second-hand of an analog clock taking one whole minute to go from reading 13:05:10 to 13:05:11, then doing a full lap of the clock as quickly as possible until it’s caught up to the correct time of (slightly after) 13:06:10
And speaking of clocks, I’m out of time.
computersciencealgorithms 