Releases: sdd/kiddo
v2.1.0
- feat: implement the main query methods plus
size
onkiddo::float::kdtree::ArchivedKdTree
and improve the rkyv example.
The previous Rkyv example was not really using Rkyv in the most efficient way (Thanks to @cavemanloverboy for spotting my mistakes!). In order to properly use rkyv'z zero-copy deserialization, you need to use rkyv::archived_root
to transmute a buffer into an ArchivedKdTree
. For ArchivedKdTree
to be useful, it actually needs some methods though!
v2.1.0 refactors the query code so that the method bodies of the queries are templated by macros, allowing them to be implemented on KdTree
and ArchivedKdTree
without completely duplicating the code.
The updated rkyv example shows the difference that zero-copy usage of rkyv makes vs deserializing, as well as also showing the gains that can be made using mmap compared to standard file access. Combining both together results in absolutely mind-blowing performance when measuring time-from-binary-start-to-first-query-result.
See for yourself by downloading the sample datasets mentioned in the examples readme and running:
cargo run --example rkyv --features=serialize_rkyv --release
On my machine, using the old technique of normal file access and deserialization into KdTree
, the example code takes 348 milliseconds to load and query. The memmapped code that just transmutes to an ArchivedKdTree
and then queries it takes 182 micro seconds(!) - an improvement by a factor of 1900x!!
I'll follow up this release with equivalent methods for Fixed
, and some more ergonomic methods for loading and saving.
v2.0.2
v2.0.0
It's finally here! After months and months of work, the full, from-the-ground-up re-write that is Kiddo v2 is finally ready for general release.
The TL; DR vs the previous version:
- a new internal architecture for much-improved performance;
- Added integer / fixed point support via the
Fixed
library; - instant zero-copy deserialization and serialization via
Rkyv
(Serde
still available). - See the changelog for a detailed run-down on all the changes made in v2.
How much improved performance? A lot. Kiddo v2 is fast. Very fast. In fact, it is faster than other libraries in almost every query, from 2 to four dimensions, from trees with a hundred to ten million nodes.
Don't just take my word for it: check out the benchmark results. Kiddo v1 is embarrassingly slow in comparison - you should upgrade now if you are using it and care about performance.
Try it and see!
v2.0.0-beta.9
- Performance of
nearest_n
queries improved significantly by switching from aMinMaxHeap
back to the originalBinaryHeap
and usinginto_sorted_vec()
- Return a
Neighbour
struct instead of a(dist, item)
tuple for all queries that return more than one result. This is a bit more ergonomic and also allows us to return the same struct that we use internally to store on theBinaryHeap
rather than transforming it needlessly into a tuple
v2.0.0-beta.2
- Add a lot more documentation. All of the public structs, methods, traits and types should now be documented.
- Fix the serialisation code for both Serde and Rkyv
Still to do:
- Improve docs
- Add more examples, especially for Rkyv serialisation