You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Timers currently use a BtreeMap which is theoretically efficient at scale, especially when there are thousands of timers, or when the thread is heavily overloaded. However a BtreeMap generates a lot of code, and is probably overkill. It would be better to have something tuned to this application. So these changes are proposed:
New type MonoTime (for monotonic time) which is time since base Instant as a u64 in ns, allowing Stakker to run for 500+ years at a time. Support most things that Instant does. Conversion to/from Instant is supported via a Core reference to get the base time. Support creation directly from a time in ns to support virtual time without reference to an Instant
New type MonoDur for monotonic duration as a u64 in ns. Support easy conversion from f64 in seconds. Support most things that Duration does, and conversion to/from Duration
Switch all times and durations in API to use these types (or Into<...> these types), i.e. so Stakker can work purely with these types internally
Create timer benchmarks (based on estimated realistic distribution of timers at various scales) and run against the current BtreeMap implementation
Rewrite timer queue as a N-ary heap with an associated slab-style array to support deletion, and benchmark to check that this is an improvement
This will be a breaking API change, so it will mean going to 0.3. However API changes will be kept to a minimum and where code uses type inference it might not even notice. Justifications for design decisions:
Instant is problematic because the representation is different on different platforms, and calculations may be relatively heavy (e.g. macOS). Also, there's no way to construct an Instant zero. You always have to work relative to 'now' even if you're working in virtual time. Also secs/ns time in Duration is inconvenient to calculate with.
Using ns time is easy to calculate with (add/sub). Current Stakker timer code internally uses a compromise time representation with discontinuities.
Converting secs/ns to ns is just a mul and add (fast).
Converting back from ns to secs/ns (as used by Instant and Duration) requires a divide and modulus which is slow, but there shouldn't be much need to convert back within the Stakker system. Just maybe on the edges
Encouraging const conversion of f64 to MonoDur means easy representation of durations in the code, which are converted to ns at compile-time
N-ary heap can be optimised to cache line size. It will produce a shallow tree. It should perform well for single timer fetches. It doesn't support partition to grab a whole chunk of timers like BtreeMap does. However the code will be many times smaller.
Weak point of heap is O(N) deletion, which is worked around by having a slab-like vec associated with it where the callbacks are stored, where deletion can occur
The text was updated successfully, but these errors were encountered:
Timers currently use a BtreeMap which is theoretically efficient at scale, especially when there are thousands of timers, or when the thread is heavily overloaded. However a BtreeMap generates a lot of code, and is probably overkill. It would be better to have something tuned to this application. So these changes are proposed:
MonoTime
(for monotonic time) which is time since baseInstant
as au64
in ns, allowing Stakker to run for 500+ years at a time. Support most things thatInstant
does. Conversion to/fromInstant
is supported via a Core reference to get the base time. Support creation directly from a time in ns to support virtual time without reference to anInstant
MonoDur
for monotonic duration as au64
in ns. Support easy conversion fromf64
in seconds. Support most things thatDuration
does, and conversion to/fromDuration
This will be a breaking API change, so it will mean going to 0.3. However API changes will be kept to a minimum and where code uses type inference it might not even notice. Justifications for design decisions:
Instant
is problematic because the representation is different on different platforms, and calculations may be relatively heavy (e.g. macOS). Also, there's no way to construct anInstant
zero. You always have to work relative to 'now' even if you're working in virtual time. Also secs/ns time inDuration
is inconvenient to calculate with.f64
toMonoDur
means easy representation of durations in the code, which are converted to ns at compile-timeThe text was updated successfully, but these errors were encountered: