3dgeo-heidelberg / py4dgeo

py4dgeo - A Python library for change analysis in 4D point clouds
https://py4dgeo.readthedocs.io
MIT License
77 stars 12 forks source link

Parallelization of KDTree construction #92

Open dokempf opened 2 years ago

dokempf commented 2 years ago

Performance benchmarking shows that as is, the KDTree construction is the bottleneck of the entire algorithm. A naive approach to parallelization could be to distribute the subtree construction to threads. The very coarse levels do not parallelize well in this algorithm, but a sufficiently deep tree mitigates this disadvantage.

Implementation includes two non-trivial aspects:

dokempf commented 1 year ago

Nanoflann v1.5.0 added parallel construction support: https://github.com/jlblancoc/nanoflann/releases/tag/v1.5.0

However, my initial testing was far off the advocated speedup of 3. I got around 20% for medium core counts and the code got slower for large core counts. I am currently hesitant to include that in the code base, at least not without a user interface to control.