Stack overflow in Query::next

[t-veor]

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:

None

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.

[ambuc]

@t-veor, thank you for this exhaustive and extremely helpful bug report! I am delighted to see someone else is using this library in a complex enough way to catch a bug. If you don't mind, I would be interested to hear what you are using it for.

It seems you have already written a fix for the next() method -- would you mind terribly taking out a PR?

I think you are right about improving HandleIter and have taken out https://github.com/ambuc/quadtree/issues/2 as a reminder to myself to implement that fix.

[NoSuchThingAsRandom]

Hi, Similarly, I have ran into the same issue and the fix provided by @t-veor works. I forked and implemented the fix at (https://github.com/NoSuchThingAsRandom/quadtree) and opened a pull request to merge the changes upsteam (https://github.com/ambuc/quadtree/pull/3).

Is there any update on improving HandleIter performance?

[tooxo]

Hey, I've noticed a great performance improvement in HandleIter just by changing the function from a recursive to a iterative structure like so:

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(handle) = self.handle_stack.pop() {
                if !self.visited.insert(handle) {
                    continue;
                }
                return Some(handle);
            }

            // Then check the qt_stack.
            if let Some(qt) = self.qt_stack.pop() {
                // Push my regions onto the region stack
                self.handle_stack.extend(qt.handles());

                // Push my sub quadrants onto the qt_stack too.
                if let Some(sub_quadrants) = qt.subquadrants().as_ref() {
                    self.qt_stack.extend(sub_quadrants.iter().map(|x| x.deref()));
                }
                continue;
            }

            // Else there's nothing left to search.
            return None;
        }
    }

Another possibility would be to first search the sub-quadrants with the greatest overlap to the search area, so maybe fewer iterations would be necessary in most usecases?