findNeighbors is slow for repeated calls, would be faster with caching in leaves

[froody]

I'm using findNeighbors via PDAL filters.icp, and the general algorithm is (pseudocode):

# Given two point clouds A and B
iterations = 100 # customizable
kdtree = KDTree(A)
for i in iterations:
    for point in B:
        kdtree.findNeighbours(point, 1)
    B = applyTransform(B)

This leads to poor data locality with repeated call to kdtree_get_pt for each iteration. I have a fix which caches points in leaf Node instances, and this leads to a ~3x performance increase in my limited testing. I can create a pull request if this is something of interest.

[jlblancoc]

There's probably some trade-off, but yes please go on and propose a PR.

Thanks!

[yasamoka]

@froody hello, do you still have the implementation by any chance? I have an iterative algorithm that needs every speedup it can get.

I can clean it up and create a pull request if you like. It would be much appreciated.

Thank you!