RFC: routines for handling wrapped tick counts

[jepler]

I plan to raise this issue In the Weeds on Monday and if there is a consensus about approach I can be the implementor

Problem statement

Libraries and users need a way to manage time durations, and existing solutions are not entirely satisfactory. Thanks to @dglaude for raising this issue on Discord and github.

For consistency and portability reasons, we have only included compatible time-related functions in the standard time module. When it comes to dealing with durations and times not related to a particular epoch, this means we have

• time.monotonic(), available on all builds, which returns a floating point number of seconds that increases until the microcontroller is reset. monotonic() loses precision so that after around 18 hours, intervals of 1/64 second can no longer be distinguished; within several days, intervals of 1/8 second can no longer be distinguished
• time.monotonic_ns(), which returns an integer number of nanoseconds that increases until the microcontroller is reset. monotonic_ns() is only available on builds with long integers, because without it the count overflows in less than 2 seconds.

Multiple Adafruit bundle libraries have implemented workarounds of the general form:

if (monotonic_ns exists and is usable):
    def custom_timekeeping_function():
        implement in terms of monotonic_ns
else:
    def custom_timekeeping_function():
        implement in terms of monotonic

however, due to the problem of time.monotonic granularity, this leads to programs which have to be restarted (reset button, not soft restart) everyday or they misbehave.

Another (resolvable) problem is that due to the evolution of the core, the test (monotonic_ns exists and is usable) is different between 5.3 and 6.0, which means that at the time I write this, the adafruit_debouncer library does not work on the Trinket M0. The other workaround I know of, in adafruit_led_animation, is what I would consider the canonical workaround.

The ble_midi library uses monotonic_ns with no workaround, but we probably do not anticipate any devices that support ble but are too resource-constrained to have long ints.

I did not survey libraries that use time.monotonic only; there are a large number of them and there are probably many "misbehaves after hours/days" class bugs there, such as

adafruit_esp32spi.py:        while (time.monotonic() - times) < 0.1:

In all, 89 files in the Adafruit bundle and 14 files in the community bundle seem to use time.monotonic().

Requirements

I think we can only address this by adding new code to CircuitPython. This is a dicey proposition but right this second we do have space in our most constrained builds due to improvements in message compression, so we should be able to make it work for 6.0.

• The new APIs are not placed in a desktop Python module like time
  • microcontroller and rtc are two plausible places
  • microcontroller already has sleep_us
• work with the data type of (short) integers only
• is feasible to implement in terms of time.monotonic_ns, so it can be implemented in blinka and for backwards compatibility on long int builds
• is feasible to implement in terms of time.monotonic, without worsening the granularity problem

There is a solution, though it means giving up these two properties:

• The clock increases forever, never wrapping around
• the units of the clock are one of the python-"comptaible" units, seconds
  or nanoseconds

Proposal

Pull some select routines from micropython.utime into microcontroller, possibly choosing more expressive names:

microcontroller.ticks_ms()
microcontroller.ticks_add()
microcontroller.ticks_diff()

ticks_ms counts up, but each time it would count past a maximum value, it wraps back to zero. If you have two values from ticks_ms(), you can add them (or subtract them, by negating one):

start = ticks_ms()
wait_for_event()
end = ticks_ms
duration_ms = ticks_add(end, -start)

You can use ticks_diff to find out if you're before or after a deadline:

start = ticks_ms()
deadline = ticks_add(start, 100)
while ticks_diff(deadline, ticks_ms()) > 0:
    do_something_quick()

In practical terms, ticks_ms() will wrap every 2**29 milliseconds, which is approximately 6 days. Determining "before or after" works when the times are within half of the wrapping period, or about 3 days. When it comes to a program task like "count down to Halloween", it is not the appropriate API, and date-based functions are more appropriate. When it comes to a program task like "make the LED animation advance as close to every 1/20s as possible, forever", it is adequate indefinitely.

elaborating on some choices I made:

• the TICKS_PERIOD of 2**29 is chosen to simplify the backwards-compatibility implementation of ticks_add and ticks_diff on platforms without long ints; we can add or subtract any two numbers where the absolute values are less than TICKS_PERIOD without overflow.

• TICKS_PERIOD and other constants in the adafruit_ticks library should not be accessed and are considered implementation defined. The minimum guarantee would be that ticks wouldn't wrap around for at least 2 days, allowing differences of at least 1 day to be represented. (I can't think of a reason we'd want to do smaller than 2**29 either)

• ms is the best choice for granularity: seconds are too long, microseconds are too short, and other granularities like 1/1024s, .001s, etc., feel too arbitrary

Backwards compatible helper library: adafruit_ticks

This backwards compatible implementation is the one that shold be used (rather than directly using microcontroller.ticks_ms etc), because it will function on a range of CircuitPython versions from 5.x to 6.0 as well as on Adafruit Blinka. It makes a best effort implementation, but cannot solve the granularity problem on builds without long ints.

