Allocations with recursive function using kwargs and a callback

General Usage
1

Allocations are often something that seem to appear rather unpredictably when you do more complicated things… Even if you’re aware of all the most typical causes of allocations, something new pops up every time. This tends to slow down my progress more than anything else. This time I decided to make a minimal example and post it here. Is this particular behavior expected, a bug, or just how things are?

When you have a recursive function that uses a callback and the kwargs... syntax, allocations start to appear. If you use the regular keyword argument syntax or don’t call the callback, no allocations.

test(l; limit=10) = (l >= limit)

function recur1(func, l=0; kwargs...)  # Causes allocations
    if test(l; kwargs...)
        return func(l)
    end
    recur1(func, l+1; kwargs...)
end

function recur2(func, l=0; limit=10)  # No allocations
    if test(l; limit)
        return func(l)
    end
    recur2(func, l+1; limit)
end

function recur3(func, l=0; kwargs...)  # No allocations
    if test(l; kwargs...)
        return identity(l)
    end
    recur3(func, l+1; kwargs...)
end

# Compile and test
recur1(identity) # returns 10
recur2(identity) # returns 10
recur3(identity) # returns 10
recur1(identity, limit=5) # returns 5
recur2(identity, limit=5) # returns 5
recur3(identity, limit=5) # returns 5

julia> @allocated recur1(identity)
0

julia> @allocated recur1(identity, limit=1)
0

julia> @allocated recur1(identity, limit=2)
32

julia> @allocated recur1(identity, limit=3)
64

julia> @allocated recur2(identity, limit=5)
0

julia> @allocated recur3(identity, limit=5)
0

As you can see, as soon as you pass a keyword argument to func1 it allocates starting from depth 2, with more allocations the deeper you go in recursion.

2

That does not hold for me

julia> @allocated recur1(identity)
0

julia> @allocated recur1(identity, limit=1)
0

julia> @allocated recur1(identity, limit=2)
0

julia> @allocated recur1(identity, limit=10)
0

I’m using Julia v1.10-rc1, what version are you using?

EDIT:

Actually, there seems to be some difference in how @allocated counts, using @time I do see the growing number of allocations

julia> @time recur1(identity, limit=1000)
  0.000127 seconds (2.49 k allocations: 54.469 KiB)
1000

julia> @time recur1(identity, limit=100)
  0.000018 seconds (99 allocations: 3.094 KiB)
100

julia> @time recur1(identity, limit=1)
  0.000002 seconds
1

julia> @time recur1(identity, limit=2)
  0.000002 seconds (1 allocation: 32 bytes)
2
3

Adding the type parameter T here helps

function recur1(func::T, l=0; kwargs...) where T # Causes no allocations
    if test(l; kwargs...)
        return func(l)
    end
    recur1(func, l+1; kwargs...)
end

julia> @time recur1(identity, limit=1)
  0.000001 seconds
1

julia> @time recur1(identity, limit=2)
  0.000001 seconds
2

julia> @time recur1(identity, limit=100)
  0.000002 seconds
100

I figured this out using AllocCheck.jl:

julia> AllocCheck.check_allocs(recur1, (typeof(identity),))
2-element Vector{Any}:
 Allocation of Int64 in /tmp/allocs.jl:7
  | recur1(func, l+1; kwargs...)

Stacktrace:
 [1] recur1(func::typeof(identity), l::Int64; kwargs::@Kwargs{})
   @ Main /tmp/allocs.jl:7
 [2] recur1
   @ /tmp/allocs.jl:3 [inlined]
 [3] #recur1#12
   @ /tmp/allocs.jl:7 [inlined]
 [4] recur1
   @ /tmp/allocs.jl:3 [inlined]
 [5] recur1(func::typeof(identity))
   @ Main /tmp/allocs.jl:3

 Dynamic dispatch to function recur1 in /tmp/allocs.jl:7
  | recur1(func, l+1; kwargs...)

Stacktrace:
 [1] recur1(func::typeof(identity), l::Int64; kwargs::@Kwargs{})
   @ Main /tmp/allocs.jl:7
 [2] recur1
   @ /tmp/allocs.jl:3 [inlined]
 [3] #recur1#12
   @ /tmp/allocs.jl:7 [inlined]
 [4] recur1
   @ /tmp/allocs.jl:3 [inlined]
 [5] recur1(func::typeof(identity))
   @ Main /tmp/allocs.jl:3

or in a screenshot for nicer highlighting:

image
image551×505 49.3 KB

which after adding the type parameter becomes

julia> check_allocs(recur1, (typeof(identity),))
Any[]
4

You’re right, adding a type parameter does the trick! Now that you say it, I actually remember that functions don’t specialize on function arguments that are not called within the function unless a type parameter is specified. I’ll try to find a link that…

Thanks!

5

The documentation actually mentions it

https://docs.julialang.org/en/v1/manual/performance-tips/#Be-aware-of-when-Julia-avoids-specializing

I’ve seen that before but this stuff is quite non-obvious and it’s hard to make the connection when the problem seemed to come from the kwargs.... I think callback functions in particular are a plentiful source of weird allocations. In some case I concluded that a callback in a recursive function caused allocations if the callback function had enough many lines of code, no matter what I did (I tried the specialization trick). Making a minimal example was obviously not simple so I didn’t try…