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}