BoundsTree balance and CPU evidence

This is index-only Linux/x86-64 orb evidence from 2026-09-13, against the pre-change base. It measures neither native GPU performance nor FPS. Scene recording, renderers, resource leases, geography components and presentation are outside this change.

Contract and algorithm

Insertion assigns exactly one plus the maximum order of intersecting prior bounds; no intersecting bounds means order one. Search calls the existing Bounds::intersects: touching edges do not intersect, but a zero-size point strictly inside a nonempty rectangle does. The global-max shortcut is valid even with ties because any intersecting global maximum proves the answer. A miss must search for other leaves, including tied maxima.

All leaves now have the same depth. A full internal node splits its 13 children into groups of 6 and 7, sorting a fixed scratch array by origin along its longest bounding-box axis. A sibling propagates to the parent, recursively in concept but iteratively in code; an overflowing root creates a new root. Other internal nodes have 6–12 children; the root has 2–12. Descent minimizes half-perimeter enlargement, then union half-perimeter, with stable ties. Metadata is recomputed from children; a maximum-order child is placed last for stack traversal.

For n leaves and height h measured in root-to-leaf edges, a non-leaf root requires at least 2 × 6^(h−1) leaves. Descent and propagation are O(log n); each level does bounded work on at most 13 children. A split uses fixed-size insertion sort, O(13²), without requiring Ord, Copy, coordinate conversion or new arithmetic traits on units. Search remains O(n) worst-case when subtree bounds overlap; balanced height does not promise logarithmic spatial queries. Storage is O(n). The nodes vector retains leaf indices across growth and splits. Search uses indices rather than raw pointers. Both traversal stacks and node allocation capacity are retained by clear; there is no recursive traversal or rebuild.

Reproduce the isolated comparison

cargo test -p gpui-box --lib bounds_tree
cargo clippy -p gpui-box --lib --tests -- -D warnings
cargo run -p xtask -- dependencies check
bash crates/gpui/src/bounds_tree/benchmark.sh

The script compiles the actual old/new index source against the same GPUI Bounds/geometry implementation. Only test instrumentation is inserted in the old source: one counter at insertion-descent loop entry and one at search stack pop. Current source has matching cfg(test) counters. These are not all CPU operations: they exclude child scans, metadata unions, splitting and the single global-max check. Height, ownership and metadata are inspected outside timing. Input generation and order-oracle checks are also outside timing. Every case constructs a separate tree and includes its insertion allocations in timing.

release in this script means index and generic geometry monomorphizations compiled with rustc -C opt-level=3 -C debug-assertions=no; debug means opt-level=0 with debug assertions. Linked GPUI dependencies use the test profile. This isolates the index without a whole-workspace thin-LTO build and must not be confused with an application's cargo --release timing. Timings below are one sample, not statistical performance guarantees. Compiler: Rust 1.97.1.

Logs and complete little-endian u32 order vectors are written under target/bounds-tree-bench/. The script compares every order byte-for-byte between old and new in each mode; it does not infer equality from a checksum.

Structural evidence exposes the old degeneration

Horizontal bounds are (3i, −17, 2, 7), so every order is independently known to be one. Fully overlapping bounds are (−3, 7, 11, 19), so order i is i+1. The fully overlapping fast path explains its zero search pops; it does not eliminate insertion descent. At 100k, horizontal node count grows from 109,091 to 119,994 for minimum split occupancy; fully overlapping node count falls from 116,383 to 109,978. This is a storage/time tradeoff, not free balancing.

The dense fixture inserts i=0..9,999 in source order with longitude −179+(i mod 1000)×0.358 and latitude −80+floor(i/1000)×1.6. Projection is x=(longitude+180)/360, y=0.5−latitude/360. Screen centers are (320,140)+(projected−projected[5000])×280; destinations are 10×10 bounds centered on them. Every assigned order is additionally checked with an independent quadratic strict-overlap oracle. No component batching or paint-order shortcut is involved.

Optimized CPU samples

Small fully overlapping submissions can be slower because splitting and exact metadata maintenance cost more despite fewer descents. The result establishes bounded insertion height, not a speedup for every input.

Debug CPU samples and completed checks

Both modes produced the same structural counters above. All seven old/new order-vector comparisons passed byte-for-byte in both modes, including all 100k cases. cargo test -p gpui-box --lib passed 626 tests, with only the isolated CPU benchmark ignored. Focused BoundsTree tests also passed with --no-default-features. Default and no-default-feature library/test Clippy passed with -D warnings. dependencies check reported “package identities, dependency graphs, compatibility, and provenance records agree”. Rustfmt, benchmark shell syntax and git diff --check passed.

Correctness and remaining integration checks

Focused tests independently derive orders for asymmetric horizontal, vertical, reversed, row-major grid, fully overlapping, nested, disconnected, touching and zero-size inputs. Seeded random tests compare both insertion and later queries against a naive oracle and verify deterministic node construction. Existing 1,000-seed fractional-coordinate coverage is retained. Structural checks cover root splits, occupancy, unique ownership, reachability, metadata and equal leaf depth, with six 100k workloads. Tied maxima, retained clear/reuse capacity and non-Copy, partially ordered units have direct tests.

The renderer/headless catalog and the full workspace gate must be checked by the coordinator after integration with independently owned Scene work. Native macOS/Windows lanes have not run in this Linux worker. These CPU tests make no new native-platform or rendered-frame claim and do not attribute all geography paint or semantic-bound costs to this tree.