Timer queue
The timer queue contains a list of FnOnce
calls to execute at
specific instants. What we need from this queue is:
- To give us the next expiry time
- To execute items from the front of the queue when time advances
- To add and delete items
A BinaryHeap
might be good for this queue, except for the problem
of deletions being O(N). So instead for the moment a BTreeMap
is
used. The map is partitioned to split off the items to execute when
time advances. This should scale much better than a binary heap,
especially considering deletions. However a BTreeMap
generates a
lot of code, so it is likely a combined N-ary heap tuned to cache line
size and Vec
to support deletion might perform better. So the
underlying implementation will probably change at some point, once
various scenarios have been benchmarked.
Apart from fixed timers, there are also "max" and "min" timers, that can be adjusted very cheaply (just a memory write), without having to add and delete timers from the timer queue most of the time.
For fixed timers, the BTreeMap
maps a 64-bit key (32-bit wrapping
expiry time + 31-bit unique value) to a boxed FnOnce
. For min/max
timers, the 64-bit key in the map consists of a 32-bit provisional
expiry time and a 31-bit slot number. The actual current expiry time
which is updated by the calls is kept in a separate array. When the
timer expires, the current expiry time is checked, and another timer
added back in if necessary.