Skip to main content

slab_wheel/
policy.rs

1//! What a wheel is allowed to decide for itself, and what the caller decides.
2
3/// Where a deadline that falls between two ticks is placed.
4///
5/// The wheel's resolution is one tick, so a deadline of 1.7 ticks has to be
6/// stored at a whole one. Which way it goes is not a detail: it decides
7/// whether a timer can fire before the caller asked for it.
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Rounding {
10    /// Never early, possibly late. A future woken before its deadline has to
11    /// check the clock and arm again, so a runtime wants this one.
12    Up,
13    /// Lowest average error, early or late. For sampling and metrics, where
14    /// the direction of the error matters less than its size.
15    Nearest,
16    /// Never late, possibly early. For enforcing a deadline, where overshoot
17    /// is the failure and a spurious wake is not.
18    Down,
19}
20
21/// How the wheel answers "what is due next" for a level it cannot read without
22/// breaking it down.
23///
24/// A coarse slot holds deadlines spanning its whole resolution, and finding
25/// the earliest means examining them. Whether that is worth doing depends
26/// entirely on the caller's access pattern.
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum CoarseQuery {
29    /// Answer from the slot's position alone: an entry in the slot at offset
30    /// `k` from the cursor cannot be due before that bucket begins.
31    ///
32    /// Constant cost and never reads an entry, at the price of naming a time
33    /// earlier than the truth, which costs the caller one wasted poll. Arming
34    /// and cancelling stay flat because neither disturbs the answer.
35    BucketBound,
36    /// Track the earliest deadline in each slot and answer with it.
37    ///
38    /// Exact, so no wasted poll. The cost lands on cancellation: withdrawing
39    /// the entry that supplied a slot's minimum invalidates it, and the next
40    /// query rebuilds that slot. A workload that arms a timeout per operation
41    /// and cancels it on completion pays this on every operation.
42    ExactMinimum,
43}
44
45/// What to do with a deadline beyond the wheel's furthest slot.
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum Overflow {
48    /// Park it in an ordered map until the wheel's reach catches up. Costs a
49    /// tree insertion for deadlines that are, by construction, rare.
50    Park,
51    /// Refuse the insertion. For callers who would rather hear about it than
52    /// discover a timer fired hours early.
53    Reject,
54}
55
56/// A wheel's shape and the decisions it makes.
57///
58/// Implemented as associated constants so a layout is fixed per wheel type and
59/// costs nothing to consult.
60pub trait Policy {
61    /// Slots per level, coarsest last. Every entry must be a power of two.
62    const SLOTS: &'static [usize];
63    /// Ticks spanned by one slot of each level. The first is always 1, and
64    /// every entry must be a power of two.
65    const RESOLUTION: &'static [u64];
66
67    /// Which way a deadline between two ticks is moved.
68    const ROUNDING: Rounding = Rounding::Up;
69    /// How much work answering "what is due next" is worth at a coarse level.
70    const COARSE_QUERY: CoarseQuery = CoarseQuery::BucketBound;
71    /// What happens to a deadline past the wheel's furthest slot.
72    const OVERFLOW: Overflow = Overflow::Park;
73}
74
75/// Milliseconds, four levels, eighteen hours of reach, and an entry that never
76/// expires before it was asked to.
77///
78/// The shape an event loop wants, and the one every figure in this crate's
79/// benchmarks was measured against. `BucketBound` in particular answers a
80/// workload that arms a timeout per operation and withdraws it on completion,
81/// where tracking exact minima turns every withdrawal into a slot rebuild.
82#[derive(Debug, Clone, Copy)]
83pub struct Millis;
84
85impl Policy for Millis {
86    const SLOTS: &'static [usize] = &[256, 64, 64, 64];
87    const RESOLUTION: &'static [u64] = &[1, 256, 16_384, 1_048_576];
88}
89
90/// Checked once when a wheel is built, so a layout that would be silently slow
91/// or silently wrong cannot produce a wheel at all.
92pub(crate) fn validate<P: Policy>() {
93    assert_eq!(
94        P::SLOTS.len(),
95        P::RESOLUTION.len(),
96        "a level needs both a slot count and a resolution"
97    );
98    assert!(!P::SLOTS.is_empty(), "a wheel needs at least one level");
99    assert_eq!(P::RESOLUTION[0], 1, "the finest level spans one tick");
100
101    for (level, (&slots, &resolution)) in P::SLOTS.iter().zip(P::RESOLUTION).enumerate() {
102        // Powers of two are not a style preference. The hot path divides by a
103        // resolution and takes a remainder by a slot count on every insertion;
104        // as powers of two those are a shift and a mask, and the layout can
105        // then be a runtime value without costing anything against constants.
106        assert!(
107            slots.is_power_of_two(),
108            "level {level} has {slots} slots, which is not a power of two"
109        );
110        assert!(
111            resolution.is_power_of_two(),
112            "level {level} spans {resolution} ticks, which is not a power of two"
113        );
114        if level > 0 {
115            // Each level must span exactly what the one below it covers, or
116            // cascading either loses deadlines or visits them twice.
117            let below = P::RESOLUTION[level - 1] * P::SLOTS[level - 1] as u64;
118            assert_eq!(
119                resolution, below,
120                "level {level} spans {resolution} ticks but the level below covers {below}"
121            );
122        }
123    }
124}