# Compiler recursion limit

**URL:** <https://discourse.julialang.org/t/compiler-recursion-limit/112698>\
**Category:** General Usage\
**Tags:** tuple, compilation, recursion\
**Created:** [April 8, 2024, 9:13pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698 "2024-04-08T21:13:02Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [April 8, 2024, 9:13pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/1 "2024-04-08T21:13:02Z")

</div>

I’ve written some recursive code that compiles away due to (I believe) constant propagation. However, I’m afraid that if I run the code on a larger problem I will hit a compiler recursion limit and it will no longer compile away. Does anyone have a rule of thumb for how deep your code can recurse before compiler inference gives up and infers `Any`?

I know, I know, you probably want to see a MWE. I do have one, but it’s in a repo that is currently private, so I’d prefer not to share it at this time. If there is no precise number, like a `JULIA_INFERENCE_RECURSION_LIMIT`, a rule of thumb will do.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 9, 2024, 6:45am UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/2 "2024-04-09T06:45:28Z")

</div>

Maybe a very simple test case can help answer?

```julia
julia> using Test

julia> f(::Val{0}) = 0
f (generic function with 1 method)

julia> f(::Val{N}) where {N} = f(Val{N-1}())
f (generic function with 2 methods)

julia> @inferred f(Val(10))
0

julia> @inferred f(Val(100))
0

julia> @inferred f(Val(1000))
Internal error: stack overflow in type inference of f(Base.Val{1000}).
This might be caused by recursion over very long tuples or argument lists.
0

```

However I assume the compiler behavior is more complex, and typically depends on the actual function involved.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [April 9, 2024, 12:16pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/3 "2024-04-09T12:16:06Z")

</div>

Ok, here’s my example. I wrote a function `topo_sort` that does a topological sort on a tuple of singleton types. There is a DAG relationship among the types, which is defined by overloads of a `children` function.

Here’s the implementation:

```julia
function in_tuple(x::S, t::Tuple{T, Vararg}) where {S, T}
    S === T || in_tuple(x, Base.tail(t))
end

in_tuple(::T, t::Tuple{T, Vararg}) where {T} = true
in_tuple(_, t::Tuple{}) = false

function visit_node(order::Tuple, x)
    in_tuple(x, order) && return order
    new_order = visit_children(order, children(x))
    (x, new_order...)
end

function visit_children(order::Tuple, children::Tuple)
    new_order = visit_node(order, children[1])
    visit_children(new_order, Base.tail(children))
end

visit_children(order::Tuple, ::Tuple{}) = order

topo_sort(to_visit::Tuple) = _topo_sort((), to_visit)

function _topo_sort(order::Tuple, to_visit::Tuple)
    new_order = visit_node(order, to_visit[1])
    _topo_sort(new_order, Base.tail(to_visit))
end

_topo_sort(order::Tuple, unvisited::Tuple{}) = order

```

I’ve come up with a fairly simple example DAG that sometimes compiles away and sometimes does not, depending on the order that I provide the singleton types to the `topo_sort` function. Here’s the DAG:

```julia
struct A end
struct B end
struct C end
struct D end
struct E end
struct F end
struct G end

children(::A) = (B(), C())
children(::B) = (D(), )
children(::C) = (D(), )
children(::D) = (E(), )
children(::E) = (F(), )
children(::F) = (G(), )
children(::G) = ()

```

And here we can see that sometimes `topo_sort` compiles away, and sometimes it does not:

