What combination of resolution and precision should we support for representation of time

[erlingrj]

@arengarajan99 and I had a little discussion about how time should be represented in reactor-c. Lets make that discussion public here and reach a conclusion.

There are 2 options:

1) Keep a single way of representing time. 64bit signed integers representing nanoseconds since program start (or since 1970 to match UTC).

• It keeps code complexity low
• We don't have to consider integer overflow (in our lifetimes)

2) Allow different platforms to have different representations. E.g. microseconds and 32 bit signed.

• It is more efficient for resource constraint platforms. Especially the older Arduinos which are 8bit

[erlingrj]

My position is that we should do (1) because there is a lot of subtleties introduced when we move from a monotonically increasing clock to a wrapping clock.

1) There will be a limit to the interval between two events. E.g. doing MINUTES(36) with 32bit+us will yield -35minutes currently. We can increase to 71minutes by using unsigned. 2) If using unsigned we will be able to represent a greater range of instant_t's but not the interval_t from now till all those instant_t. Because interval_t has to be signed. 3) If using unsigned we will no longer have a NEVER tag (it is now set to -INT32_MAX) 4) Regardless of using signed or unsigned we no longer have a FOREVER tag. This is set to INT64_MAX. We cannot do this when we expect an overflow. This will e.g. cause shutdown to be trigger at overflow.

To support lower precision we should really make a timing library to make sure that we handle overflows properly. We will have to add a bit to each timestamp to signal if this is a FOREVER timestamp and thus greater than all other timestamps. Each time we want to compute the interval between 2 timestamps we will have to figure out which timestamp is greater than the other, this might be known from the context or we will have to assume that it is the "least distance" between the timestamp.

The question is if the performance argument for using lower precision is strong enough. For 8bit microcontrollers it is a strong argument, but they are rare and there are, to my knowledge, no new 8 bit MCUs being designed. I think it is reasonable to sacrifice performance for a few outdated Arduinos to keep code complexity as low as possible and avoid hard-to-debug timing bugs.

[arengarajan99]

Adding additional information to the discussion:

Arduino in itself is designed with the idea of 32 bit timing standards in mind: the micros() internal timer that arduino uses internally is 32-bit by design since a standard use case of Arduino timers do not involve long running programs (programs that do run long term utilize the loop() functionality to run infinitely which we abstracted away as a part of our original design).

In its current state, the infrastructure needed to support 64 bit timing on arduino is not present. The only variable standard that can be used to mitigate this effect is long long with another library support. Though this seems ideal, we run into the following set of issues:

1. Since the internal timer we check against for arduino is by default a 32 bit timer, we must account for overflows (which Erling has already brought up above) and modification of our time instant to account for this discrepancy.
2. Even with this long long support, we still sacrifice efficiency since avr-gcc (the compiler used for Arduino programs) does its operations on a per byte basis. Extending the timer to 64 bit will in fact take twice as long to update as 32 bit (which is a point to bring up in terms of the tradeoffs).
3. If there ever comes a time in the future where we have an embedded platform that only supports 32-bit, it may be important to have a certain level of flexibility in reactor-c rather than hoping for long long support on the new platform.

I do tend to agree with Erling that it would be a lot more ideal to keep 64 bit as the universal standard rather than reworking all of reactor-c to make 32 bit timers feasible, but I would like other's thoughts on the matter as well.

[erlingrj]

1. Since the internal timer we check against for arduino is by default a 32 bit timer, we must account for overflows (which Erling has already brought up above) and modification of our time instant to account for this discrepancy.

This is true. But we would only need to handle overflow in one single place (lf_clock_gettime) vs every single time some arithmetic is done on instant_t or interval_t (which happens all over). Also safely handling these overflows is subtle, but doable. It is done in the nRF port.

2. Even with this long long support, we still sacrifice efficiency since avr-gcc (the compiler used for Arduino programs) does its operations on a per byte basis. Extending the timer to 64 bit will in fact take twice as long to update as 32 bit (which is a point to bring up in terms of the tradeoffs).

This I think is the main point against using 64 bit. But how significant is the overhead? How big percentage of execution time is spent calculating times? Actually I have no idea and we should benchmark it. Also consider finding the interval between two timestamps t1 and t2, i.e. t2-t1. Remember that this could be a positive or negative interval.

int8_t diff(int8_t t1, int8_t t2) {
  int8_t delta = t2 - t1;

  if (delta < -INT8_MAX/2 || delta > INT8_MAX/2) {
    delta = t1 - t2;
   }
   return delta;
}

