# Recursive inner functions a thousand times slower?

**URL:** <https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604>\
**Category:** Performance\
**Created:** [August 11, 2022, 4:43am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604 "2022-08-11T04:43:21Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![ikirill](https://avatars.discourse-cdn.com/v4/letter/i/43a26b/32.png) [@ikirill](https://discourse.julialang.org/u/ikirill)\
**Post date:** [August 11, 2022, 4:43am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/1 "2022-08-11T04:43:21Z")

</div>

In the following code

```julia
function f(y)
    loop(x::Int)::Int = x > 0 ? 1 + loop(x-1) : 0
    loop(y)
end

g(x::Int)::Int = x > 0 ? 1 + g(x-1) : 0

```

I get the following timings:

```julia
julia> @btime f(100)
  12.770 μs (2 allocations: 32 bytes)
100

julia> @btime g(100)
  106.513 ns (0 allocations: 0 bytes)
100

```

with the internal recursive function being 100 times slower than an equivalent top-level function. Obviously adding up 100 1’s should take around ~5ns.

In pprof I can see that `loop` calls `jl_apply_generic`, which calls `jl_invoke` which calls `loop`, which I’m guessing is what makes `f` particularly slow.

It seems ([Performance of recursive function](https://discourse.julialang.org/t/performance-of-recursive-function/83961) [Type instability of nested recursive function - #3 by ma-chengyuan](https://discourse.julialang.org/t/type-instability-of-nested-recursive-function/78392/3)) that this has been an issue for a while, but does anybody know of a workaround that doesn’t involve hand-unrolling the recursion by maintaining a stack manually? My actual code is quite a lot bigger than this and unrolling it by hand or hoisting out the recursive loop would be difficult.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 11, 2022, 5:48am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/2 "2022-08-11T05:48:50Z")

</div>

Seems like a self-referential version of [this](https://discourse.julialang.org/t/type-instability-of-nested-function/57007/2), which links to the core Github issue #15276. The problem in that case seems like the compiler gives up easily on inferring the captured value if it changes during runtime, which can be worked around by replacing the closure with a functor, a function-like instance whose type is a `struct` containing captured variables (`struct` and the associated `function` are defined at global scope).

I’m not exactly sure why the compiler gives up on inferring a nested recursive function (this doesn’t look like a world age problem, which involves global scope definitions, and nested method definitions aren’t actually redone as dynamically as global definitions), and the workaround is to define the method at global scope like `g`. If you need to capture other variables, you could make a functor as described before. (EDIT: To be clear, a functor could only capture itself if you struggle with uninitialized `mutable struct`s, and it is unnecessary for calling the function part. I’m talking about capturing other things, like if you wanted to iterate with different steps `g(x-step)` ).

---

<div class="post-metadata">

**Author:** ![filchristou](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/filchristou/32/26760_2.png) [@filchristou](https://discourse.julialang.org/u/filchristou)\
**Post date:** [August 11, 2022, 6:45am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/3 "2022-08-11T06:45:33Z")

</div>

I was playing around with this and can someone explain me this: Just by removing the type annotation I get 4x faster execution. In the meantime the `@code_warntype` code remains the same:

```julia
function f2(y)
    loop(x) = x > 0 ? 1 + loop(x-1) : 0
    loop(y)
end

```

In my machine `f(100)` runs in _14μs_ and `f2(100)` in _3μs_.

```julia
julia> @btime f2(100)
3.066 μs (2 allocations: 32 bytes)

```

What surprises me is that even `@code_llvm` code looks the same. Is there any way to understand what is going on here ?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 11, 2022, 7:31am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/4 "2022-08-11T07:31:46Z")

</div>

I can replicate this (17.8us vs 5.3us) on a mac, and the `@code_native` also matches.

---

<div class="post-metadata">

**Author:** ![marius311](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marius311/32/3953_2.png) [@marius311](https://discourse.julialang.org/u/marius311)\
**Post date:** [August 11, 2022, 8:27am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/5 "2022-08-11T08:27:23Z")

</div>

Here’s one workaround:

```julia
function f3(y)
    loop(loop, x) = x > 0 ? 1 + loop(loop, x-1) : 0
    loop(loop, y)
end
@btime f3(100) # ~100ns

```

Like those other issues mention, the problem is the `loop` variable is used in the function (to call itself recursively) so its a closed-over variable, then for various Julia reasons it gets Boxed, which then leads to bad performance. Here, you just manually pass it around as an argument.

---

<div class="post-metadata">

**Author:** ![ikirill](https://avatars.discourse-cdn.com/v4/letter/i/43a26b/32.png) [@ikirill](https://discourse.julialang.org/u/ikirill)\
**Post date:** [August 11, 2022, 8:35am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/6 "2022-08-11T08:35:57Z")

</div>

That’s just like the solution everybody uses in C++!

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 19, 2022, 7:21am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/7 "2022-08-19T07:21:42Z")

</div>

[Another thread](https://discourse.julialang.org/t/extra-allocation-with-t-datatype/85930/19) made me remember this and consider if `@btime` is the problem here, but unlike that example, `@time`ing a loop actually corroborates the 3-4x difference in `@btime`, not the matching `@code_native`/`@code_llvm`:

```julia
julia> @time for i in 1:10_000
        f(i÷i*100) # prevent constant hoisting
       end
  0.181906 seconds (20.00 k allocations: 312.500 KiB)

julia> @time for i in 1:10_000
        f2(i÷i*100) # prevent constant hoisting
       end
  0.056144 seconds (20.00 k allocations: 312.500 KiB)

julia> 0.181906/0.056144
3.239990025648333

```

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [August 20, 2022, 2:19am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/8 "2022-08-20T02:19:28Z")

</div>

If the issue you want to avoid is namespace pollution, you could put the recursive function into the top level of a submodule.

---

<div class="post-metadata">

**Author:** ![ikirill](https://avatars.discourse-cdn.com/v4/letter/i/43a26b/32.png) [@ikirill](https://discourse.julialang.org/u/ikirill)\
**Post date:** [August 20, 2022, 7:57am UTC](https://discourse.julialang.org/t/recursive-inner-functions-a-thousand-times-slower/85604/9 "2022-08-20T07:57:58Z")

</div>

No, the issue I had was that the recursive function needs access to ~twelve different variables from its scope, and what was killing performance was the recursive call itself rather than accesses to variables from inside the closure. I ended up using this macro:

```julia
macro closure_struct(name, args...)
    @assert isa(name, Symbol)
    @assert all(s->isa(s,Symbol), args)
    typenames = map(s->esc(Symbol(uppercase(string(s)))), args)
    type_args = Expr(:curly, esc(name), typenames...)
    body = Expr(:block, map(p -> Expr(:(::), p...), zip(args,typenames))...)
    decl = Expr(:struct, false, type_args, body)
    constructor = let
        lhs = Expr(:call, esc(name), Expr(:parameters, args...))
        rhs = Expr(:call, esc(name), args...)
        :($lhs = $rhs)
    end
    quote
        $decl
        $constructor
    end
end

```

That way you can define a recursive function with

```julia
@closure_struct _loop x y z

function (rec::_loop)(a::Int)::Int
    @unpack x, y, z = rec
    a > 0 ? rec(a-1) : a
end

```

at the top level, and then I can use it directly as `_loop(;x,y,z)(a)`.