```julia-repl
julia> using Test 

julia> @code_typed topo_sort((A(), B(), C(), D(), E(), F(), G()))
CodeInfo(
1 ─ return (A(), C(), B(), D(), E(), F(), G())
) => Tuple{A, C, B, D, E, F, G}

julia> @inferred topo_sort((A(), B(), C(), D(), E(), F(), G()))
(A(), C(), B(), D(), E(), F(), G())

julia> @code_typed topo_sort((C(), F(), B(), A(), D(), E(), G()))
CodeInfo(
1 ─ %1 = invoke Main._topo_sort((C(), D(), E(), F(), G())::Tuple{C, D, E, F, G}, (B(), A(), D(), E(), G())::Tuple{B, A, D, E, G})::Tuple{Any, Vararg{Any}}
└── return %1
) => Tuple{Any, Vararg{Any}}

julia> @inferred topo_sort((C(), F(), B(), A(), D(), E(), G()))
ERROR: return type Tuple{A, B, C, D, E, F, G} does not match inferred return type Tuple{Any, Vararg{Any}}

```

Is there any way my implementation can be improved so that it is more likely to constant propagate in a wider variety of situations?

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [April 9, 2024, 1:05pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/4 "2024-04-09T13:05:00Z")

</div>

I don’t know if this is acceptable in your situation, but if you use `@assume_effects`,

```julia
Base.@assume_effects :total topo_sort(to_visit::Tuple) = _topo_sort((), to_visit)

```

then inference works:

```julia
julia> @inferred topo_sort((C(), F(), B(), A(), D(), E(), G()))
(A(), B(), C(), D(), E(), F(), G())

```

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [April 9, 2024, 1:14pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/5 "2024-04-09T13:14:46Z")

</div>

For recursive tuple code like this, my rule of thumb is that the arguments should be _decreasing_ in complexity on each recursive step. In other words, the red flag here is that (I think) your `new_order` is getting longer, whereas you want things that get shorter (like `children`).

I’m not sure how you’d refactor this to achieve that, unfortunately.

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [April 9, 2024, 5:07pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/6 "2024-04-09T17:07:55Z")

</div>

