After inserting a large amount of points into a quadtree, making queries can cause a stack overflow when iterating through results. I've cut down to a reproducing example here:
use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree};
// Insert regions into the quadtree in this pattern:
// +------+------+------+------+
// | | | | |
// | | | | |
// +------+------+------+------+
// | | | |
// | | | |
// +------+ (recurse) +------+
// | | | |
// | | | |
// +------+------+------+------+
// | | | | |
// | | | | |
// +------+------+------+------+
// then recurse into the centre, and repeat.
fn prepare_quadtree(tree: &mut Quadtree<usize, ()>) {
let mut step_size = 2usize.pow(tree.depth() as u32) / 4;
let mut x = 0;
let mut y = 0;
while step_size > 0 {
for i in 0..4 {
for j in 0..4 {
if i == 0 || i == 3 || j == 0 || j == 3 {
tree.insert(
AreaBuilder::default()
.anchor(Point {
x: x + i * step_size,
y: y + j * step_size,
})
.dimensions((step_size, step_size))
.build()
.unwrap(),
(),
);
}
}
}
x += step_size;
y += step_size;
step_size /= 2;
}
}
fn main() {
let mut tree = Quadtree::new(20);
for _ in 0..32 {
prepare_quadtree(&mut tree);
}
let result = tree
.query_strict(
AreaBuilder::default()
.anchor(Point {
x: tree.width() / 2 - 1,
y: tree.height() / 2 - 1,
})
.dimensions((2, 2))
.build()
.unwrap(),
)
.next();
println!("{:?}", result);
}Expected output:
Actual output:
$ cargo run --release
Finished release [optimized] target(s) in 0.07s
Running `target\release\quadtree-test.exe`
thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\release\quadtree-test.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)
My active toolchain:
stable-x86_64-pc-windows-msvc (default)
rustc 1.46.0 (04488afe3 2020-08-24)
Looking at it through a debugger, it looks like the problem is that Rust can't figure out Query::next is tail-recursive:
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if let Some(handle) = self.handle_iter.next() {
if let Some(entry) = self.store.get(&handle) {
if self.traversal_method.eval(entry.area(), self.query_region) {
return Some(entry);
}
}
return self.next();
}
None
}I'm not sure why, since it looks like all this function is dealing with is references and u64s. Maybe the Options confuse it?
In any case, replacing it with a semantically-equivalent iterative version fixes the issue:
#[inline]
fn next(&mut self) -> Option<Self::Item> {
while let Some(handle) = self.handle_iter.next() {
if let Some(entry) = self.store.get(&handle) {
if self.traversal_method.eval(entry.area(), self.query_region) {
return Some(entry);
}
}
}
None
}
By the way, the pattern of regions I used for the example seems to demonstrate the worst case for HandlerIter, because HandleIter::query_optimization can't optimise at all since the query area spans all four subquadrants of the root, and the behaviour of HandleIter::next() appears to be to evaluate every single handle past that, which in this case means going through literally every single subquadrant andhandle in the entire tree.
Surely this could be improved by HandleIter skipping over subquadrants that do not overlap with the query area at all? Then HandleIter::query_optimization shouldn't even be needed.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent