Bonsai: Compiling Queries to Pruned Tree Traversals
summary
Bonsai compiles high-level queries plus an annotated algebraic tree spec into C++ single-pass traversals that automatically generate always/maybe/never pruning conditions using symbolic interval analysis and added geometric predicate analysis. It fuses filters, counts, reductions and products into one traversal, reads tree augmentations (counts, mins) to avoid recursion, and produces code that matches handwritten traversals, gives asymptotic speedups over scans, equals hand-tuned ray tracers and beats a collision library by ~1.5x, artifacts available with the paper.
AI-written summary · about
chapters (14)
- 0:00Bonsai compiler intro
- 1:02Interval trees example
- 3:50Query ops in Bonsai
- 5:13Compiling queries to traversals
- 6:17State of the art before Bonsai
- 7:21Base iterators for traversals
- 8:45Count ops with filters
- 9:28Lowering filters in Bonsai
- 10:30Pruning via predicate analysis
- 12:15Performance results
- 13:59Geometric predicate analysis
- 16:49Representative power
- 17:49Bonsai in system ecosystem
- 18:39Q&A
related talks
38mModern B-Tree techniques
14mDataflow-Based Pruning for Speeding up Superoptimization
08mCompiling pattern matching to in-place modifications
15mSealing Pointer-Based Optimizations Behind Pure Functions
32mTyped Program Analysis Without Encodings
32mCircuits for Querying Trees: A Little Survey
20mThe Functional Essence of Imperative Binary Search Trees
08mEarly Path Traversal Pruning