Avoiding SmallVec in SelectionIterator

[grovesNL]

In SelectionIterator and SelectionIteratorMut we use a SmallVec to queue nodes as we're iterating over the nodes in the tree, e.g.:

rstar/rstar/src/algorithm/iterators.rs

Line 46 in 84d1265

current_nodes: SmallVec<[&'a RTreeNode<T>; 24]>,

Constantly resizing this SmallVec seems to show up on some of my profiles where I have relatively dense trees.

I was wondering if there might be a way to avoid SmallVec here somehow but it's not clear how it could work. Maybe some other crates already have found a good pattern to avoid this kind of iteration queue? e.g., if we could somehow represent a flattened position of the next node then maybe that could work, but I don't know if this would be possible without changing how nodes are stored.

[adamreichold]

It was worse when this was a Vec instead of SmallVec. ;-)

But I think if we want to provide an Iterator-based, we do need the buffer as rstar uses a "dense" representation of the tree without padding out the nodes to a fixed size (so that sizes could just be computed).

I did try implementing internal iteration once in #37 but the recursive function overhead was not so nice. I could try to resurrect that code if you interested in trying that. It does obviously not provide an Iterator implementation though, so I am not sure if this works for you.

[adamreichold]

@grovesNL Please give #164 a try if it works for you. (Let me know if you need another query method besides the four examples provided over there.)

[grovesNL]

That's really interesting, thank you! I shouldn't need Iterator for my use case.

Internal iteration with recursion could work well and the benchmarks in that PR seem promising. I would be a little concerned with the extra call stack overhead depending on the tree depth, but the tradeoff might be worth it here.

I'm currently using locate_in_envelope_intersecting but it looks like the selection functions are mostly private, so I might have to modify a copy of your branch before I can try it out.

Maybe there might be some hybrid approach where we track parent nodes per tree level and the current child's offset on the stack (like the existing buffer), which would avoid frequently moving nodes in and out of the buffer. I'm not sure how something like that would compare to recursion though.

[adamreichold]

I pushed the envelope queries as a follow-up commit onto the branch/PR.

[grovesNL]

There's a bit of noise in the profile I'm using, but on average it looks like improves the performance for my use case (~185ms with internal iteration vs. ~234ms with Iterator, averaged over three runs each).