aabb 0.7.0

Static AABB spatial index for 2D 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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

//! Performance profiling example for tree building
//! 
//! This example focuses exclusively on benchmarking the build phase.
//! Designed to be used with low-level profilers like `samply`:
//! 
//! ```bash
//! samply record cargo run --release --example perf_build
//! ```

use aabb::prelude::*;
use std::time::Instant;

fn main() {
    println!("AABB Build Performance Benchmark");
    println!("=================================\n");
    
    println!("Generating 1,000,000 random bounding boxes...");
    let mut boxes = Vec::new();
    let mut rng = 12345u64; // Simple LCG random number generator
    
    for _ in 0..1_000_000 {
        rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        let x1 = ((rng >> 32) as f64 / u32::MAX as f64) * 1000.0;
        
        rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        let y1 = ((rng >> 32) as f64 / u32::MAX as f64) * 1000.0;
        
        rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        let size_x = ((rng >> 32) as f64 / u32::MAX as f64) * 50.0 + 1.0;
        
        rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        let size_y = ((rng >> 32) as f64 / u32::MAX as f64) * 50.0 + 1.0;
        
        boxes.push((x1, y1, x1 + size_x, y1 + size_y));
    }
    
    println!("Running build phase benchmark 100 times for profiling...\n");
    
    let num_runs = 100;
    let mut total_add_time = std::time::Duration::ZERO;
    let mut total_build_time = std::time::Duration::ZERO;
    
    let overall_start = Instant::now();
    
    for _run in 1..=num_runs {
        let build_start = Instant::now();
        let mut tree = AABB::with_capacity(1_000_000);
        
        // Add all boxes
        for (x1, y1, x2, y2) in &boxes {
            tree.add(*x1, *y1, *x2, *y2);
        }
        
        let add_duration = build_start.elapsed();
        total_add_time += add_duration;
        
        // Build the tree
        let build_phase_start = Instant::now();
        tree.build();
        let build_phase_duration = build_phase_start.elapsed();
        total_build_time += build_phase_duration;
        
        // if run % 10 == 0 {
        //     println!("Run {:3}/{}: Add {:.2}ms, Build {:.2}ms", 
        //         run, num_runs,
        //         add_duration.as_secs_f64() * 1000.0,
        //         build_phase_duration.as_secs_f64() * 1000.0
        //     );
        // }
    }
    
    let overall_duration = overall_start.elapsed();
    
    println!("\nBuild Summary ({} runs):", num_runs);
    println!("  Total Add time:   {:.2}ms", total_add_time.as_secs_f64() * 1000.0);
    println!("  Average Add:      {:.2}ms", total_add_time.as_secs_f64() * 1000.0 / num_runs as f64);
    println!("  Total Build time: {:.2}ms", total_build_time.as_secs_f64() * 1000.0);
    println!("  Average Build:    {:.2}ms", total_build_time.as_secs_f64() * 1000.0 / num_runs as f64);
    println!("  Overall time:     {:.2}ms", overall_duration.as_secs_f64() * 1000.0);
}


/*
cargo build --release --example perf_build
./target/release/examples/perf_build
samply record cargo run --release --example perf_build

Build Summary (100 runs):
  Total Add time:   1296.90ms
  Average Add:      12.97ms
  Total Build time: 9583.86ms
  Average Build:    95.84ms
  Overall time:     10988.86ms
_________________________________________________
OPT 6 - avoiding resize of initial data array
  Total Add time:   1091.36ms
  Average Add:      10.91ms
  Total Build time: 9616.03ms
  Average Build:    96.16ms
  Overall time:     10827.15ms
_________________________________________________
OPT 7 - replacing custom quicksort with sort_unstable_by_key
Note the Add phase also imrpves 50% somehow (memory layout?)
  Total Add time:   459.30ms
  Average Add:      4.59ms
  Total Build time: 7675.16ms
  Average Build:    76.75ms
  Overall time:     8231.33ms

__________________________________________________
OPT 8 - removed unecessary vector initializations (2.3%)
  Total Add time:   457.16ms
  Average Add:      4.57ms
  Total Build time: 7544.34ms
  Average Build:    75.44ms
  Overall time:     8124.56ms
___________________________________________________
OPT 9 - Calculate exact total nodes needed
  Total Add time:   397.41ms
  Average Add:      3.97ms
  Total Build time: 7442.48ms
  Average Build:    74.42ms
  Overall time:     7965.43ms
___________________________________________________
Removed sorted_order
  Total Add time:   390.01ms
  Average Add:      3.90ms
  Total Build time: 7471.13ms
  Average Build:    74.71ms
  Overall time:     7986.26ms
___________________________________________________
 */