| 1 |
use criterion::{black_box, criterion_group, criterion_main, Bencher, BenchmarkId, Criterion}; |
| 2 |
use itertools::Itertools; |
| 3 |
use rand::{rngs::StdRng, seq::SliceRandom, SeedableRng}; |
| 4 |
|
| 5 |
fn strict(b: &mut Bencher, (k, vals): &(usize, &Vec<usize>)) { |
| 6 |
b.iter(|| black_box(vals.iter()).k_smallest(*k)) |
| 7 |
} |
| 8 |
|
| 9 |
fn relaxed(b: &mut Bencher, (k, vals): &(usize, &Vec<usize>)) { |
| 10 |
b.iter(|| black_box(vals.iter()).k_smallest_relaxed(*k)) |
| 11 |
} |
| 12 |
|
| 13 |
fn ascending(n: usize) -> Vec<usize> { |
| 14 |
(0..n).collect() |
| 15 |
} |
| 16 |
|
| 17 |
fn random(n: usize) -> Vec<usize> { |
| 18 |
let mut vals = (0..n).collect_vec(); |
| 19 |
vals.shuffle(&mut StdRng::seed_from_u64(42)); |
| 20 |
vals |
| 21 |
} |
| 22 |
|
| 23 |
fn descending(n: usize) -> Vec<usize> { |
| 24 |
(0..n).rev().collect() |
| 25 |
} |
| 26 |
|
| 27 |
fn k_smallest(c: &mut Criterion, order: &str, vals: fn(usize) -> Vec<usize>) { |
| 28 |
let mut g = c.benchmark_group(format!("k-smallest/{order}")); |
| 29 |
|
| 30 |
for log_n in 20..23 { |
| 31 |
let n = 1 << log_n; |
| 32 |
|
| 33 |
let vals = vals(n); |
| 34 |
|
| 35 |
for log_k in 7..10 { |
| 36 |
let k = 1 << log_k; |
| 37 |
|
| 38 |
let params = format!("{log_n}/{log_k}"); |
| 39 |
let input = (k, &vals); |
| 40 |
g.bench_with_input(BenchmarkId::new("strict", ¶ms), &input, strict); |
| 41 |
g.bench_with_input(BenchmarkId::new("relaxed", ¶ms), &input, relaxed); |
| 42 |
} |
| 43 |
} |
| 44 |
|
| 45 |
g.finish() |
| 46 |
} |
| 47 |
|
| 48 |
fn k_smallest_asc(c: &mut Criterion) { |
| 49 |
k_smallest(c, "asc", ascending); |
| 50 |
} |
| 51 |
|
| 52 |
fn k_smallest_rand(c: &mut Criterion) { |
| 53 |
k_smallest(c, "rand", random); |
| 54 |
} |
| 55 |
|
| 56 |
fn k_smallest_desc(c: &mut Criterion) { |
| 57 |
k_smallest(c, "desc", descending); |
| 58 |
} |
| 59 |
|
| 60 |
criterion_group!(benches, k_smallest_asc, k_smallest_rand, k_smallest_desc); |
| 61 |
criterion_main!(benches); |