Performance regression after "Adapt AbstractArray subtypes for indexing fallbacks"

[KristofferC]

After noticing that my k-nearest-neighbour searches in https://github.com/KristofferC/KDTrees.jl got significantly slower I ran a git bisect and noticed that 5cb2835 causes a 30% net speed loss in the speed of my knn searches.

The relevant function can be seen here: https://github.com/KristofferC/KDTrees.jl/blob/master/src/kd_tree.jl#L394

I have seen there has been regressions for subarrays and high dimensional arrays but I am not using any of these.

Not sure how useful this is but profiling with

using KDTrees
tree = KDTree(rand(3,10^5))

knn(tree, rand(3), 5);
@profile for i = 1:10^6
    knn(tree, rand(3), 5)
end

gives the following data:

Slow: https://gist.github.com/KristofferC/e330d0a923f0a69261a4

Fast: https://gist.github.com/KristofferC/5950285ced3879c76298

Does anyone have any tips on good methods or "experiments" to try to narrow down the problem?

[mbauman]

Thanks for reporting this! I've narrowed down at least part of the issue to euclidean_distance_red(tree, idx, point). @code_typed is crazy-convoluted; way more convoluted than it needs to be. I'll look into this more thoroughly later this week, but you could try my branch at #11827 to see if it resolves everything?

[KristofferC]

Master

knn / sec: 438334.517

#11827

knn / sec: 601891.399

This seems to bring performance back to pre 5cb2835. Great 👍

[mbauman]

Thanks for testing it! Now I need to work on getting it fixed properly.

[mbauman]

Fixed by #11827 (and requires #7799 for a proper fix).

[KristofferC]

Thanks for a timely fix.