Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stack overflow in Query::next #1

Open
t-veor opened this issue Oct 4, 2020 · 3 comments
Open

Stack overflow in Query::next #1

t-veor opened this issue Oct 4, 2020 · 3 comments
Labels
bug Something isn't working

Comments

@t-veor
Copy link

t-veor commented Oct 4, 2020

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
Copy link
Owner

ambuc commented Oct 4, 2020

@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 #2 as a reminder to myself to implement that fix.

@ambuc ambuc added the bug Something isn't working label Oct 4, 2020
NoSuchThingAsRandom added a commit to NoSuchThingAsRandom/quadtree that referenced this issue Jan 10, 2022
@NoSuchThingAsRandom
Copy link
Contributor

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 (#3).

Is there any update on improving HandleIter performance?

@tooxo
Copy link
Contributor

tooxo commented Apr 5, 2023

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

4 participants