# One Millisecond Loop

 Previous ⇦ Algorithms Algorithms ⇫ Up Running Average ⇨ Next

## Overview

Running a loop at a precise frequency can be very useful. What is a simple and accurate way to do this on a full non-real-time OS like Ubuntu or OSX? In embedded devices where you have control over all of the resources and timer capabilities, it is fairly straightforward to do.

The following shows one technique that is quite accurate and the code is minimal.

## Git repository

git clone git@bitbucket.org:arrizza/algorithms.git

## The Loop

There are three parts to the code. The first is the initialization of the loop variables, the second is the part where you do the work you need to do every millisecond and the third is code that does a delay.

As an aside, for test purposes, I used a for() loop, but in production code it will most likely be an infinite loop e.g. for(;;) or while(true)

The initialization just takes the current time and calculates the nearest next "millisecond interval". For example if the current clock is 122,045,678 nS then the next millisecond interval is 123,000,000 nS

```      next_clock = ((get_current_clock_ns() / one_ms_in_ns) * one_ms_in_ns);
```

The call to get_current_clock_ns() gets the current clock value on your PC in nanoseconds and the rest of the formula calculates the nearest millisecond interval by truncating the nanoseconds to milliseconds. If you're willing to have a clock period of 1.024 ms then the divide and multiply operations can be replaced with right and left shifts making this calculation much faster.

The second part is encapsulated within a function:

```
on_tick();

```

For testing purposes, I used a random delay from 1 to 900 microseconds.

```std::uniform_int_distribution<> distribution(1, 900);
```

This means that you have up to 900 microseconds to get all of the work you want done in the loop.

You can play around with the upper value here to see what happens on your PC. The total amount of time spend in on_tick() has to be less than 1ms less the amount of time it takes to do the rest of the loop calculations and other operations. If it goes over, then the next tick will be shorter than 1ms by the overage.

In simple terms, if your PC is faster than mine (it probably is!) then you might be able to get even more work done since the rest of processing being done here will take less time.

Here's the simulated "your stuff here" code:

```    void on_tick()
{
// TEST only: simulate the work done in every tick
// by waiting a random amount of time
}
```

The third part calculates how much time (in nanoseconds) to wait before the next 1ms interval arrives. For example if the clock is at time 123.250 ms, then you need to wait 0.750 ms (or 750,000 ns) for the next interval at 124.000 ms.

If it turns out that the time_to_wait is negative, then the loop has already gone past the next interval and so it immediately runs on_tick() again. You can probably guess what happens if on_tick() is chronically late.

The "m_tick" variable counts the number of 1ms ticks (loops) since the loop was started.

```        // calculate the next tick time and time to wait from now until that time
time_to_wait = calc_time_to_wait();

// check if we're already past the 1ms time interval
if (time_to_wait > 0)
{
// wait that many ns
}
++m_tick;
```

The time_to_wait() function is very simple:

```
int32_t calc_time_to_wait()
{
next_clock += one_ms_in_ns;
return next_clock - get_current_clock_ns();
}
```

It simply calculates the next millisecond interval by adding 1 ms to the last interval and then calculates the difference between that time and now in nanoseconds.

## Testing and Results

The test code runs the loop 1000 times (1 second's worth of loops) and does that 20 times for a total of a 20 second run. It takes the time at various points and calculates the average time in the loop.

Typical output is:

```One Second Loops:
Avg (ns)       ms   err(ms)
[ 0]  1000085   1.0001  -0.0001
[ 1]   999759   0.9998   0.0002
[ 2]   999822   0.9998   0.0002
[ 3]   999948   0.9999   0.0001
[ 4]   999855   0.9999   0.0001
[ 5]   999726   0.9997   0.0003
[ 6]  1000100   1.0001  -0.0001
[ 7]   999800   0.9998   0.0002
[ 8]   999734   0.9997   0.0003
[ 9]  1000011   1.0000  -0.0000
[10]   999954   1.0000   0.0000
[11]   999985   1.0000   0.0000
[12]   999641   0.9996   0.0004
[13]   999813   0.9998   0.0002
[14]  1000198   1.0002  -0.0002
[15]   999778   0.9998   0.0002
[16]   999949   0.9999   0.0001
[17]   999806   0.9998   0.0002
[18]   999842   0.9998   0.0002
[19]   999838   0.9998   0.0002
Expected total time: 20.0000ms
Actual total time  : 19.9976ms
```

This shows that on average the loops were within 1 to 4 microseconds of a 1 millisecond time.

## Notes

The testing here is not 100% accurate since it is using the same timing mechanisms (my PC's crystal) for both the loop and for testing purposes. It would be a much more accurate test if there were a way to get a signal (quickly!) out of the PC and use an oscilloscope or some other tool to measure the actual timing.

The on_loop() function is using a widely ranging (from 1 to 900 microsecond) sleep to simulate very erratic loop timing. Even with that, the loop timing is very consistent!

But also note that the averages are done across 1000 loops, a lot of variance may be averaged out. It would be a better to calculate the standard deviation of all the loop times.