1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

use super::CliffSearch;

/// An iterator that determines the maximum supported load for a system by exponential search.
///
/// See the [crate-level documentation](..) for details.
#[derive(Debug, Clone)]
pub struct ExponentialCliffSearcher {
    max_in: core::ops::Range<usize>,
    last: Option<usize>,
    fidelity: usize,
    overloaded: bool,
    done: bool,
}

impl ExponentialCliffSearcher {
    /// Perform a load search starting at `start`, and ending when the maximum load has been
    /// determined to within a range of `start / 2`.
    pub fn new(start: usize) -> Self {
        Self::until(start, start / 2)
    }

    /// Perform a load search starting at `start`, and ending when the maximum load has been
    /// determined to within a range of `min_width`.
    pub fn until(start: usize, min_width: usize) -> Self {
        Self {
            max_in: start..usize::max_value(),
            fidelity: min_width,
            last: None,
            overloaded: false,
            done: false,
        }
    }

    // NOTE: we provide inherent methods for CliffSearch so that those who do not need LoadIterator
    // do not need to think about the trait at all.

    /// Indicate that the system could not keep up with the previous load factor yielded by
    /// [`Iterator::next`].
    ///
    /// This will affect what value the next call to [`Iterator::next`] yields.
    ///
    /// This provides [`CliffSearch::overloaded`] without having to `use` the trait.
    pub fn overloaded(&mut self) {
        self.overloaded = true;
    }

    /// Give the current estimate of the maximum load the system-under-test can support.
    ///
    /// This provides [`CliffSearch::estimate`] without having to `use` the trait.
    pub fn estimate(&self) -> core::ops::Range<usize> {
        self.max_in.clone()
    }
}

impl CliffSearch for ExponentialCliffSearcher {
    fn overloaded(&mut self) {
        ExponentialCliffSearcher::overloaded(self)
    }

    fn estimate(&self) -> core::ops::Range<usize> {
        ExponentialCliffSearcher::estimate(self)
    }
}

impl Iterator for ExponentialCliffSearcher {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        if self.done {
            return None;
        }

        if let Some(ref mut last) = self.last {
            if self.overloaded {
                // the last thing we tried failed, so it sets an upper limit for max load
                self.max_in.end = *last;
                self.overloaded = false;
            } else {
                // the last thing succeeded, so that increases the lower limit
                self.max_in.start = *last;
            }

            let next = if self.max_in.end == usize::max_value() {
                // no upper limit, so exponential search
                2 * self.max_in.start
            } else {
                // bisect the range
                self.max_in.start + (self.max_in.end - self.max_in.start) / 2
            };

            // we only care about the max down to `fidelity`
            if self.max_in.end - self.max_in.start > self.fidelity {
                *last = next;
                Some(next)
            } else {
                self.done = true;
                None
            }
        } else {
            self.last = Some(self.max_in.start);
            return self.last;
        }
    }
}

#[test]
fn search_from() {
    let mut scale = ExponentialCliffSearcher::new(500);
    assert_eq!(scale.next(), Some(500));
    assert_eq!(scale.next(), Some(1000));
    assert_eq!(scale.next(), Some(2000));
    assert_eq!(scale.next(), Some(4000));
    scale.overloaded();
    assert_eq!(scale.next(), Some(3000));
    assert_eq!(scale.next(), Some(3500));
    scale.overloaded();
    assert_eq!(scale.next(), Some(3250));
    assert_eq!(scale.next(), None);
    assert_eq!(scale.estimate(), 3250..3500);

    // check that it continues to be terminated
    assert_eq!(scale.next(), None);
    // even after another "failed"
    scale.overloaded();
    assert_eq!(scale.next(), None);
    // and the estimate is still the same
    assert_eq!(scale.estimate(), 3250..3500);
}

#[test]
fn search_from_until() {
    let mut scale = ExponentialCliffSearcher::until(500, 1000);
    assert_eq!(scale.next(), Some(500));
    assert_eq!(scale.next(), Some(1000));
    assert_eq!(scale.next(), Some(2000));
    assert_eq!(scale.next(), Some(4000));
    assert_eq!(scale.next(), Some(8000));
    scale.overloaded();
    assert_eq!(scale.next(), Some(6000));
    scale.overloaded();
    assert_eq!(scale.next(), Some(5000));
    scale.overloaded();
    assert_eq!(scale.next(), None);
    assert_eq!(scale.estimate(), 4000..5000);

    // check that it continues to be terminated
    assert_eq!(scale.next(), None);
    // even after another "failed"
    scale.overloaded();
    assert_eq!(scale.next(), None);
    // and the estimate is still the same
    assert_eq!(scale.estimate(), 4000..5000);
}

#[test]
fn through_trait() {
    let mut scale = ExponentialCliffSearcher::until(500, 1000);
    let scale: &mut dyn CliffSearch = &mut scale;
    assert_eq!(scale.next(), Some(500));
    assert_eq!(scale.next(), Some(1000));
    assert_eq!(scale.next(), Some(2000));
    assert_eq!(scale.next(), Some(4000));
    assert_eq!(scale.next(), Some(8000));
    scale.overloaded();
    assert_eq!(scale.next(), Some(6000));
    scale.overloaded();
    assert_eq!(scale.next(), Some(5000));
    scale.overloaded();
    assert_eq!(scale.next(), None);
    assert_eq!(scale.estimate(), 4000..5000);
}