slab-wheel 0.0.1

A hierarchical timing wheel with stable handles and configurable rounding, layout and lookup policy
Documentation
  • Coverage
  • 100%
    20 out of 20 items documented1 out of 1 items with examples
  • Size
  • Source code size: 109.8 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 440.1 kB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 2s Average build duration of successful builds.
  • all releases: 2s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • slipstreamhq/slab-wheel
    0 0 0
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • dahankzter

slab-wheel

A hierarchical timing wheel with stable handles, for schedulers that have to cancel far more often than they fire.

use std::time::{Duration, Instant};
use slab_wheel::{Millis, TimingWheel};

let start = Instant::now();
let mut wheel: TimingWheel<&str, Millis> = TimingWheel::starting_at(start);

let key = wheel.insert(start + Duration::from_millis(50), "read timeout");

// Nothing is due yet, and the wheel says when to come back.
wheel.advance_to(start + Duration::from_millis(10));
let mut due = Vec::new();
wheel.drain_expired_into(&mut due);
assert!(due.is_empty());
assert!(wheel.next_expiry().unwrap() <= start + Duration::from_millis(50));

// The read completed, so withdraw the timeout before it fires.
assert_eq!(wheel.remove(key), Some("read timeout"));
assert!(wheel.is_empty());

What it is for

The workload this is shaped around is a timeout armed per operation and withdrawn when the operation completes, so most entries are cancelled and few ever expire. An ordered map handles that at O(log n) with two structures to keep in step; this handles it at a flat cost with one.

Entries live in a slab and the wheel's slots hold indices into it. Cascading moves four-byte indices rather than whole entries, and a handle stays valid for an entry's whole life however many times it moves between slots, which is what makes cancellation an array index rather than a lookup.

It never reads the clock

advance_to is told what time it is. The whole structure is therefore testable without waiting, and a caller with its own time source can drive it. The property tests run two hundred randomized seeds in a tenth of a second for exactly this reason.

The contract

A caller sleeps on next_expiry with no clock behind it, so the answer may name a time earlier than the truth but never a later one. Waking early costs a wasted poll; waking late is a missed deadline.

Whether an entry can expire early is a separate question, and it is the caller's to answer:

Rounding guarantee for
Up never early, may be late runtimes, where waking a future early means it re-arms
Down never late, may be early deadline enforcement, where overshoot is the failure
Nearest within half a tick either way sampling and metrics

The one trade worth understanding

CoarseQuery decides how a level too coarse to read directly answers "what is due next".

BucketBound answers from the slot's position alone: nothing in the slot at offset k from the cursor can be due before that bucket begins. Constant cost, never reads an entry, may name a time early.

ExactMinimum tracks the earliest deadline per slot and answers with it. Exact, so no wasted poll.

Measured separately, ExactMinimum wins the query: 11.5ns against 13.4ns. That is not the case that matters. Cancelling the entry that supplied a slot's minimum invalidates it, and the next query rebuilds the slot, so a caller doing both continuously pays for it:

entries in one slot BucketBound ExactMinimum
64 17.1 ns 39.1 ns
512 16.1 ns 221.0 ns
4,096 15.9 ns 1.55 µs

At a million it does not finish. BucketBound is the default because arming and cancelling is the workload; choose ExactMinimum if you query far more than you cancel.

Configuring the layout

Slot counts and resolutions must be powers of two. That is not a style rule: they are stored as a shift and a mask, so a runtime-configurable layout costs nothing against compiled-in constants. A layout that would be silently slow, or whose levels do not tile exactly, is rejected when the wheel is built.

use slab_wheel::{Policy, Rounding, TimingWheel};

struct Coarse;
impl Policy for Coarse {
    const SLOTS: &'static [usize] = &[64, 64, 64];
    const RESOLUTION: &'static [u64] = &[1, 64, 4_096];
    const ROUNDING: Rounding = Rounding::Down;
}

// Building the wheel is what checks the layout: each level here spans
// exactly what the one below it covers, 64 x 1 and then 64 x 64.
let wheel: TimingWheel<(), Coarse> = TimingWheel::new();
assert!(wheel.is_empty());

Cost

Criterion, one machine, entries sharing a slot:

insert                  12.4 -> 9.9 -> 9.9 -> 12.3 ns    at 64 .. 1M
cancel_earliest_first    4.1 -> 3.6 -> 3.7 ->  4.0 ns    at 64 .. 1M
next_expiry             13.4 ns flat
idle_gap                  50 ns at 1ms and at 600s

Insertion and cancellation do not care what shape the wheel is, but asking what is due next does, because it consults every level:

                        levels   next_expiry
  one level                  1       5.2 ns
  reactor layout             4      13.2 ns
  eight narrow levels        8      20.5 ns
  two levels, 1024 slots     2      20.7 ns

Depth costs about two nanoseconds a level. Width costs too, at the far end: two levels of a thousand slots search as long as eight levels of two, because the occupancy mask is sixteen words instead of one.

Rounding is very nearly free, 10.8 ns against 11.4 ns, the difference being that rounding up divides with a ceiling. Refusing overflow rather than parking it costs 2.2 ns an insertion, for the check itself.

Flat is the claim. The absolute figures are a sanity check and nothing more until a real caller is driving it.

What this does not do yet

No integrated measurement against a real runtime, which is the number that would actually justify it. No no_std. Timing is in whole milliseconds. The wheel is single-threaded by construction and holds no locks.

Licence

MIT or Apache-2.0, at your option.