Investigate having timeout code track tick deadlines instead of deltas

[zephyrbot]

Reported by Allan Stephens:

Currently the kernel maintains a linked list of active timeouts, with each timeout recording the number of additional ticks it must wait after the preceding timeout expires. It may be more efficient for a timeout to record the absolute tick count when it expires, rather than a delta.

Potential benefits:

• k_timer_remaining_get() would no longer need to walk the list to compute how much time is left until a timer expires -- it could just subtract the current tick count from the deadline tick count.
• It should be slightly faster to handle the removal of a timeout that is stopped before it expires, since it wouldn't be necessary to adjust the delta time of the next timeout in the list (if one exists).

Potential costs:

• Unknown. It might be worth prototyping the change and seeing if it increases footprint significantly -- if so, the time vs. space trade-off would need to be analyzed.

(Imported from Jira ZEP-1332)

[carlescufi]

@andyross still relevant?

[andyross]

Technically yes. I didn't change the basic algorithm, so we have the same kind of performance behavior (i.e. computing the remaining time on a timeout is O(N) in the number of active timeouts). It would be possible to do here what we do in the scheduler and have multiple backends such that we could use a rbtree if needed for higher code size and constant factor performance but log time scaling.

Absent a real app that needs the ability to track hundreds of timeouts in flight and be able to call k_timer_remaining_get() on them (which is a pretty obscure API), though, it seems like wasted work.

And even if we did need that, with just one word of storage per timeout we could do both: compute a static/unchanging deadline AND a delta, and just return the former in O(1) time. Trivial for an app that needs it (and frankly could be done trivially in the app, too).

No opinion on this issue, really. I wouldn't object to closing it. If we leave it open I'd suggest making the priority "low".

[andyross]

Let's close this. While this is still relevant, it's been several years now and really no one has run into trouble with the existing data structure[1]. I think we can close this. When there's need, obviously, we can always revisit things and do another rework of the timer subsystem. But until then I think it's safe to say this won't be worked on.

[1] Which to remind everyone: is slightly faster for the common case of adding timeouts and firing them from ISRs, but algorithmically slower for the varous _remaining() APIs that need to know how long until a timeout expires.