KristofferC / NearestNeighbors.jl

High performance nearest neighbor data structures (KDTree and BallTree) and algorithms for Julia.
Other
413 stars 65 forks source link

optimize some hypersphere checks for minkowski metrics #195

Closed KristofferC closed 2 months ago

KristofferC commented 2 months ago

We can:

Some kind of benchmark:

julia> x = BallTree(rand(3,10^5));

# master
julia> @time inrange(x, rand(3,10^5), 0.01);
  0.186999 seconds (133.77 k allocations: 11.731 MiB)

# PR
julia> @time inrange(x, rand(3,10^5), 0.01);
  0.155827 seconds (133.87 k allocations: 11.739 MiB)
KristofferC commented 2 months ago

To verify that this is better:

 using Revise, StableRNGs
 using NearestNeighbors
 data = rand(StableRNG(1), 3, 10^4);
 x = BallTree(data);
 v = rand(StableRNG(1), 3);
 using GFlops
 @count_ops inrange(x, v, 0.01)

Master:

Flop Counter: 2050 flop
┌──────┬─────────┐
│      │ Float64 │
├──────┼─────────┤
│  add │     610 │
│  sub │     640 │
│  mul │     640 │
│ sqrt │     160 │
└──────┴─────────┘

PR:

Flop Counter: 1491 flop
┌──────┬─────────┐
│      │ Float64 │
├──────┼─────────┤
│  add │     438 │
│  sub │     468 │
│  mul │     555 │
│ sqrt │      30 │
└──────┴─────────┘