deepstrike_core/benchmark/
mod.rs

1//! Deterministic workflow-scheduler regression gates from the policy-upgrade specification.
2
3use crate::orchestration::task_graph::TaskGraph;
4use crate::orchestration::workflow::{
5    DependencyPolicy, WorkflowNode, WorkflowNodeStatus, WorkflowRun, WorkflowSpec,
6};
7use crate::scheduler::policy::SchedulerPolicyConfig;
8use crate::types::agent::AgentRole;
9use crate::types::result::{LoopResult, TerminationReason};
10use crate::types::task::RuntimeTask;
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub struct CriticalPathGate {
14    pub id_order_makespan: u64,
15    pub policy_makespan: u64,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub struct LoopFairnessGate {
20    pub waiting_rounds: u64,
21}
22
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct TerminationPolicyGate {
25    pub cases_checked: usize,
26}
27
28fn result(termination: TerminationReason, loop_continue: Option<bool>) -> LoopResult {
29    LoopResult {
30        termination,
31        final_message: None,
32        turns_used: 1,
33        total_tokens_used: 0,
34        loop_continue,
35        classify_branch: None,
36        pace_decision: None,
37        tournament_winner: None,
38    }
39}
40
41fn f1_graph() -> (TaskGraph, Vec<u64>) {
42    let mut graph = TaskGraph::new();
43    let wide_a = graph.add(RuntimeTask::new("wide-a"), vec![]);
44    let wide_b = graph.add(RuntimeTask::new("wide-b"), vec![]);
45    let wide_c = graph.add(RuntimeTask::new("wide-c"), vec![]);
46    let chain_1 = graph.add(RuntimeTask::new("critical-1"), vec![]);
47    graph.add(RuntimeTask::new("wide-a-1"), vec![wide_a]);
48    graph.add(RuntimeTask::new("wide-a-2"), vec![wide_a]);
49    graph.add(RuntimeTask::new("wide-b-1"), vec![wide_b]);
50    graph.add(RuntimeTask::new("wide-b-2"), vec![wide_b]);
51    graph.add(RuntimeTask::new("wide-c-1"), vec![wide_c]);
52    graph.add(RuntimeTask::new("wide-c-2"), vec![wide_c]);
53    let chain_2 = graph.add(RuntimeTask::new("critical-2"), vec![chain_1]);
54    let chain_3 = graph.add(RuntimeTask::new("critical-3"), vec![chain_2]);
55    let chain_4 = graph.add(RuntimeTask::new("critical-4"), vec![chain_3]);
56    graph.add(RuntimeTask::new("critical-5"), vec![chain_4]);
57
58    let mut durations = vec![1; graph.len()];
59    for node in [chain_1, chain_2, chain_3, chain_4, 13] {
60        durations[node] = 4;
61    }
62    (graph, durations)
63}
64
65fn simulate_f1(policy: SchedulerPolicyConfig) -> u64 {
66    let (mut graph, durations) = f1_graph();
67    graph.configure_scheduling(policy, &[]);
68    let mut now = 0u64;
69    let mut running: Vec<(usize, u64)> = Vec::new();
70    while !graph.all_done() {
71        for node in graph.ready_tasks() {
72            if running.len() == 2 {
73                break;
74            }
75            graph.start(node);
76            running.push((node, now + durations[node]));
77        }
78        let next = running
79            .iter()
80            .map(|(_, finish)| *finish)
81            .min()
82            .expect("unfinished graph must have runnable work");
83        now = next;
84        let completed: Vec<usize> = running
85            .iter()
86            .filter_map(|(node, finish)| (*finish == now).then_some(*node))
87            .collect();
88        running.retain(|(_, finish)| *finish != now);
89        for node in completed {
90            graph.complete(node, result(TerminationReason::Completed, None));
91        }
92    }
93    now
94}
95
96/// F1: a long critical chain must beat FIFO/node-id ordering on modeled makespan.
97pub fn f1_critical_path_skew() -> CriticalPathGate {
98    let id_policy = SchedulerPolicyConfig {
99        critical_path_weight: 0,
100        fanout_weight: 0,
101        age_weight: 0,
102        token_cost_weight: 0,
103        ..SchedulerPolicyConfig::default()
104    };
105    CriticalPathGate {
106        id_order_makespan: simulate_f1(id_policy),
107        policy_makespan: simulate_f1(SchedulerPolicyConfig::default()),
108    }
109}
110
111/// F2: a 100-iteration loop gets one quantum, then yields to an already-waiting peer.
112pub fn f2_loop_fairness() -> LoopFairnessGate {
113    let spec = WorkflowSpec::new(vec![
114        WorkflowNode::new(RuntimeTask::new("loop"), AgentRole::Implement).with_loop(100),
115        WorkflowNode::new(RuntimeTask::new("peer"), AgentRole::Implement),
116    ]);
117    let mut run = WorkflowRun::new(&spec, "f2").expect("valid F2 workflow");
118    assert_eq!(run.ready_batch(), vec![0, 1]);
119    let loop_id = run.current_agent_id(0);
120    run.mark_spawned(0, &loop_id);
121    run.record_completion(&loop_id, result(TerminationReason::Completed, Some(true)));
122    let next = run.ready_batch();
123    LoopFairnessGate {
124        waiting_rounds: u64::from(next.first().copied() != Some(1)),
125    }
126}
127
128fn expected_status(
129    termination: TerminationReason,
130    policy: DependencyPolicy,
131) -> Option<WorkflowNodeStatus> {
132    match (termination, policy) {
133        (TerminationReason::Completed, _) => None,
134        (
135            TerminationReason::MaxTurns
136            | TerminationReason::TokenBudget
137            | TerminationReason::Timeout
138            | TerminationReason::MilestoneExceeded
139            | TerminationReason::ContextOverflow
140            | TerminationReason::NoProgress,
141            DependencyPolicy::AllSuccess,
142        ) => Some(WorkflowNodeStatus::SkippedUpstreamFailed),
143        (
144            TerminationReason::Error | TerminationReason::UserAbort,
145            DependencyPolicy::AllSuccess | DependencyPolicy::AcceptPartial,
146        ) => Some(WorkflowNodeStatus::SkippedUpstreamFailed),
147        _ => None,
148    }
149}
150
151/// F3: every termination class is crossed with every dependency policy. A `None` expectation means
152/// the dependent must be ready; otherwise it must close with the given terminal status.
153pub fn f3_termination_dependency_matrix() -> TerminationPolicyGate {
154    let terminations = [
155        TerminationReason::Completed,
156        TerminationReason::MaxTurns,
157        TerminationReason::Error,
158    ];
159    let policies = [
160        DependencyPolicy::AllSuccess,
161        DependencyPolicy::AcceptPartial,
162        DependencyPolicy::AllTerminal,
163        DependencyPolicy::Optional,
164    ];
165    let mut cases_checked = 0;
166    for termination in terminations {
167        for policy in policies {
168            let spec = WorkflowSpec::new(vec![
169                WorkflowNode::new(RuntimeTask::new("upstream"), AgentRole::Implement),
170                WorkflowNode::new(RuntimeTask::new("dependent"), AgentRole::Implement)
171                    .with_depends_on(vec![0])
172                    .with_dependency_policy(policy),
173            ]);
174            let mut run = WorkflowRun::new(&spec, "f3").expect("valid F3 workflow");
175            let upstream = run.current_agent_id(0);
176            run.mark_spawned(0, &upstream);
177            run.record_completion(&upstream, result(termination, None));
178            match expected_status(termination, policy) {
179                None => assert!(run.ready_batch().contains(&1)),
180                Some(status) => assert_eq!(run.node_outcomes()[1].status, status),
181            }
182            cases_checked += 1;
183        }
184    }
185    TerminationPolicyGate { cases_checked }
186}
187
188#[cfg(test)]
189mod tests {
190    use super::*;
191
192    #[test]
193    fn f1_gate_reduces_makespan() {
194        let gate = f1_critical_path_skew();
195        assert!(gate.policy_makespan < gate.id_order_makespan, "{gate:?}");
196    }
197
198    #[test]
199    fn f2_gate_bounds_peer_wait() {
200        assert_eq!(f2_loop_fairness().waiting_rounds, 0);
201    }
202
203    #[test]
204    fn f3_gate_closes_all_twelve_cases() {
205        assert_eq!(f3_termination_dependency_matrix().cases_checked, 12);
206    }
207}
deepstrike_core/benchmark/mod.rs

deepstrike_core/benchmark/
mod.rs
