Crate cliff

Find the load at which a benchmark falls over.

Most good benchmarks allow you to vary the offered load to the system, and then give you output that indicate whether the system-under-test is keeping up. This could be dropped packets, latency spikes, or whatever else is appropriate for the problem domain. Now, you want to find out how far you can push your system until it falls over. How do you do that?

This crate provides one answer: exponential search. The idea is simple: first, you double offered load until the system falls over. As long as the system keeps up, you raise the lower bound of your estimate for the maximum tolerated load. When the system no longer keeps up, that gives you an upper limit on the throughput your system can support. At that point, you perform a binary search between the upper and lower bounds, tightening the range until you reach the fidelity you want.

If you instead want to search for the minimum for a given parameter, use BinaryMinSearcher. It performs a binary search for a parameter between 0 and the starting point you give. No exponential phase is needed for the min searchers, since 0 already bounds the minimum.

So that you can easily support manual override, the crate also provides LoadIterator, which implements the same interface (CliffSearch) over a pre-defined list of loads. It simply stops iteration when the test runner indicates that the system is no longer keeping up through CliffSearch::overloaded. To dynamically switch between these depending on user choices, use dyn CliffSearch.

Examples

use cliff::ExponentialCliffSearcher;

// First, we set the starting load. This is the initial lower bound.
let mut loads = ExponentialCliffSearcher::new(500);
while let Some(load) = loads.next() {
    if !benchmark(load) {
        loads.overloaded();
    }
}

let supported = loads.estimate();
println!("maximum supported load is between {} and {}", supported.start, supported.end);

Stepping through the search bit by bit:

use cliff::ExponentialCliffSearcher;

// First, we set the starting load. This is the initial lower bound.
let mut load = ExponentialCliffSearcher::new(500);
// The initial lower bound is the first load we try.
assert_eq!(load.next(), Some(500));
// Since we did not say that the system was overloaded,
// the iterator next produces twice the load of the previous step.
assert_eq!(load.next(), Some(1000));
// Same thing again.
assert_eq!(load.next(), Some(2000));
// Now, let's say the system did not keep up with the last load level:
load.overloaded();
// At this point, cliff will begin a binary search between
// 1000 (the highest supported load)
// and
// 2000 (the lowest unsupported load).
// The middle of that range is 1500, so that's what it'll try.
assert_eq!(load.next(), Some(1500));
// Let's say that succeeded.
// That means the cliff must lie between 1500 and 2000, so we try 1750:
assert_eq!(load.next(), Some(1750));
// And if that failed ...
load.overloaded();
// ... then the cliff must lie between 1500 and 1750, and so on.
// Ultimately, we reach the desired fidelity,
// which defaults to half the initial lower bound (here 250).
// At that point, no more benchmark runs are performed.
assert_eq!(load.next(), None);
// We can then ask the iterator what the final estimate is
assert_eq!(load.estimate(), 1500..1750);

Dynamically switching between search and a user-provided list:

use cliff::{ExponentialCliffSearcher, CliffSearch, LoadIterator};

let mut loads: Box<dyn CliffSearch> = if user_list.is_empty() {
    Box::new(ExponentialCliffSearcher::new(500))
} else {
    Box::new(LoadIterator::from(user_list))
};

// from here, the strategy is the same:
while let Some(load) = loads.next() {
    if !benchmark(load) {
        loads.overloaded();
    }
}

let supported = loads.estimate();
println!("maximum supported load is between {} and {}", supported.start, supported.end);

Structs

BinaryMinSearcher	An iterator that determines the minimum value of a system parameter by binary search.
ExponentialCliffSearcher	An iterator that determines the maximum supported load for a system by exponential search.
LoadIterator	An iterator that determines the maximum supported load by walking an iterator until the system cannot keep up.

Traits

CliffSearch

A class of type that can estimate the performance cliff for a system.