use std::hint::black_box;
use std::time::Duration;
use std::vec::Vec;
use cap_vec::CapVec;
use criterion::{BatchSize, BenchmarkId, Criterion, criterion_group, criterion_main};
const CAP: usize = 512;
struct Benchmark {
name: &'static str,
cap_vec: fn() -> usize,
vec: fn() -> usize,
}
fn bench_vec_compare(c: &mut Criterion) {
let mut group = c.benchmark_group(format!("vec_compare/capacity_{CAP}"));
for benchmark in construction_benchmarks() {
group.bench_function(BenchmarkId::new(benchmark.name, "CapVec"), |b| {
b.iter(|| black_box((benchmark.cap_vec)()))
});
group.bench_function(BenchmarkId::new(benchmark.name, "Vec"), |b| {
b.iter(|| black_box((benchmark.vec)()))
});
}
group.bench_function(
BenchmarkId::new("swap_remove_middle_until_empty", "CapVec"),
|b| {
b.iter_batched(
cap_vec_filled,
|values| black_box(cap_vec_swap_remove_middle_until_empty(values)),
BatchSize::SmallInput,
)
},
);
group.bench_function(
BenchmarkId::new("swap_remove_middle_until_empty", "Vec"),
|b| {
b.iter_batched(
vec_filled,
|values| black_box(vec_swap_remove_middle_until_empty(values)),
BatchSize::SmallInput,
)
},
);
group.bench_function(BenchmarkId::new("truncate_half", "CapVec"), |b| {
b.iter_batched(
cap_vec_filled,
|values| black_box(cap_vec_truncate_half(values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("truncate_half", "Vec"), |b| {
b.iter_batched(
vec_filled,
|values| black_box(vec_truncate_half(values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("drain_middle", "CapVec"), |b| {
b.iter_batched(
cap_vec_filled,
|values| black_box(cap_vec_drain_middle(values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("drain_middle", "Vec"), |b| {
b.iter_batched(
vec_filled,
|values| black_box(vec_drain_middle(values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("iter_sum", "CapVec"), |b| {
b.iter_batched(
cap_vec_filled,
|values| black_box(cap_vec_iter_sum(&values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("iter_sum", "Vec"), |b| {
b.iter_batched(
vec_filled,
|values| black_box(vec_iter_sum(&values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("into_iter_sum", "CapVec"), |b| {
b.iter_batched(
cap_vec_filled,
|values| black_box(cap_vec_into_iter_sum(values)),
BatchSize::SmallInput,
)
});
group.bench_function(BenchmarkId::new("into_iter_sum", "Vec"), |b| {
b.iter_batched(
vec_filled,
|values| black_box(vec_into_iter_sum(values)),
BatchSize::SmallInput,
)
});
group.finish();
}
fn construction_benchmarks() -> [Benchmark; 5] {
[
Benchmark {
name: "push",
cap_vec: cap_vec_push,
vec: vec_push,
},
Benchmark {
name: "extend",
cap_vec: cap_vec_extend,
vec: vec_extend,
},
Benchmark {
name: "push_then_pop",
cap_vec: cap_vec_push_then_pop,
vec: vec_push_then_pop,
},
Benchmark {
name: "insert_front_then_remove_front",
cap_vec: cap_vec_insert_front_then_remove_front,
vec: vec_insert_front_then_remove_front,
},
Benchmark {
name: "insert_middle_then_remove_middle",
cap_vec: cap_vec_insert_middle_then_remove_middle,
vec: vec_insert_middle_then_remove_middle,
},
]
}
fn cap_vec_filled() -> CapVec<usize, CAP> {
let mut values = CapVec::<usize, CAP>::new();
values.extend(0..CAP);
values
}
fn vec_filled() -> Vec<usize> {
let mut values = Vec::with_capacity(CAP);
values.extend(0..CAP);
values
}
fn cap_vec_push() -> usize {
let mut values = CapVec::<usize, CAP>::new();
for value in 0..CAP {
values.push(black_box(value)).unwrap();
}
black_box(values.iter().sum::<usize>() + values.len())
}
fn vec_push() -> usize {
let mut values = Vec::with_capacity(CAP);
for value in 0..CAP {
values.push(black_box(value));
}
black_box(values.iter().sum::<usize>() + values.len())
}
fn cap_vec_extend() -> usize {
let mut values = CapVec::<usize, CAP>::new();
let mut leftover = values.extend(0..CAP);
black_box(leftover.next());
black_box(values.iter().sum::<usize>() + values.len())
}
fn vec_extend() -> usize {
let mut values = Vec::with_capacity(CAP);
values.extend(0..CAP);
black_box(values.iter().sum::<usize>() + values.len())
}
fn cap_vec_push_then_pop() -> usize {
let mut values = CapVec::<usize, CAP>::new();
for value in 0..CAP {
values.push(value).unwrap();
}
let mut sum = 0;
while let Some(value) = values.pop() {
sum += black_box(value);
}
black_box(sum)
}
fn vec_push_then_pop() -> usize {
let mut values = Vec::with_capacity(CAP);
for value in 0..CAP {
values.push(value);
}
let mut sum = 0;
while let Some(value) = values.pop() {
sum += black_box(value);
}
black_box(sum)
}
fn cap_vec_insert_front_then_remove_front() -> usize {
let mut values = CapVec::<usize, CAP>::new();
for value in 0..CAP {
values.insert(0, black_box(value)).unwrap();
}
let mut sum = 0;
while let Some(value) = values.remove(0) {
sum += black_box(value);
}
black_box(sum)
}
fn vec_insert_front_then_remove_front() -> usize {
let mut values = Vec::with_capacity(CAP);
for value in 0..CAP {
values.insert(0, black_box(value));
}
let mut sum = 0;
while !values.is_empty() {
sum += black_box(values.remove(0));
}
black_box(sum)
}
fn cap_vec_insert_middle_then_remove_middle() -> usize {
let mut values = CapVec::<usize, CAP>::new();
for value in 0..CAP {
values.insert(values.len() / 2, black_box(value)).unwrap();
}
let mut sum = 0;
while !values.is_empty() {
sum += black_box(values.remove(values.len() / 2).unwrap());
}
black_box(sum)
}
fn vec_insert_middle_then_remove_middle() -> usize {
let mut values = Vec::with_capacity(CAP);
for value in 0..CAP {
values.insert(values.len() / 2, black_box(value));
}
let mut sum = 0;
while !values.is_empty() {
sum += black_box(values.remove(values.len() / 2));
}
black_box(sum)
}
fn cap_vec_swap_remove_middle_until_empty(mut values: CapVec<usize, CAP>) -> usize {
let mut sum = 0;
while !values.is_empty() {
sum += black_box(values.swap_remove(values.len() / 2).unwrap());
}
black_box(sum)
}
fn vec_swap_remove_middle_until_empty(mut values: Vec<usize>) -> usize {
let mut sum = 0;
while !values.is_empty() {
sum += black_box(values.swap_remove(values.len() / 2));
}
black_box(sum)
}
fn cap_vec_truncate_half(mut values: CapVec<usize, CAP>) -> usize {
values.truncate(CAP / 2);
black_box(values.iter().sum::<usize>() + values.len())
}
fn vec_truncate_half(mut values: Vec<usize>) -> usize {
values.truncate(CAP / 2);
black_box(values.iter().sum::<usize>() + values.len())
}
fn cap_vec_drain_middle(mut values: CapVec<usize, CAP>) -> usize {
let sum = values
.drain(CAP / 4..CAP * 3 / 4)
.fold(0, |acc, value| acc + black_box(value));
black_box(sum + values.len())
}
fn vec_drain_middle(mut values: Vec<usize>) -> usize {
let sum = values
.drain(CAP / 4..CAP * 3 / 4)
.fold(0, |acc, value| acc + black_box(value));
black_box(sum + values.len())
}
fn cap_vec_iter_sum(values: &CapVec<usize, CAP>) -> usize {
let sum = values.iter().fold(0, |acc, value| acc + black_box(*value));
black_box(sum)
}
fn vec_iter_sum(values: &[usize]) -> usize {
let sum = values.iter().fold(0, |acc, value| acc + black_box(*value));
black_box(sum)
}
fn cap_vec_into_iter_sum(values: CapVec<usize, CAP>) -> usize {
let sum = values
.into_iter()
.fold(0, |acc, value| acc + black_box(value));
black_box(sum)
}
fn vec_into_iter_sum(values: Vec<usize>) -> usize {
let sum = values
.into_iter()
.fold(0, |acc, value| acc + black_box(value));
black_box(sum)
}
criterion_group! {
name = benches;
config = Criterion::default()
.sample_size(10)
.warm_up_time(Duration::from_millis(200))
.measurement_time(Duration::from_millis(500));
targets = bench_vec_compare
}
criterion_main!(benches);