And here I didn't even check if one of them was FOREVER. To represent forever I guess we would represent time as a struct with an additional byte telling whether it is FOREVER or not. Maybe there are better approaches.

Anyways, it seems to me that there will be as much overhead because we need to handle the overflows now.

3. If there ever comes a time in the future where we have an embedded platform that only supports 32-bit, it may be important to have a certain level of flexibility in reactor-c rather than hoping for long long support on the new platform.

I dont think that is likely. That would be some ancient or esoteric HW with its custom compiler. 64bit integers are in the C standard.

I do tend to agree with Erling that it would be a lot more ideal to keep 64 bit as the universal standard rather than reworking all of reactor-c to make 32 bit timers feasible, but I would like other's thoughts on the matter as well.

Agreed, I am definitely not seeing the whole picture. And I have a bias in that I have only worked with certain HW platforms where this would not be a big problem.

[edwardalee]

I think it is important to keep clear the difference between logical time and physical time. The nRF port shows clearly that there is no particular difficulty with handling 32-bit representation in timers measuring physical time (with appropriate handling of overflow) while preserving 64-bit representations for logical time and for the users view of physical time. There is a performance cost, but we should measure that before concluding it is onerous.

[erlingrj]

What is a good way to measure this? Of top of my head I can imagine doing the following:

1. Find a "representative" test program (or maybe a couple).
2. Record 4 timestamps: (t1) Time right before sleeping. (t2) Time right after waking up from sleep. (t3) Time right before any reaction invocation (t4) time right after the reaction invocation.
3. Now we can compute the "runtime overhead" as 1 - (t2-t1)/(t4-t3)

This would be an estimate of the time spent doing any calculation besides reaction bodies. If we measure that with 32 bit and 64 bit time representation we can get a feel of the additional overhead. I wanna note that our current 32 bit implementation is not really the "baseline" as it is unsafe wrt overflows when adding and subtracting timestamps. But still it would reveal how much time is spent doing timestamp arithmetic.

Does anyone have any comment on this approach? Or suggestions for what a representative test program would be? Maybe something from the benchmark suite?

[lhstrh]

This sounds like a very useful experiment to me.

[erlingrj]

Had a brief talk with @edwardalee about this yesterday, and I think our conclusion was the following.

1. 64 bit signed integer with nanosecond resolution should be the default for all platforms. I don't yet know of any platform where this is impossible (due to lack of compiler support for 64 bit integers).
2. Using different precision and resolution would require abstracting all time arithmetic behind a library that safely handles all corner cases with overflow as well as the NEVER and FOREVER tag.

(2) is definitely possible, but it requires careful thought and design. We should not start that task until we know that it is necessary for platforms that we want to support. So to conclude:

We should start by making 64 bit nanosecond support default for all targets, including Arduino. I think that this should be merged in together with the lock-time branch as soon as possible. From there we can explore the design of a timing library to achieve 32 bit precision, but that should be preceded by benchmarking showing that it is necessary.

@edwardalee would you agree with this?

[edwardalee]

I agree, except that I think the lock-time branch has already been merged.

Edward

---

Edward A Lee Professor UC Berkeley

On Sep 27, 2022, at 9:32 AM, erling @.***> wrote:

 Had a brief talk with @edwardalee about this yesterday, and I think our conclusion was the following.

64 bit signed integer with nanosecond resolution should be the default for all platforms. I don't yet know of any platform where this is impossible (due to lack of compiler support for 64 bit integers). Using different precision and resolution would require abstracting all time arithmetic behind a library that safely handles all corner cases with overflow as well as the NEVER and FOREVER tag. (2) is definitely possible, but it requires careful thought and design. We should not start that task until we know that it is necessary for platforms that we want to support. So to conclude:

We should start by making 64 bit nanosecond support default for all targets, including Arduino. I think that this should be merged in together with the lock-time branch as soon as possible. From there we can explore the design of a timing library to achieve 32 bit precision, but that should be preceded by benchmarking showing that it is necessary.

@edwardalee would you agree with this?

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.

[lhstrh]

It hasn't yet been merged, see #106.

[erlingrj]

@arengarajan99 What do you think about this? I previously had a look at how to achieve this for Arduino based in the nrf52 work and I have put it here, it is branched out from the lock-time branch. Do you wanna take the lead on finalizing this and getting it merged into lock-time? I would be happy to contribute or review it.

[arengarajan99]

Thanks for this @erlingrj, I have local changes that I can port over to this branch. I will need to tweak a few things to work with Arduino-CMake but we can definitely get a proof of concept going.