response_time_analysis/
fixed_point.rs

1/*! Helper functions for fixed-point searches
2
3This module implements the standard iterative strategy for solving
4fixed-point equations of **monotonically increasing** functions.
5
6 */
7
8use std::cmp::Ordering;
9
10use thiserror::Error;
11
12use crate::supply::SupplyBound;
13use crate::time::{Duration, Offset, Service};
14
15#[cfg(debug_assertions)]
16use crate::time::Time;
17
18/// Error type returned when a fixed point search fails.
19#[derive(Debug, Error, Copy, Clone, Eq, PartialEq, PartialOrd)]
20pub enum SearchFailure {
21    /// No fixed point found below the given divergence threshold.
22    #[error("no fixed point less than {limit} found for offset {offset}")]
23    DivergenceLimitExceeded { offset: Offset, limit: Duration },
24
25    /// Some analysis assumption is violated.
26    #[error("analysis assumption violated")]
27    AssumptionViolated,
28}
29
30/// A fixed-point search either returns the fixed point (of type [Duration]) or
31/// a [SearchFailure] explaining why the search failed.
32pub type SearchResult = Result<Duration, SearchFailure>;
33
34/// Conduct an iterative fixed point search up to a given divergence
35/// threshold, assuming a given fixed `offset` within the busy
36/// window.
37pub fn search_with_offset<SBF, RHS>(
38    supply: &SBF,
39    offset: Offset,
40    divergence_limit: Duration,
41    workload: &RHS,
42) -> SearchResult
43where
44    SBF: SupplyBound + ?Sized,
45    RHS: Fn(Duration) -> Service,
46{
47    let mut assumed_response_time = Duration::from(1);
48    while assumed_response_time <= divergence_limit {
49        let demand = workload(assumed_response_time);
50        let demand_met = Offset::from_time_zero(supply.service_time(demand));
51        let response_time_bound = offset.distance_to(demand_met);
52        if response_time_bound <= assumed_response_time {
53            // we have converged
54            return Ok(response_time_bound);
55        } else {
56            // continue iterating
57            assumed_response_time = response_time_bound
58        }
59    }
60    // if we get here, we failed to converge => no solution
61    Err(SearchFailure::DivergenceLimitExceeded {
62        offset,
63        limit: divergence_limit,
64    })
65}
66
67/// Very slow, naive search for a fixed point up to the given
68/// `divergence_limit`, assuming a given fixed `offset` within the
69/// busy window. Do not use --- use [search_with_offset] instead.
70#[cfg(debug_assertions)]
71fn brute_force_search_with_offset<SBF, RHS>(
72    supply: &SBF,
73    offset: Offset,
74    divergence_limit: Duration,
75    workload: &RHS,
76) -> SearchResult
77where
78    SBF: SupplyBound + ?Sized,
79    RHS: Fn(Duration) -> Service,
80{
81    for r in 1..=Time::from(divergence_limit) {
82        let assumed_response_time = Duration::from(r);
83        let lhs = supply.provided_service(offset.since_time_zero() + assumed_response_time);
84        let rhs = workload(assumed_response_time);
85        // corner case: zero demand is trivially satisfied immediately
86        if rhs.is_none() {
87            return Ok(Duration::zero());
88        } else if lhs == rhs {
89            return Ok(assumed_response_time);
90        }
91    }
92    Err(SearchFailure::DivergenceLimitExceeded {
93        offset,
94        limit: divergence_limit,
95    })
96}
97
98/// Iterative search for a fixed point up to a given
99/// `divergence_limit`, assuming a given processor supply and a
100/// generic workload bound.
101pub fn search<SBF, RHS>(
102    supply: &SBF,
103    divergence_limit: Duration,
104    workload_bound: RHS,
105) -> SearchResult
106where
107    SBF: SupplyBound + ?Sized,
108    RHS: Fn(Duration) -> Service,
109{
110    let bw = search_with_offset(supply, Offset::from(0), divergence_limit, &workload_bound);
111    // In debug mode, compare against the brute-force solution, if the limit is not too large.
112    #[cfg(debug_assertions)]
113    if divergence_limit <= Duration::from(100_000) {
114        debug_assert_eq!(
115            brute_force_search_with_offset(
116                supply,
117                Offset::from(0),
118                divergence_limit,
119                &workload_bound
120            ),
121            bw
122        );
123    }
124    bw
125}
126
127/// Given a sequence of [SearchResult]s, either return the maximum
128/// finite result (if no divergence errors occurred) or propagate the
129/// first error encountered.
130///
131/// This utility function is useful when analyzing a set of offsets
132/// that must be considered as part of a response-time analysis.
133pub fn max_response_time(rta_per_offset: impl Iterator<Item = SearchResult>) -> SearchResult {
134    rta_per_offset
135        .max_by(|a, b| {
136            // propagate any errors values
137            if a.is_err() {
138                // if a is an error, we want to report it
139                Ordering::Greater
140            } else if b.is_err() {
141                // if a is not an error, but b is, then we want b
142                Ordering::Less
143            } else {
144                // if neither is an error, report the maximum result
145                a.unwrap().cmp(&b.unwrap())
146            }
147        })
148        // If we have no result at all, there are no demand steps, so the
149        // response-time is trivially zero.
150        .unwrap_or(Ok(Duration::zero()))
151}
response_time_analysis/fixed_point.rs

response_time_analysis/
fixed_point.rs
