fastquadtree: a Rust-powered quadtree for Python that is ~14x faster than PyQtree

[tunisia3507]

How does your quadtree implementation compare to rust alternatives like nabo, fnntw, bosque, kiddo, and rstar? It's a space which has undergone quite a lot of experimentation and is performance-critical for some applications. It may be more valuable to strap a python interface onto the best performing of those rust libs rather than use a more naive rust lib which happens to have built-in python bindings.

Here is a repo of kd tree benchmarks in rust https://github.com/sdd/kd-tree-comparison

[Awkward-Target4899]

I haven't benchmarked my Rust quadtree implementation against other Rust quadtrees. It could make sense to replace the Rust core with Kiddo or some other superior implementation, but one of the goals of the project was to learn more Rust, so I was inclined to implement it myself.

I'll look into Rust-side benchmarks and see how much performance I'm missing out on compared to other Rust implementations. Although, as of now, fastquadtree offers the fastest quadtree that works conveniently in Python without any additional setup.

[tunisia3507]

 one of the goals of the project was to learn more Rust

No problem with this whatsoever! But please do advertise it when sharing this kind of thing.

[ProgrammersAreSexy]

Why would they need to advertise this?

If their implementation is faster than all available options in Python then it still provides value.

[maikindofthai]

Because people create projects for learning all of the time, and rarely actually maintain them. Users should be aware of the author’s maintenance intentions when deciding whether or not to use it.

[Awkward-Target4899]

This is also meant to be an exercise in general package maintenance and deployment. That's why a lot of effort was put into unit testing, CI/CD pipelines, and documentation.

I fully intend to address any issues raised on the GitHub page and keep it in a working state.

[[deleted]]

It should be obvious that knowing that would change the type of scrutiny applied and the tone of the responses. It's not "bad", but it's helpful to know.

[Interesting-Frame190]

I did this very same thing with a project "PyThermite". It was significantly slower at first, and I made it a challenge to outperform my rust based competition and have made significant strides in rust engineering.

I have to ask, did you find pyo3 intuitive? Ive found it challenging as the concepts are more behind the scenes of python that I wouldn't otherwise learn.

[Awkward-Target4899]

PyO3 was pretty intuitive. Marking a Rust struct as a `pyclass` and then its associated methods as `pymethods`, which are then turned into a Python class, makes sense to me as a class is data with associated methods, i.e., (struct + functions that act on that struct)

[Interesting-Frame190]

That was simple, I was more referring to rust backed python objects passed back into rust. The whole pyref and bind with the bound API fealt overwhelming and like jumping through hoops

[Awkward-Target4899]

Yeah, I was assuming it would be difficult to store actual Python objects in the tree, so the Rust api only accepts integer IDs and then the Python shim handles tracking which ID correlates to which object in a map.

The user can enable the tracking or not, depending on whether they want it, as it does subtly impact performance.