gpu_async_reactor/core/
estimator.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! The deadline estimator (ADL, `reports/zav-async-dl.md` §1.2), moved from the
4//! `rw/zav-async-dl` prototype into the core unchanged in behaviour.
5//!
6//! The prediction at a readback point is the minimum of the last `window` *exact* residuals
7//! (residual = completion − wait start, observed by a poll that was already running when the
8//! work finished, so a sleep's overshoot never feeds back). A wake that finds the work already
9//! done is censored: it records `min(wake, prediction) / 2`, so a run of late wakes lowers the
10//! prediction geometrically. Early costs CPU, late costs latency: the asymmetry is the point.
11//!
12//! Invariants: pure (ns in, ns out); a sleep never exceeds the plan's `max_sleep_ns`; a late
13//! wake never raises the prediction.
14
15use alloc::collections::BTreeMap;
16
17use crate::core::plan::{DeadlinePlan, WINDOW_MAX};
18
19/// What one wait observed at its readback point.
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum Outcome {
22    /// The wait saw the work pending, then done `residual_ns` after the wait started.
23    Exact {
24        /// Completion minus wait start, ns.
25        residual_ns: u64,
26    },
27    /// The first query after the sleep found the work already done `woke_ns` after the wait
28    /// started: the true residual is at most that.
29    Late {
30        /// Wake minus wait start, ns: an upper bound on the residual.
31        woke_ns: u64,
32    },
33}
34
35/// One readback point's residual estimate (a ring of the last samples).
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37pub struct PointEstimate {
38    ring: [u64; WINDOW_MAX],
39    len: u8,
40    next: u8,
41}
42
43impl Default for PointEstimate {
44    fn default() -> Self {
45        Self::new()
46    }
47}
48
49impl PointEstimate {
50    /// No samples yet: the first wait at a point does not sleep.
51    #[must_use]
52    pub const fn new() -> Self {
53        Self {
54            ring: [0; WINDOW_MAX],
55            len: 0,
56            next: 0,
57        }
58    }
59
60    /// The predicted residual (min of the kept samples), `None` before the first.
61    #[must_use]
62    pub fn predicted_ns(&self) -> Option<u64> {
63        self.ring[..usize::from(self.len)].iter().copied().min()
64    }
65
66    /// How long to sleep from the wait's start; `None` = do not sleep.
67    #[must_use]
68    pub fn sleep_ns(&self, plan: &DeadlinePlan) -> Option<u64> {
69        let s = self.predicted_ns()?.checked_sub(plan.margin_ns)?;
70        (s >= plan.min_sleep_ns).then_some(s.min(plan.max_sleep_ns))
71    }
72
73    /// Record one wait's outcome.
74    pub fn observe(&mut self, plan: &DeadlinePlan, outcome: Outcome) {
75        let sample = match outcome {
76            Outcome::Exact { residual_ns } => residual_ns,
77            Outcome::Late { woke_ns } => woke_ns.min(self.predicted_ns().unwrap_or(woke_ns)) / 2,
78        };
79        let w = plan
80            .window
81            .clamp(1, u8::try_from(WINDOW_MAX).unwrap_or(u8::MAX));
82        if self.next >= w {
83            self.next = 0;
84        }
85        self.ring[usize::from(self.next)] = sample;
86        self.next += 1;
87        if self.len < w {
88            self.len += 1;
89        }
90    }
91}
92
93/// The estimates of every readback point a host has waited at, keyed by `K` (the
94/// host's point identity, e.g. a call site). Runtime measurement, not a decision input.
95#[derive(Clone, Debug)]
96pub struct PointTable<K> {
97    points: BTreeMap<K, PointEstimate>,
98}
99
100impl<K: Ord> Default for PointTable<K> {
101    fn default() -> Self {
102        Self::new()
103    }
104}
105
106impl<K: Ord> PointTable<K> {
107    /// No points yet.
108    #[must_use]
109    pub const fn new() -> Self {
110        Self {
111            points: BTreeMap::new(),
112        }
113    }
114
115    /// The sleep the next wait at `key` takes under `plan` (`None`: no sleep).
116    #[must_use]
117    pub fn sleep_ns(&self, key: &K, plan: &DeadlinePlan) -> Option<u64> {
118        self.points.get(key)?.sleep_ns(plan)
119    }
120
121    /// Record one wait's outcome at `key`.
122    pub fn observe(&mut self, key: K, plan: &DeadlinePlan, outcome: Outcome) {
123        self.points.entry(key).or_default().observe(plan, outcome);
124    }
125
126    /// How many points have been seen.
127    #[must_use]
128    pub fn len(&self) -> usize {
129        self.points.len()
130    }
131
132    /// No point seen yet.
133    #[must_use]
134    pub fn is_empty(&self) -> bool {
135        self.points.is_empty()
136    }
137}
138
139#[cfg(test)]
140#[path = "estimator_tests.rs"]
141mod tests;
gpu_async_reactor/core/estimator.rs

gpu_async_reactor/core/
estimator.rs
