NNsearch returns neighbors in different order on MacOS - M1

BrunoLevy / geogram

a programming library with geometric algorithms

Other

1.8k stars 122 forks source link

NNsearch returns neighbors in different order on MacOS - M1 #153

Open BrunoLevy opened 2 months ago

BrunoLevy commented 2 months ago

On MacOS-M1 (macos-14 runner on github), some nearest neighbor search test fail (ANN and geogram return different results). Debugging strategy:

[ ] verify that ANN results are the same as with Intel architecture
[ ] check that there is no Intel-specific code in ANN

BrunoLevy commented 2 months ago

May come to float to int conversions, handled differently on M1 silicon, more information here

BrunoLevy commented 2 months ago

Another hypothesis: ANN has its own boolean type, it may be the culprit (M1 has different int<->bool conversion rules). -> Nope, still fails when redefiningh ANNbool as bool, ANNfalse as false and ANNtrue as true...

BrunoLevy commented 2 months ago

Tryed to define ANN_DLB_MAX as 1e300 (instead of using value from limits.h), did not work either.

BrunoLevy commented 2 months ago

Tryed to compile ANN with all warnings activated -> did not see anything.

BrunoLevy commented 2 months ago

So next thing to do is to determine which one of ANN or Geogram is right (and there is also the option that both are wrong !!). Let us output the IDs of the NNs when they differ, and compare with a "ground truth" obtained on an Intel...

BrunoLevy commented 2 months ago

Distances are nearly correct, except a tiny difference, may come from compiler's optimizations
It seems that I get garbage instead of the indices ! To be investigated... -> fixed: was 64-bits index_t <-> 32 bit indices in ANN
Tryed to recompute distance using same function, but it seems I still get small differences
For now, non-regression test uses distances, with tiny tolerance.

BrunoLevy commented 2 months ago

The problem (nearly) systematically happens when a pair of points is swapped in the two lists. Re-activated tolerance for now.