weir/
fixed_point_execution_plan.rs

1//! Scale-aware execution planning for Weir fixed-point analyses.
2//!
3//! This module owns scheduling policy only. It does not dispatch kernels, build
4//! graphs, mutate scratch, or own backend resources.
5
6use crate::dense_domain::{
7    plan_sparse_dense_domain, SparseDenseDomainMode, SparseDenseDomainObservation,
8    SparseDenseDomainPolicy,
9};
10use crate::fixed_point_scratch::{FrontierDensityTelemetry, FrontierExecutionMode};
11
12/// Shape and memory facts used to choose a fixed-point execution family.
13#[derive(Clone, Copy, Debug, Eq, PartialEq)]
14pub struct FixedPointExecutionPlan {
15    /// Dispatch-domain nodes.
16    pub node_count: u32,
17    /// Dispatch-domain CSR edges.
18    pub edge_count: u32,
19    /// Stable normalized graph layout hash when available.
20    pub layout_hash: u64,
21    /// Retained invariant graph bytes for the prepared plan.
22    pub retained_graph_bytes: usize,
23    /// Frontier bytes transferred per host-visible iteration.
24    pub frontier_bytes_per_iteration: usize,
25    /// Average outgoing degree in parts per million.
26    pub average_degree_ppm: u64,
27    /// Latest frontier density telemetry used by the decision.
28    pub frontier_density: FrontierDensityTelemetry,
29    /// Selected execution family for this graph and observed frontier.
30    pub execution_mode: FrontierExecutionMode,
31}
32
33impl FixedPointExecutionPlan {
34    /// Conservative bytes moved by one host-visible iteration.
35    pub fn estimated_iteration_io_bytes(self) -> Result<usize, String> {
36        self.frontier_bytes_per_iteration
37            .checked_mul(2)
38            .ok_or_else(|| {
39                "weir fixed-point iteration IO byte estimate overflowed usize. Fix: shard the graph before planning host-visible fixed-point execution."
40                    .to_string()
41            })
42    }
43
44    /// Whether repeated runs should favor resident graph resources.
45    #[must_use]
46    pub fn should_use_resident_graph(self) -> bool {
47        self.retained_graph_bytes >= 4096 || self.edge_count >= 1024 || self.node_count >= 1024
48    }
49}
50
51/// Build a scale-aware plan for an already prepared fixed-point graph.
52pub fn plan_prepared_graph(
53    graph: &crate::fixed_point_graph::FixedPointForwardGraph,
54    frontier_density: FrontierDensityTelemetry,
55) -> Result<FixedPointExecutionPlan, String> {
56    plan_from_parts(
57        graph.node_count(),
58        graph.edge_count(),
59        graph.stable_layout_hash(),
60        graph.retained_bytes(),
61        frontier_density,
62    )
63}
64
65/// Build a scale-aware plan from graph shape and retained-byte facts.
66pub fn plan_from_parts(
67    node_count: u32,
68    edge_count: u32,
69    layout_hash: u64,
70    retained_graph_bytes: usize,
71    frontier_density: FrontierDensityTelemetry,
72) -> Result<FixedPointExecutionPlan, String> {
73    let frontier_bytes_per_iteration = frontier_bytes_for_node_count(node_count)?;
74    let average_degree_ppm = if node_count == 0 {
75        0
76    } else {
77        (u64::from(edge_count) * 1_000_000) / u64::from(node_count)
78    };
79    let execution_mode = choose_execution_mode(node_count, average_degree_ppm, frontier_density);
80    Ok(FixedPointExecutionPlan {
81        node_count,
82        edge_count,
83        layout_hash,
84        retained_graph_bytes,
85        frontier_bytes_per_iteration,
86        average_degree_ppm,
87        frontier_density,
88        execution_mode,
89    })
90}
91
92fn choose_execution_mode(
93    node_count: u32,
94    average_degree_ppm: u64,
95    frontier_density: FrontierDensityTelemetry,
96) -> FrontierExecutionMode {
97    let plan = plan_sparse_dense_domain(
98        SparseDenseDomainPolicy::fixed_point_execution(),
99        SparseDenseDomainObservation {
100            domain_bits: u64::from(node_count),
101            samples: frontier_density.samples,
102            iterations: frontier_density.iterations,
103            active_bits_total: frontier_density.active_bits_total,
104            delta_bits_total: frontier_density.delta_bits_total,
105            last_active_bits: frontier_density.last_active_bits,
106            peak_active_bits: frontier_density.peak_active_bits,
107            average_degree_ppm,
108        },
109    );
110    match plan.mode {
111        SparseDenseDomainMode::Empty => FrontierExecutionMode::Empty,
112        SparseDenseDomainMode::Sparse => FrontierExecutionMode::Sparse,
113        SparseDenseDomainMode::Hybrid => FrontierExecutionMode::Hybrid,
114        SparseDenseDomainMode::Dense => FrontierExecutionMode::Dense,
115    }
116}
117
118const fn bitset_words(bits: u32) -> u64 {
119    (bits as u64).div_ceil(32)
120}
121
122fn frontier_bytes_for_node_count(node_count: u32) -> Result<usize, String> {
123    let words = usize::try_from(bitset_words(node_count)).map_err(|source| {
124        format!(
125            "weir fixed-point plan frontier word count cannot fit usize: {source}. Fix: shard the graph before planning."
126        )
127    })?;
128    words.checked_mul(std::mem::size_of::<u32>()).ok_or_else(|| {
129        "weir fixed-point plan frontier byte count overflowed usize. Fix: shard the graph before planning."
130            .to_string()
131    })
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    fn density(
139        active_total: u64,
140        delta_total: u64,
141        samples: u64,
142        iterations: u64,
143    ) -> FrontierDensityTelemetry {
144        FrontierDensityTelemetry {
145            domain_bits: 4096,
146            samples,
147            iterations,
148            active_bits_total: active_total,
149            delta_bits_total: delta_total,
150            last_active_bits: active_total / samples.max(1),
151            last_delta_bits: delta_total / iterations.max(1),
152            peak_active_bits: active_total / samples.max(1),
153            peak_delta_bits: delta_total / iterations.max(1),
154            truncated_frontier_samples: 0,
155            domain_overflow_events: 0,
156            arithmetic_overflow_events: 0,
157        }
158    }
159
160    #[test]
161    fn execution_plan_prefers_sparse_for_large_low_degree_low_delta_frontiers() {
162        let plan = plan_from_parts(4096, 4096, 7, 32768, density(8, 4, 2, 1))
163            .expect("large low-degree execution plan must fit host byte accounting");
164
165        assert_eq!(plan.frontier_bytes_per_iteration, 512);
166        assert_eq!(plan.average_degree_ppm, 1_000_000);
167        assert_eq!(plan.execution_mode, FrontierExecutionMode::Sparse);
168        assert!(plan.should_use_resident_graph());
169    }
170
171    #[test]
172    fn execution_plan_keeps_small_graphs_dense_to_avoid_scheduler_churn() {
173        let plan = plan_from_parts(128, 16, 9, 2048, density(2, 1, 2, 1))
174            .expect("small graph execution plan must fit host byte accounting");
175
176        assert_eq!(plan.frontier_bytes_per_iteration, 16);
177        assert_eq!(plan.execution_mode, FrontierExecutionMode::Dense);
178        assert!(!plan.should_use_resident_graph());
179    }
180
181    #[test]
182    fn execution_plan_uses_hybrid_for_mid_density_mid_degree_graphs() {
183        let plan = plan_from_parts(4096, 16384, 11, 65536, density(1024, 256, 2, 1))
184            .expect("mid-density execution plan must fit host byte accounting");
185
186        assert_eq!(plan.average_degree_ppm, 4_000_000);
187        assert_eq!(plan.execution_mode, FrontierExecutionMode::Hybrid);
188    }
189
190    #[test]
191    fn execution_plan_uses_exact_bitset_word_ceiling_at_u32_limit() {
192        let plan = plan_from_parts(u32::MAX, u32::MAX, 13, 0, density(1, 1, 1, 1))
193            .expect("u32-limit execution plan must fit host byte accounting");
194
195        assert_eq!(plan.frontier_bytes_per_iteration, 536_870_912);
196        assert_eq!(
197            plan.estimated_iteration_io_bytes()
198                .expect("u32 graph frontier IO estimate must fit usize"),
199            1_073_741_824
200        );
201        assert_eq!(
202            plan.average_degree_ppm,
203            (u64::from(u32::MAX) * 1_000_000) / u64::from(u32::MAX)
204        );
205    }
206
207    #[test]
208    fn execution_plan_rejects_manual_iteration_io_overflow_without_panic() {
209        let plan = FixedPointExecutionPlan {
210            node_count: 1,
211            edge_count: 0,
212            layout_hash: 0,
213            retained_graph_bytes: 0,
214            frontier_bytes_per_iteration: usize::MAX,
215            average_degree_ppm: 0,
216            frontier_density: density(0, 0, 1, 1),
217            execution_mode: FrontierExecutionMode::Dense,
218        };
219
220        let error = plan
221            .estimated_iteration_io_bytes()
222            .expect_err("manually constructed overflowing execution plans must return errors");
223
224        assert!(
225            error.contains("iteration IO byte estimate overflowed usize")
226                && error.contains("Fix: shard the graph"),
227            "overflow diagnostic must identify the byte estimate and operator action"
228        );
229    }
230
231    #[test]
232    fn execution_plan_source_has_no_planner_panic_paths() {
233        let source = include_str!("fixed_point_execution_plan.rs");
234
235        for forbidden in [
236            concat!("panic", "!("),
237            concat!(".unwrap_or_else", "(|source|"),
238            concat!(".", "unwrap()"),
239        ] {
240            assert!(
241                !source.contains(forbidden),
242                "Fix: fixed-point execution planning must return errors instead of panicking or unwrapping on release-path shape arithmetic: {forbidden}"
243            );
244        }
245    }
246}
weir/fixed_point_execution_plan.rs

weir/
fixed_point_execution_plan.rs
