Is ErrorKind and all the Options it creates really necessary? API pollution and Potential Runtime Performance impact

[EriKWDev]

Hi!

I read through the implementation and found that almost everything is an Option/Result due to the choice from the original kdtree to include hrm "useful" runtime errors such as inserting infinite coordinates, 0 capacity and whatnot.

This causes some pretty tedious API usage that can be seen in the tests: (tests/count_dist.rs):

// Sure hope you like typing '.unwrap()' ...
let mut kdtree = KdTree::with_per_node_capacity(capacity_per_node).unwrap();

kdtree.add(&POINT_A.0, POINT_A.1).unwrap();
kdtree.add(&POINT_B.0, POINT_B.1).unwrap();
kdtree.add(&POINT_C.0, POINT_C.1).unwrap();
kdtree.add(&POINT_D.0, POINT_D.1).unwrap();

From my experience it not only pollutes the API with a bunch of .unwrap()/.expect() (which panics on errors anyway so what's the point...) and in a toy game I'm writing that rebuilds the tree every frame, using cargo flamegraph we can see that is_some() actually shows up significantly in runtime of the release build. (This might be due to the algorithm though and not the ErrorKinds... in which case this is irrelevant to the API pollution and is fine enough)

Would it not be possible to remove all the error-kinds in the name of a cleaner API and (potential) runtime performance with a "promise" from the user not to insert what I would call stupid values anyways? xP Alternatively have a kiddo::KdTreeYesIPromiseNotToInsertWeirdThings (with a better name..). Alternatively yet would be to have the checks behind some compile flag cfg! or just simple assert_eq!..

I feel like someone who creates a KdTree with zero capacity should also expect the program to panic! on insert. In what use-case would one want to be able to create a tree with zero capacity and have a runtime check for it?

culprits:

This function causes almost every part of the API to become a Result/Option.

fn check_point(&self, point: &[A; K]) -> Result<(), ErrorKind> {
    if point.iter().all(|n| n.is_finite()) {
        Ok(())
    } else {
        Err(ErrorKind::NonFiniteCoordinate)
    }
}

---

Everytime you make a query:

if self.size == 0 {
    return Err(ErrorKind::Empty);
}
self.check_point(point)?;

---

Does anyone who uses the KdTree actually have checks for any of these errorkinds? I find myself just .unwrap()-ing. Should the API really be polluted and runtime efficiency impacted due to cases that don't happen in real usage? I feel like I could do my own if !tree.is_empty() { /* .. */ } if I really want to check for Empty-ness.

pub enum ErrorKind {
    NonFiniteCoordinate,
    ZeroCapacity,
    Empty,
}

---

Could this not be a compile-time error? I'm not too familiar with it but perhaps NonZeroUsize could be used? Alternatively just assert_ne!(capacity, 0)

pub fn with_per_node_capacity(capacity: usize) -> Result<Self, ErrorKind> {
    if capacity == 0 {
        return Err(ErrorKind::ZeroCapacity);
    }
   /* ... */
}

---

I haven't investigated the algorithm in detail enough yet to see if the .is_some() comes from all these checks or if it is an integral part of the algorithm, but if not for performance reasons I think removing these would still clean up the API a bunch.

[sdd]

Hi Erik! Thanks so much for taking the time to write this, it's very much appreciated.

Your point about initializing with zero dimensions / zero capacity makes total sense - I like the idea of using NonZeroUsize and in fact I think I may have toyed with using that before, I don't recall the outcome. Switching to that or a panic would make things cleaner.

Regarding the extra checks around check_point, I'm inclined to agree with you too - Kiddo's aims are for performance and ergonomics, in that order, and if removing these checks enhances both of those then I'm all for it, since, as you say, users of the library can put those checks in-place themselves if they feel the need.

I'm quite excited to try this out on both the benchmark suite and some real-world workloads! 😁

[sdd]

Removing all the emptiness and finite-ness checks has made the API feel more ergonomic. In terms of the benchmark suite though, there does not seem to be any significant change. I'll try it with a real-world workload though and see if I see any effect.

[sdd]

The changes are on this branch, if you want to check for your use case: https://github.com/sdd/kiddo/tree/remove-some-checks-and-errors

[sdd]

I'm seeing no real change in the real-life workload I've tested it with.

[EriKWDev]

I'll check it out with my workload tomorrow. As I said I hadn't investigated the algorithm enough to determine where that is_some() came from so it's probably part of the core algorithm.

But great with the improvements! I felt like the API could indeed feel a lot better :) I tried removing them on a local clone I have as well but ran into some issues with Iterator traits.

[EriKWDev]

Nice! Yup feels much better now without the .unwraps. I noticed though that is_empty() is actually not implemented for the KdTree, only .size(), so maybe that should be added now since it's the new way to do such checks..

#[inline]
pub fn is_empty(&self) -> bool {
    self.size == 0
}

I can further confirm that I see no measuralbe performance increase, but I still think that this is a win :)

The use case that I have for my bullet-hell-ish/tower-defense game is to populate the tree with enemy positions every frame so that I can make queries for bullets and towers on wether they've hit the enemies. There can be quite a few bullets and enemies on screen at once and Kiddo has helped with the performance a bunch. nearest_one is used a ton.

This is perhaps a bit beyond the scope of what this issue covers, but I have a question: Is there a more efficient way to clear the tree and bulk add new positions rather than just calling tree = kiddo::KdTree::with_per_node_capacity(X) again and then repeatedly calling .add? I have tried tuning the per_node_capacity but I still see a spike in the flamegraph for every frame's rebuilding of the tree:

This is perhaps an inherit limitation of the algorithm xP I get more than enough performance as is so no worries there, but would be good to know if there's a more efficient way.

[sdd]

For sure, is_empty would be a good addition now that the onus on checking emptiness is on the library user. Really great to hear that Kiddo has helped with performance! Regarding bulk adds - repeated add calls is really the only way, and like you say, it is an inherent limitation of how kd trees work. If you had some items in the tree that are static and some that are moving, an alternative to rebuilding the tree could be to call remove for all of the items that moved, and only re-add those? Not sure if it would definitely be faster or not but worth a try.