16 October 2020

Have you ever written code like this?

while true
    do_something()
    sleep(PERIOD)
end

(This article uses scripting-like pseudo-code.) You’re trying to run a function every PERIOD milliseconds, i.e. at a rate of RATE = 1 / PERIOD hertz. This method is simple and usually adequate, but it is not accurate. It doesn’t take into account two things:

  1. the time do_something takes to execute
  2. inaccuracies in sleep; lots of sleep functions only guarantee they will sleep for at least the specified time.

One way to resolve (1) would be to record how much time do_something takes and subtract it from the sleep duration.

while true
    before = time()
    do_something()
    duration = time() - before

    if duration > 0
        sleep(PERIOD - duration)
    end
end

But in addition to not solving (2), it raises some further concerns:

  1. If sleep has lower precision than time, and duration is close to PERIOD, we might do sleep(0) and run too fast.
  2. If sometimes duration > PERIOD, we will sleep(0) but forget our remaining “sleep debt” next loop, and run too fast.

These concerns became a problem when I was developing a CPU emulator, as I had to find a way of running code very accurately at a certain average rate. What I came up with is this. I call it the “stretchy sleep.”

lasttime = time()
credit = 0

while true
    target = 0

    if credit > 0
        sleep(credit)
        target += credit
        credit = 0
    end

    do_something()
    target += DESIRED_TIME

    newtime = time()
    credit += target - (newtime - lasttime)
    lasttime = newtime
end

It works via a simple time budgeting system which has memory between loops. During a loop, you set target to the amount of time you want the current run of the loop to take. The difference between this target and the recorded time is recorded in the variable credit. When the credit is positive, it is “paid off” by sleeping, with the intended sleep time again added to the target. (Adding the intended sleep time to the budget allows for averaging out any inaccuracies or imprecision in sleep.)

The result is basically a flexible, self-correcting timing system which runs at a specified average rate, and is accurate up to that of the time function.

As a final note, this loop above isn’t suited to all needs for periodic code, just ones where overall average rate is important. For example, when re-drawing a screen at 30 FPS, consistency is most important to the viewer. The way credit is adjusted can be modified to account for different requirements, or in some cases other timing mechanisms will be more appropriate.