benchmarks.md

Benchmarks last updated for teardown_tree v0.6.6 / Rust 1.17.0-nightly.

Download the data.

To benchmark on your machine: cd rs_teardown_tree/benchmarks && cargo run --release.

TeardownTree vs other data structures

Refill/teardown

In the benchmarks below, we initialize the master copy of the data structure with N usize items, clone it and repeatedly:

1. Tear down the data structure by a random series of delete_range (or equivalent) operations.
2. Refill the copy so that its internal state is again equivalent to the master.
3. Rinse, repeat.

We measure the mean time it takes to perform the steps above with two parameters: N (the number of items in the master copy) and B (the number of items removed by a single delete_range operation). Each graph shows how much slower the given operation was on average relative to TeardownTree::delete_range() (used as baseline).

Teardown

The graphs below are based on the same data as above, except we subtract the time it takes to refill the data structure from each mean time. This allows to compare the performance of the teardown sequence separately from refill.

TeardownTree variations

We repeat the same benchmarks as above, but this time we compare 6 variations of TeardownTree::delete_range():

1. TeardownSet::delete_range(): the baseline. Each item stores a single usize value.
2. TeardownMap::delete_range(): same as above, but each item stores a key-value pair: (usize, usize)
3. TeardownSet::filter_range(): Each item stores a single usize value. The algorithm is a variation of delete_range(), modified to support filtering.
4. IntervalTeardownSet::delete_overlap(): each item stores an Interval with two usize bounds. Since we are interested in measuring the overhead of the algorithm over TeardownSet::delete_range(), both bounds are set to the same value, which makes the IntervalTeardownSet behave like a slower verison of TeardownSet.
5. IntervalTeardownMap::delete_overlap(): each item stores an Interval with two usize bounds and a usize value.
6. IntervalTeardownSet::filter_overlap(): each item stores an Interval with two usize bounds. Supports filtering.

Refill/teardown

Teardown