::Function argument in recursive function is expensive

[KristofferC]

Just having a function as an argument in a recursive function creates an allocation at each call. This is a minimized example from one of my packages:

function knn_kernel2!(index::Int)
    index > 1_000_000 && return
    knn_kernel2!(2*index)
    knn_kernel2!(2*index+1)
    return
end

function knn_kernel2!(index::Int,
                      skippoint::Function)
    index > 1_000_000 && return
    knn_kernel2!(2*index, skippoint)
    knn_kernel2!(2*index+1, skippoint)
    return
end

julia> @time knn_kernel2!(1)
  0.003125 seconds (4 allocations: 160 bytes)

julia> @time knn_kernel2!(1, x->false)
  0.181919 seconds (2.00 M allocations: 30.511 MB, 2.16% gc time)

Is there anyway to workaround this?

[KristofferC]

Hmm, I seem to already have reported this at #16185 (comment) and that was commented by @JeffBezanson with:

The reduced example in that issue might not get fixed. The extra code allows dynamic dispatch to a version of g specialized for f. The method in the example is probably not performance-critical, since all it does is call another function. This is part of the cost of faster higher-order functions.

So closing this but I don't know how to solve the problem...

[JeffBezanson]

A possible workaround is to force specialization like this:

function knn_kernel2!{F<:Function}(index::Int, skippoint::F)

But this is definitely a real issue, concerning the performance of dynamic dispatch and our calling convention. However fixing it is definitely a long-term project.