125 lines
3.3 KiB
Rust
125 lines
3.3 KiB
Rust
use spacedog::*;
|
|
|
|
use rand::{Rng, SeedableRng};
|
|
use rand_hc::Hc128Rng;
|
|
|
|
fn create_random_points(num_points: usize, seed: &[u8; 32]) -> Vec<[f64; 2]> {
|
|
let mut rng = Hc128Rng::from_seed(*seed);
|
|
(0..num_points).map(|_| rng.random()).collect()
|
|
}
|
|
|
|
use criterion::Criterion;
|
|
use criterion::{criterion_group, criterion_main};
|
|
|
|
const SEED_1: &[u8; 32] = b"Gv0aHMtHkBGsUXNspGU9fLRuCWkZWHZx";
|
|
// const SEED_2: &[u8; 32] = b"km7DO4GeaFZfTcDXVpnO7ZJlgUY7hZiS";
|
|
|
|
const DEFAULT_NUM_POINTS: usize = 100_000;
|
|
|
|
fn new_index(c: &mut Criterion) {
|
|
c.bench_function("new index", move |b| {
|
|
let points: Vec<_> = create_random_points(DEFAULT_NUM_POINTS, SEED_1)
|
|
.into_iter()
|
|
.map(|[x, y]| Point2d { x, y })
|
|
.collect();
|
|
|
|
b.iter(|| {
|
|
Spindex2d::new(&points);
|
|
});
|
|
});
|
|
}
|
|
|
|
fn update_positions(c: &mut Criterion) {
|
|
c.bench_function("update positions", move |b| {
|
|
let points: Vec<_> = create_random_points(DEFAULT_NUM_POINTS, SEED_1)
|
|
.into_iter()
|
|
.map(|[x, y]| Point2d { x, y })
|
|
.collect();
|
|
|
|
let mut rng = Hc128Rng::from_seed(*SEED_1);
|
|
|
|
let jitters: Vec<_> = points
|
|
.iter()
|
|
.map(|p| {
|
|
let x = p.x + rng.random_range(-5.0..=5.0);
|
|
let y = p.y + rng.random_range(-5.0..=5.0);
|
|
Point2d { x, y }
|
|
})
|
|
.collect();
|
|
|
|
let index = Spindex2d::new(&points);
|
|
let mut round = 0;
|
|
b.iter(|| {
|
|
if round % 2 == 0 {
|
|
index.update(&jitters);
|
|
} else {
|
|
index.update(&points);
|
|
}
|
|
round += 1;
|
|
});
|
|
});
|
|
}
|
|
|
|
fn nearest_default_horizon(c: &mut Criterion) {
|
|
c.bench_function("nearst point with default horizon", move |b| {
|
|
let points: Vec<_> = create_random_points(DEFAULT_NUM_POINTS, SEED_1)
|
|
.into_iter()
|
|
.map(|[x, y]| Point2d { x, y })
|
|
.collect();
|
|
|
|
let index = Spindex2d::new(&points);
|
|
|
|
let mut i = 0;
|
|
b.iter(|| {
|
|
i += 1;
|
|
index.nearest(&points[i - 1]).is_some()
|
|
});
|
|
});
|
|
}
|
|
|
|
fn nearest_short_horizon(c: &mut Criterion) {
|
|
c.bench_function("nearst point with short horizon", move |b| {
|
|
let points: Vec<_> = create_random_points(DEFAULT_NUM_POINTS, SEED_1)
|
|
.into_iter()
|
|
.map(|[x, y]| Point2d { x, y })
|
|
.collect();
|
|
|
|
let index = Spindex2d::new(&points).with_horizon(20);
|
|
|
|
let mut i = 0;
|
|
b.iter(|| {
|
|
i += 1;
|
|
index.nearest(&points[i - 1]).is_some()
|
|
});
|
|
});
|
|
}
|
|
|
|
fn aabb_search(c: &mut Criterion) {
|
|
c.bench_function(
|
|
"search an axis-aligned bounding box 10 units a side",
|
|
move |b| {
|
|
let points: Vec<_> = create_random_points(DEFAULT_NUM_POINTS, SEED_1)
|
|
.into_iter()
|
|
.map(|[x, y]| Point2d { x, y })
|
|
.collect();
|
|
|
|
let index = Spindex2d::new(&points);
|
|
|
|
let mut i = 0;
|
|
b.iter(|| {
|
|
i += 1;
|
|
!index.aabb(&points[i - 1], 10.0).is_empty()
|
|
});
|
|
},
|
|
);
|
|
}
|
|
|
|
criterion_group!(
|
|
benches,
|
|
new_index,
|
|
update_positions,
|
|
nearest_default_horizon,
|
|
nearest_short_horizon,
|
|
aabb_search
|
|
);
|
|
criterion_main!(benches);
|