Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Timer queue and time/duration overhaul #18

Open
uazu opened this issue May 2, 2021 · 0 comments
Open

Timer queue and time/duration overhaul #18

uazu opened this issue May 2, 2021 · 0 comments
Labels
enhancement New feature or request

Comments

@uazu
Copy link
Owner

uazu commented May 2, 2021

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
@uazu uazu added the enhancement New feature or request label May 2, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant