packed_spatial_index 0.3.0

Packed static spatial index for 2D and 3D AABBs with Hilbert ordering, adaptive parallel builds, and SIMD queries.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

//! Experiment: effect of `node_size` on 3D builds and SIMD queries.
//! Run: `cargo run --release --example nodesize_experiment_3d`

use std::time::Instant;

use packed_spatial_index::experimental::ExperimentalSortKey3D;
use packed_spatial_index::{Box3D, Index3DBuilder};
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};

const N: usize = 100_000;
const NQ: usize = 1_000;
const REPS_Q: usize = 200;
const REPS_B: usize = 50;

fn main() {
    let mut rng = StdRng::seed_from_u64(0x3D0B);
    let boxes: Vec<Box3D> = (0..N)
        .map(|_| {
            let x: f64 = rng.random_range(0.0..10_000.0);
            let y: f64 = rng.random_range(0.0..10_000.0);
            let z: f64 = rng.random_range(0.0..10_000.0);
            let dx: f64 = rng.random_range(0.1..20.0);
            let dy: f64 = rng.random_range(0.1..20.0);
            let dz: f64 = rng.random_range(0.1..20.0);
            Box3D::new(x, y, z, x + dx, y + dy, z + dz)
        })
        .collect();

    let mut qrng = StdRng::seed_from_u64(0x3ACE);
    let queries: Vec<Box3D> = (0..NQ)
        .map(|_| {
            let x: f64 = qrng.random_range(0.0..10_000.0);
            let y: f64 = qrng.random_range(0.0..10_000.0);
            let z: f64 = qrng.random_range(0.0..10_000.0);
            let w: f64 = qrng.random_range(10.0..200.0);
            Box3D::new(x, y, z, x + w, y + w, z + w)
        })
        .collect();

    println!(
        "N={N}, queries={NQ}\n{:>9} | {:>11} | {:>12} | {:>12}",
        "node_size", "build(serial)", "query SIMD", "query AVX-512"
    );
    println!("{}", "-".repeat(54));

    for &node_size in &[4usize, 8, 16, 32, 64] {
        let mut build_best = f64::INFINITY;
        for _ in 0..REPS_B {
            let start = Instant::now();
            let mut builder = Index3DBuilder::new(N)
                .node_size(node_size)
                .experimental_sort_key(ExperimentalSortKey3D::Hilbert);
            for &bounds in &boxes {
                builder.add(bounds);
            }
            let index = builder.finish().unwrap();
            build_best = build_best.min(start.elapsed().as_secs_f64() * 1e3);
            std::hint::black_box(index.num_items());
        }

        let mut builder = Index3DBuilder::new(N)
            .node_size(node_size)
            .experimental_sort_key(ExperimentalSortKey3D::Hilbert);
        for &bounds in &boxes {
            builder.add(bounds);
        }
        let simd = builder.finish_simd().unwrap();
        let (mut out, mut stack) = (Vec::new(), Vec::new());

        let mut simd_best = f64::INFINITY;
        for _ in 0..REPS_Q {
            let start = Instant::now();
            let mut total = 0usize;
            for &query in &queries {
                simd.search_simd(query, &mut out, &mut stack);
                total += out.len();
            }
            std::hint::black_box(total);
            simd_best = simd_best.min(start.elapsed().as_secs_f64() * 1e6);
        }

        let mut avx_best = f64::INFINITY;
        for _ in 0..REPS_Q {
            let start = Instant::now();
            let mut total = 0usize;
            for &query in &queries {
                simd.search_avx512(query, &mut out, &mut stack);
                total += out.len();
            }
            std::hint::black_box(total);
            avx_best = avx_best.min(start.elapsed().as_secs_f64() * 1e6);
        }

        println!(
            "{node_size:>9} | {build_best:>8.3} ms | {simd_best:>9.1} us | {avx_best:>9.1} us"
        );
    }
}