_MS_PER_NS = const(1000000)
_MS_PER_S = const(1000)
_TICKS_MAX = const(536870911)
_TICKS_PERIOD = const(536870912)
_TICKS_HALFPERIOD = const(268435456)

try:
    from microcontroller import ticks_ms, ticks_add, ticks_diff
    ticks_ms()
    ticks_add(0, -1)
    ticks_diff(1, 100)
except (ImportError, NotImplementedError):
    import time

    try:
        def ticks_ms():
            return (time.monotonic_ns() // MS_PER_NS) & _TICKS_MAX
        ticks_ms()
    except (NameError, NotImplementedError):
        def ticks_ms():
            return round(time.monotonic() * MS_PER_S % _TICKS_PERIOD)

    def ticks_add(ticks, delta):
        return (a + b) % _TICKS_PERIOD

    def ticks_diff(end, start):
        diff = (end - start) & _TICKS_MAX
        diff = ((diff + _TICKS_HALFPERIOD) & _TICKS_MAX) - _TICKS_HALFPERIOD
        return diff

this library could be rewritten so that the availablity of ticks_ms is considered separately from ticks_add and ticks_diff, reducing the in-core implementation footprint from 3 functions to 1

[dhalbert]

There is a LONGLONG implementation of long ints which we don't use. It is simply 64 bits of integer, not indefinite length. By itself, it is a fairly small piece of code. Unfortunately, it builds to be even larger than the regular MPZ implementation. But this is due to it dragging in double-precision float routines, which are huge and which should not be necessary. I am looking at how to prevent this, and perhaps LONGLONG could be included even in the smallest builds, which would make monotonic_ns be available for all ports.

[dhalbert]

See #3416 about whether using LONGLONG for longints for the smallest builds is practical. The answer is it only fits for the smaller translations.

[snej]

It's pretty trivial to implement basic 64-bit integer operations using (int, int) tuples as the representation. Especially for the kind of operations that are usually done on timestamps: addition, subtraction, comparison.

If you interpret those tuples as 32.32 fixed-point, you get a range of about ±60 years with sub-nanosecond precision.

[emard]

If I can vote, I prefer having montonic_ns() to be 32 or 64 bit integer
and better not having to use special ticks_add sub and or not mul mod etc
functions for integer time arithmetic. Still I'm not saying that those functions
should not exist for those who find it more comfortable.

correct:
endtime = montonic_ns() + some_time
while monotonic_ns()-endtime < 0:
pass

wrong:
while monotonic_ns() < endtime: # affected by wraparound
pass

[snej]

better not having to use special ticks_add sub and or not mul mod etc functions

Python has operator overloading. Whatever the type is, you should to be able to use +, -, <, etc. on it, that's not a problem.

[jepler]

Thanks, I appreciate all the comments.

I think that an object-based interface that has operator overloading is a fine idea for the hypothetical adafruit_ticks module coded in Python. As long as this object has some kind of "update"-like method that is called at least once per day, it can deal with overflows in whatever way is required.

An additional advantage of the Micropython API which only takes and returns ints is that it operates without allocations. This would not be true if an object instance or a tuple was returned.

An additional justification for why it is "okay" to restrict ticks to smaller timescales, and not pretend that it's suitable for general timekeeping: Especially when not on USB, the monotonic clock of a microcontroller is not particularly accurate. I measured a 240kHz nominal PWM output from a Trinket M0. When it's on USB, a frequency meter I trust measures 240.005 with the last digit varying -- but when it's not, I get about 235.900kHz with the last three digits varying. That's an error of nearly half an hour per day. Thus, even if there is no problem with wraparound, the "ticks" are not appropriate for accurately measuring intervals of 1 day to "human precision". You need a separate RTC chip for this, and a CircuitPython-adapted version of standard Python's "datetime" module for arithmetic on dates.

(This also means that if you try to use ANY API to blink a LED 24 times a minute -- or, say, to govern a 24FPS image display -- you'd get 23.5FPS, no matter how sophisticated the "ticks" API is, so in any case your program as a whole has to be able to behave gracefully when ticks collide with "real world" time)

I chose 240kHz because the Trinket M0 operates at (nominal) 48MHz, so the PWM frequency is a nice integer divisor 200 = 8*5*5. The frequency is more accurate when attached by USB because the Trinket makes its own timekeeping match the USB system's timekeeping; otherwise, it uses an inaccurate internal oscillator which is only good to within a few percent. In this case the host USB system is a Pi Zero W. Results will vary from Trinket to Trinket and from host to host. The Pi is running systemd-timesyncd, but I don't think that this affects the accuracy of its USB bus frequency.

[Breefield]

I am super in support of the inclusion of the utime ticks methods being included in some way. I actually just hit a small wall yesterday with https://github.com/micropython-IMU/micropython-fusion/blob/master/deltat.py#L53 because it relies on utime.ticks_diff. It also uses time.ticks_us() but it's trivial to convert from time.ticks_ms() to microseconds.

Following, and hopeful this could be included.