search

kzampog / cilantro

A lean C++ library for working with point cloud data
MIT License
1.02k stars 207 forks source link

Output of SimpleCombinedMetricRigidICP3f not deterministic #14

Closed wannesvanloock closed 5 years ago

wannesvanloock commented 5 years ago

While testing out ICP, I noticed the output of SimpleCombinedMetricRigidICP3f.estimate() is not deterministic. It seems due to multithreading as removing this omp reduction makes the output deterministic.

Steps to reproduce: Run the rigid_icp example multiple and observe the estimated transform. Even though differences are really small, I noticed very different results on other clouds, especially with respect to number of iterations.

I haven't checked the other implementations, but I suspect they suffer from the same issue.

wannesvanloock commented 5 years ago

Multi-threaded reductions are likely to be non-deterministic, so probably this is a no-fix issue.

kzampog commented 5 years ago

Hi!

Indeed, this should happen due to the reduction. The latest commit before I introduced it was ced6281b66cbd30478abc901d5d036f9a97d7d2b, which seems deterministic.

The reduction gives solid speedups (~50ms down to ~7ms of total optimization time -- correspondence search excluded -- in the example scenario on my machine), but if it behaves erratically I might have to revert back. How significant are the discrepancies you noticed?

Thanks for reporting this!

wannesvanloock commented 5 years ago

I looked into the issue some more. The varying number of iterations was due to setting a tolerance of 1e-6. Due to the non-determinism, this sometimes caused rapid convergence or no convergence at all. We could make determinism a compiler option. This way, no revert is required.

kzampog commented 5 years ago

Thanks for the suggestion! I added a CMake option to toggle non-deterministic reductions (enabled by default).