> [@CameronBieganek](#):
>
> I’ve written some recursive code that compiles away due to (I believe) constant propagation. However, I’m afraid that if I run the code on a larger problem I will hit a compiler recursion limit and it will no longer compile away. Does anyone have a rule of thumb for how deep your code can recurse before compiler inference gives up and infers `Any`?

The compiler [won’t stop inferring recursive types](https://discourse.julialang.org/t/julia-never-stops-compiling-for-new-recursive-vector-types/110232/19), and the inference process appears to be linear to the depth of the type currently. Which would make complete inference quadratic to the depth of the actual recursive structure: you don’t want this. You would end up with a complete copy of the tree structure inhabiting the type system, very slowly, and to no benefit.

The available solutions depend on the details of the type, but revolve around partially-parameterizing at some point in the process, or insisting on `Any`.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [April 10, 2024, 1:52am UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/7 "2024-04-10T01:52:07Z")

</div>

Here’s an interesting related example. Suppose we already have a tuple `order` that contains a topological sort of singleton structs, and we have a smaller tuple `xs` with a subset of the full topological sort (with no duplicates). However, the elements in `xs` are not topologically sorted. What we would like to do is return a new tuple where the elements of `xs` are topologically sorted. We can do this with the following recursive code.

**Implementation:**

```julia
function in_tuple(x::S, t::Tuple{T, Vararg}) where {S, T}
    S === T || in_tuple(x, Base.tail(t))
end

in_tuple(::T, t::Tuple{T, Vararg}) where {T} = true
in_tuple(_, t::Tuple{}) = false

Base.@assume_effects :total function tuple_topo_sort(order, match, xs)
    if length(match) == length(xs)
        return match
    end

    first = order[1]

    if in_tuple(first, xs)
        tuple_topo_sort(Base.tail(order), (match..., first), xs)
    else
        tuple_topo_sort(Base.tail(order), match, xs)
    end
end

```

**Test case:**

```julia
using Test
using BenchmarkTools

for i in 1:100
    sym = Symbol("A$i")
    @eval struct $sym end
end

order_vec = map(1:100) do i
    sym = Symbol("A$i")
    eval(:($sym()))
end

order = tuple(order_vec...)

```

The `tuple_topo_sort` function is inferred for this example:

```julia-repl
julia> @inferred tuple_topo_sort(order, (), (A75(), A50(), A25()))
(A25(), A50(), A75())

```

However, it does not completely compile away:

```julia-repl
julia> @code_typed tuple_topo_sort(order, (), (A75(), A50(), A25()))
CodeInfo(
1 ─ nothing::Nothing
│ nothing::Nothing
│ Core._apply_iterate(Base.iterate, Base.argtail, order)::Tuple{A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21, A22, A23, A24, A25, A26, A27, A28, A29, A30, A31, A32, A33, A34, A35, A36, A37, A38, A39, A40, A41, A42, A43, A44, A45, A46, A47, A48, A49, A50, A51, A52, A53, A54, A55, A56, A57, A58, A59, A60, A61, A62, A63, A64, A65, A66, A67, A68, A69, A70, A71, A72, A73, A74, A75, A76, A77, A78, A79, A80, A81, A82, A83, A84, A85, A86, A87, A88, A89, A90, A91, A92, A93, A94, A95, A96, A97, A98, A99, A100}
└── return (A25(), A50(), A75())
) => Tuple{A25, A50, A75}

```

We can see a `Core._apply_iterate` in there, and we can see its affect on the runtime of `tuple_topo_sort`:

```julia-repl
julia> @btime tuple_topo_sort(order, (), (A75(), A50(), A25()));
  3.030 μs (0 allocations: 0 bytes)

```

Any ideas on how to get this case to completely compile away?

---

<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:** [April 10, 2024, 8:39am UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/8 "2024-04-10T08:39:15Z")

</div>

> [@CameronBieganek](#):
>
> `Base.tail(t)`

> [@CameronBieganek](#):
>
> `Base.argtail`

I may look more deeply into this later, but I suggest you try what I did in TupleSorting.jl. In [`src/TupleUtils.jl`](https://gitlab.com/nsajko/TupleSorting.jl/-/blob/8d521b802c767697f9cf96eb47a19a7e57315f26/src/TupleUtils.jl#L28-34) there’s a short `tup_tail` method which is a replacement for `Base.tail` based on `ntuple` instead of on `argtail`.

There’s also a PR: [add a `Base.tail` method for nonempty tuples by nsajko · Pull Request #52035 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/52035)

You might also be interested to see the implementation of `ntuple(::Any, ::Val)`, which is basically this (look in `base/ntuple.jl` in the Julia source), I slightly simplified by removing the `@generated` branch:

```julia
function ntuple(f::F, ::Val{N}) where {F,N}
    N::Int
    (N >= 0) || throw(ArgumentError(LazyString("tuple length should be ≥ 0, got ", N)))
    Tuple(f(i) for i = 1:N)
end

```

Side note: it’s a bit annoying seeing all the trade offs between compilation cost, sysimage size, etc. on one side and runtime performance on the other that Julia Base and the Julia ecosystem have to make. There should be a way to somehow allow users to opt into maximum runtime performance while still using largely the same code paths.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [April 10, 2024, 12:24pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/9 "2024-04-10T12:24:59Z")

</div>

Awesome, that worked! Thanks, @nsajko. Here’s the complete script:

> **Code**
>
> ```julia
> using Test
> using BenchmarkTools
> 
> function tail(x::Tuple{Any, Vararg{Any, N}}) where {N}
> f = let x = x
> i -> x[i + 1]
> end
> ntuple(f, Val(N))::NTuple{N, Any}
> end
> 
> function in_tuple(x::S, t::Tuple{T, Vararg}) where {S, T}
> S === T || in_tuple(x, tail(t))
> end
> 
> in_tuple(::T, t::Tuple{T, Vararg}) where {T} = true
> in_tuple(_, t::Tuple{}) = false
> 
> Base.@assume_effects :total function tuple_topo_sort(order, match, xs)
> if length(match) == length(xs)
> return match
> end
> 
> first = order[1]
> 
> if in_tuple(first, xs)
> tuple_topo_sort(tail(order), (match..., first), xs)
> else
> tuple_topo_sort(tail(order), match, xs)
> end
> end
> 
> for i in 1:100
> sym = Symbol("A$i")
> @eval struct $sym end
> end
> 
> order_vec = map(1:100) do i
> sym = Symbol("A$i")
> eval(:($sym()))
> end
> 
> order = tuple(order_vec...)
> xs = (A75(), A50(), A25())
> 
> ```

Testing it in the REPL:

```julia-repl
julia> @inferred tuple_topo_sort(order, (), xs)
(A25(), A50(), A75())

julia> @code_typed tuple_topo_sort(order, (), xs)
CodeInfo(
1 ─ nothing::Nothing
│ nothing::Nothing
└── return (A25(), A50(), A75())
) => Tuple{A25, A50, A75}

julia> @btime tuple_topo_sort($order, (), $xs);
  1.432 ns (0 allocations: 0 bytes)

julia> bar(::Tuple{A25, A50, A75}) = 42;

julia> foo(order, xs) = bar(tuple_topo_sort(order, (), xs));

julia> @code_typed foo(order, xs)
CodeInfo(
1 ─ return 42
) => Int64

julia> @btime foo($order, $xs);
  1.432 ns (0 allocations: 0 bytes)

```

(Regarding the original topological sort, I realized that for my problem I can just keep an `order` tuple around and when new structs are added to the DAG I can insert them into the correct location in `order`, and that operation is not performance sensitive.)

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [April 17, 2024, 11:40pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/10 "2024-04-17T23:40:40Z")

</div>

> [@CameronBieganek](#):
>
> I’m afraid that if I run the code on a larger problem I will hit a compiler recursion limit and it will no longer compile away.

Any recursion will blow the stack in the end. Is that how you know a segfauly or something? You can change it with ulimit -s (not sure how on Windows; from within a process with setrlimit and maybe it’s cross-platform).

I didn’t know Python had this limitation/and this solution:

> **[How to Fix RecursionError in Python](https://rollbar.com/blog/python-recursionerror/#)**
>
> The Python RecursionError is an exception that occurs when the maximum recursion depth is exceeded. Learn how to fix it.

> Increasing the recursion limit: Python has a default maximum recursion depth of 1000. If a function exceeds this limit, it can be increased using the `sys.setrecursionlimit(n)` function.

I doubt Julia has any specific limitations except what the hardware, or rather OS gives you. At least not in general, but maybe for compilation specifically (but why would it?).

> [@CameronBieganek](#):
>
> I’ve written some recursive code that compiles away due to (I believe) constant propagation.

Interesting. Julia scales badly on this benchmark (because of constant propagation if I recall) from my friend Per: [GitHub - nordlow/compiler-benchmark: Benchmarks compilation speeds of different combinations of languages and compilers.](https://github.com/nordlow/compiler-benchmark)

The code and benchmark there is highly unusual, just to exercise the compiler, not for real-world code, so I don’t (and others) do not care enough. I believe the issue would go away on -O0 if it really meant no optimizations, as for other languages. I understand constant propagation is the only (or one of few) done on -O0.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [April 17, 2024, 11:52pm UTC](https://discourse.julialang.org/t/compiler-recursion-limit/112698/11 "2024-04-17T23:52:55Z")

</div>

> [@Palli](#):
>
> I doubt Julia has any specific limitations except what the hardware, or rather OS gives you. At least not in general, but maybe for compilation specifically (but why would it?).

The Julia compiler does eventually give up on inference for recursive and mutually recursive functions because otherwise the compile times could blow up. However, as @matthias314 pointed out, careful use of `Base.@assume_effects` can convince the compiler to keep inferring. I haven’t played around with the different settings yet, but my hypothesis is that the `:terminates_globally` setting by itself might be enough to get the compiler to completely infer a recursive function.