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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
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>,
start: usize,
prev_min: usize,
last: Option<usize>,
fidelity: usize,
overloaded: bool,
done: bool,
fill_left: 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(),
start,
prev_min: start,
fidelity: min_width,
last: None,
overloaded: false,
done: false,
fill_left: 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()
}
/// Ensure that samples are taken just before the cliff.
///
/// If the system under test supports, say, eight million operations per second, and searches
/// starting at 1M. The searcher will first sample 1M, 2M, 4M, 8M, 16M. When it detects that
/// 16M is overloaded, it'll perform a binary search from the "right", running 12M, 10M, and 9M
/// before ultimately deciding that 8M is the lower bound for the cliff.
///
/// This evaluation is correct, but may yield strange-looking results when plotting as the
/// system is likely highly loaded at 8M. In particular, a straight line drawn from the 4M
/// sample to the 8M sample may yield a jarring visual image, and will make it hard to see what
/// happens in the system leading up to its capacity.
///
/// This method makes the searcher "fill in" extra samples to the left of the lower bound when
/// necessary. In the case above, after finding that 8M is the lower bound, this filling would
/// also sample 6M and 7M.
///
/// Filling also respects the minimum search range width if specified with [`until`].
pub fn fill_left(&mut self) {
self.fill_left = true;
}
}
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 {
if self.fill_left {
// we've found the range in which the cliff lies: self.max_in
// but the user has requested that we also "fill the curve" up to the min
// by sampling some data points leading up to the cliff as well
let diff = self.max_in.start - self.prev_min;
if diff > self.fidelity {
// now just binary search between prev_min and max_in.start
let next = self.prev_min + diff / 2;
self.prev_min = next;
return Some(next);
} else {
self.fill_left = false;
}
}
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.prev_min = self.max_in.start;
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;
// normally just None, but may be Some with filling
return self.next();
}
} 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 fill_search() {
let mut scale = ExponentialCliffSearcher::until(500, 500);
scale.fill_left();
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(), Some(4500));
scale.overloaded();
// since filling is enabled, we'll also sample a few
// points just _before_ the highest known-good target.
assert_eq!(scale.next(), Some(3000));
assert_eq!(scale.next(), Some(3500));
// and then we should be done
assert_eq!(scale.next(), None);
// check that it continues to be terminated
assert_eq!(scale.next(), None);
}
#[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);
}
#[test]
fn immediate() {
let mut scale = ExponentialCliffSearcher::new(500);
assert_eq!(scale.next(), Some(500));
scale.overloaded();
assert_eq!(scale.next(), None);
assert_eq!(scale.estimate(), 500..500);
}