Add skip predicate to inrange, fixes #53

[schmrlng]

Relatively straightforward changes to the inrange methods; I also moved the skip check up in add_points_knn! (https://github.com/schmrlng/NearestNeighbors.jl/blob/3657a02de0c8f78f12c2f797b8b144830509eae8/src/tree_ops.jl#L93) to potentially save an evaluate call.

[codecov-io]

Codecov Report

Merging #56 into master will increase coverage by 0.07%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master      #56      +/-   ##
==========================================
+ Coverage   93.89%   93.96%   +0.07%     
==========================================
  Files          14       14              
  Lines         508      514       +6     
==========================================
+ Hits          477      483       +6     
  Misses         31       31

Impacted Files	Coverage Δ
src/knn.jl	96.42% <ø> (ø)	:arrow_up:
src/ball_tree.jl	100% <100%> (ø)	:arrow_up:
src/inrange.jl	95.83% <100%> (ø)	:arrow_up:
src/kd_tree.jl	100% <100%> (ø)	:arrow_up:
src/tree_ops.jl	90.47% <100%> (+0.64%)	:arrow_up:
src/brute_tree.jl	100% <100%> (ø)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 012a3da...49f89e8. Read the comment docs.

[KristofferC]

Relatively straightforward changes to the inrange methods

Straightforward huh? ;)

Benchmark:

julia> tree = KDTree(rand(3, 10^5));

julia> using BenchmarkTools

julia> @btime inrange(tree, [0.0, 0.0, 0.0], 0.1);

Master:

1.957 μs (7 allocations: 1.31 KiB)

This PR:

16.082 μs (321 allocations: 6.22 KiB)

So inrange is now 8 times slower... See https://github.com/KristofferC/NearestNeighbors.jl/pull/31. There has been a lot of effort going into optimizing performance for this package, so at least try some basic benchmarks to check for regressions.

[schmrlng]

Whoops, sorry about that. So the two function signature styles here really aren't equivalent in the case of Functions? This makes me question a lot of code I've written which has passed functions as arguments...

In some initial tests, it appears to me that forcing specialization for all methods that take skip::Function as an argument (not just the innermost recursive method) results in a slight, maybe ~5%, performance improvement. Is there a reason the change to skip::F ... where {F} shouldn't be made everywhere? If we're already planning to recompile a new inrange or knn recursive kernel for every skip function, compiling new specialized wrappers wouldn't be much worse right?

[schmrlng]

I went ahead and forced specialization for every occurrence of skip in this package. Benchmarks from runbenchmarks.jl may be found here: https://gist.github.com/schmrlng/d26f3c8803e091331cc30003e90aebd9.

The comparison was produced by running these commands with const EXTENSIVE_BENCHMARK = true in runbenchmarks.jl.

git checkout 3ad1e2edd146cd7b700d9a3c3716963b116fb927
julia -e 'using Compat; include("runbenchmarks.jl"); run_benchmarks("master")'
git checkout 49f89e8b9879b77084bca56158c5b8df82299c8e
julia -e 'using Compat; include("runbenchmarks.jl"); run_benchmarks("PR56")'
julia -e 'using Compat; include("runbenchmarks.jl"); generate_report("PR56", "master")'

[Datseris]

bump here?