Add multithreading support

[KronosTheLate]

This PR has added a function knn_threaded. I am able to achieve several X speedup from multithreading, but a several X slowdown for small problems. This is an acceptable tradeoff IMO, and possibly some smart heuristic can be implemented to only multithread when beneficial.

An internal _batch_inds function accomplishes the batching for separating the task into as few partitions as possible, based on the following quote from the readme: "It is generally better for performance to query once with a large number of points than to query multiple times with one point per query."

I have been using the following function for timing:

using NearestNeighbors, BenchmarkTools
function time_knn(n, tree=BruteTree, metric=Euclidean(), k=1)
    times_knn = @belapsed knn($tree(randn($n, $n), $metric), randn($n, $n), $k)
    times_knn_threaded = @belapsed knn_threaded($tree(randn($n, $n), $metric), randn($n, $n), $k)

    speedup = times_knn / times_knn_threaded
    return speedup
end

which on my computer

julia> versioninfo()
Julia Version 1.7.1
Commit ac5cc99908 (2021-12-22 19:35 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)

with 4 physical and 8 logical cores, gives the following results:

julia> time_knn.([5, 20, 50, 200, 500, 1000])
6-element Vector{Float64}:
 0.1949891067538126
 0.3305439330543933
 1.9000000000000001
 2.6507951356407857
 2.79413549390029
 3.0004697251425743

This PR probably requires some cleaning, especially in determining a good API and possibly heuristics for when to use multithreading. I do not think that there should be a separate knn_threaded function, but I implemented it like this for now for easy comparison. If it is confirmed to be overall faster, then I think it should be the default option.

PS - this is my first attempt at multithreading, so please doublecheck things thoroughly before merging anything.

[KronosTheLate]

friendly bump

[davidbp]

I like the idea, I wish we could have a faster Knn in the package and leverage it in other packages, such as Clustering.jl. For reference I ended up doing something similar https://github.com/JuliaStats/Clustering.jl/pulls

[KronosTheLate]

Similar to NearestNeighbours, or Multithreaded Nearest Neighbours?

[davidbp]

I would say both make sense to have in the NearestNeighbors Package. KNN single threaded by default, and one version that does not store all pairwise distances (which is what Clustering.jl is doing at the moment) and maybe with a keyword argument to allow multithreaded.