# Memory allocation in recursion
**URL:** https://discourse.julialang.org/t/memory-allocation-in-recursion/111929
**Category:** Performance
**Tags:** recursion
**Created:** [March 21, 2024, 1:00am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929 "2024-03-21T01:00:50Z")
**Posts on this page:** 12
**Page:** 1
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2024, 1:00am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/1 "2024-03-21T01:00:50Z")
Does Julia allocate memory when recursing? I see a ton of memory allocation
in a recursive quicksort…
---
### Author:  [@Elrod](https://discourse.julialang.org/u/Elrod)
#### Post date: [March 21, 2024, 2:01am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/2 "2024-03-21T02:01:39Z")
No, you shouldn’t be seeing heap allocations when recursing, unless your function heap allocates regardless.
Often, inference will fail when types change on recursion and the compiler can’t prove the recursion/type changes terminate.
Do you have inference failures?
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2024, 2:54am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/3 "2024-03-21T02:54:12Z")
No flagged problems in @code\_warntype output. It is a puzzle…
---
### Author:  [@Elrod](https://discourse.julialang.org/u/Elrod)
#### Post date: [March 21, 2024, 3:39am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/4 "2024-03-21T03:39:00Z")
Do you have a minimal reproducer?
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [March 21, 2024, 10:37am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/5 "2024-03-21T10:37:19Z")
> [@Recursion in Julia — bad idea?](https://discourse.julialang.org/t/recursion-in-julia-bad-idea/99304/11):
>
> Next level: perfect to learn about tail recursion and it’s optimization.
I was about to say “but julia doesn’t do TCO”. But you’re absolutely right, it is both educational and more readable / honest / transparent to write
```julia-auto
function foo(x,y,x)
#...
return foo(a,b,c) # tail-call
#...
end
```
as
```julia-auto
function foo(x,y,z)
@label entry
#...
x,y,z = a,b,c
@goto entry
#...
end
```
> [@PetrKryslUCSD](#):
>
> I see a ton of memory allocation in a recursive quicksort…
I would not be surprised if the recursion stumped escape analysis and caused views to be allocated instead of SROA-ed.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [March 21, 2024, 11:43am UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/6 "2024-03-21T11:43:07Z")
> [@foobar\_lv2](#):
>
> I would not be surprised if the recursion stumped escape analysis and caused views to be allocated instead of SROA-ed.
No, there’s no problem with views and recursion in general — we combine the two all the time. For example here is a recursive implementation of pairwise summation with views:
```julia
julia> using BenchmarkTools
julia> function foo(a)
n = length(a)
n ≤ 1 && return sum(a)
n2 = n >> 1
@views return foo(a[1:n2]) + foo(a[n2+1:end])
end
foo (generic function with 1 method)
julia> a = rand(1000);
julia> @btime foo($a);
11.377 μs (0 allocations: 0 bytes)
```
(It’s slow because I didn’t coarsen the base case, but it doesn’t allocate.)
Really, it’s pointless to speculate about why @PetrKryslUCSD is seeing allocations without seeing example code. But allocations are certainly not an inherent price of recursion.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2024, 2:28pm UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/7 "2024-03-21T14:28:22Z")
The code (`batch.jl`):
```julia
module PQuickSort
using LinearAlgebra
@inline function _partition!(A, perm, pivot, left,right)
@inbounds while left <= right
while A[left] < pivot
left += 1
end
while A[right] > pivot
right -= 1
end
if left <= right
A[left], A[right] = A[right], A[left]
perm[left], perm[right] = perm[right], perm[left]
left += 1
right -= 1
end
end
return (left,right)
end
function quicksortperm!(A, perm, i=1, j=length(A))
if j > i
left, right = _partition!(A, perm, A[(j+i) >>> 1], i, j)
quicksortperm!(A, perm, i, right)
quicksortperm!(A, perm, left, j)
end
end
function __pquicksortperm!(A, perm, i, j, task)
if task <= 0
quicksortperm!(A, perm, i, j)
return
end
left, right = _partition!(A, perm, A[(j+i) >>> 1], i, j)
t = Threads.@spawn __pquicksortperm!(A, perm, $i, $right, task - 1)
__pquicksortperm!(A, perm, left, j, task - 1)
wait(t)
return
end
# This has the same order of the arguments as the built in sortperm!
function pquicksortperm!(perm, A, ntasks = Threads.nthreads())
__pquicksortperm!(A, perm, 1, length(A), ntasks)
end
end # module
using LinearAlgebra
using Main.PQuickSort
function g()
N = 960_000_000
# N = 10
a = collect((N):-1:1)
p = similar(a)
@time sortperm!(p, a)
# @show a, prm
aref = sort(deepcopy(a))
a = collect((N):-1:1)
prm = collect(1:length(a))
@time PQuickSort.pquicksortperm!(prm, a)
# @show a, prm
norm(a - sort(aref)) == 0
a = collect((N):-1:1)
prm = collect(1:length(a))
@time PQuickSort.pquicksortperm!(prm, a)
end
```
This is what I see:
```julia
sorting % ../julia-1.10.0/bin/julia -t 1
julia> include("batch.jl")
g (generic function with 1 method)
julia> g()
1.764360 seconds
12.726564 seconds (686 allocations: 47.734 KiB, 0.01% compilation time)
12.728211 seconds (5 allocations: 528 bytes)
julia> g()
1.771723 seconds
12.724387 seconds (5 allocations: 528 bytes)
12.751161 seconds (5 allocations: 528 bytes)
julia>
sorting % ../julia-1.10.0/bin/julia -t 4
_
julia> include("batch.jl")
g (generic function with 1 method)
julia> g()
1.765504 seconds
3.860578 seconds (756 allocations: 54.953 KiB, 0.06% compilation time)
3.834740 seconds (75 allocations: 7.734 KiB)
julia>
sorting % ../julia-1.10.0/bin/julia -t 8
julia> include("batch.jl")
g (generic function with 1 method)
julia> g()
1.764240 seconds
2.564240 seconds (1.96 k allocations: 178.703 KiB, 0.09% compilation time)
2.506170 seconds (1.27 k allocations: 131.484 KiB)
julia> g()
1.572977 seconds
2.533586 seconds (1.27 k allocations: 131.484 KiB)
2.469899 seconds (1.27 k allocations: 131.484 KiB)
julia> g()
1.572899 seconds
2.531733 seconds (1.27 k allocations: 131.484 KiB)
2.476805 seconds (1.27 k allocations: 131.484 KiB)
julia>
sorting % ../julia-1.10.0/bin/julia -t 16
julia> include("batch.jl")
g (generic function with 1 method)
julia> g()
1.763108 seconds
1.939059 seconds (328.39 k allocations: 34.418 MiB, 0.12% compilation time)
1.908631 seconds (327.71 k allocations: 34.465 MiB)
julia> g()
1.563598 seconds
1.930559 seconds (327.71 k allocations: 34.130 MiB)
1.885926 seconds (327.68 k allocations: 33.367 MiB)
julia>
```
Platform:
```julia
julia> versioninfo()
Julia Version 1.10.0
Commit 3120989f39b (2023-12-25 18:01 UTC)
Build Info:
Official https://julialang.org/ release
Platform Info:
OS: macOS (arm64-apple-darwin22.4.0)
CPU: 24 × Apple M2 Ultra
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-15.0.7 (ORCJIT, apple-m1)
Threads: 2 on 16 virtual cores
```
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [March 21, 2024, 3:38pm UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/8 "2024-03-21T15:38:43Z")
Have you tried it without `Threads.@spawn` to check whether the allocations are just due to the threading?
---
### Author:  [@mnemnion](https://discourse.julialang.org/u/mnemnion)
#### Post date: [March 21, 2024, 3:53pm UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/9 "2024-03-21T15:53:54Z")
> [@foobar\_lv2](#):
>
> I was about to say “but julia doesn’t do TCO”.
Nothing new can be said about TCO and Julia at this point, but please bear in mind that self-recursion is the only use of TCO which can be transformed into a loop or labeled goto. It is among the less interesting applications. Dynamic programming and continuation-passing style both call for mutual recursion, where “mutual” can extend to dozens of functions.
So I hope someone finds the energy to add _explicit_ tail calls to Julia. It would be a good addition to the language. Some of the arguments against doing it implicitly and automatically are good ones, but there’s no case to be made against providing the ability to eliminate a tail call explicitly.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [March 21, 2024, 5:36pm UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/10 "2024-03-21T17:36:42Z")
> [@mnemnion](#):
>
> Dynamic programming and continuation-passing style both call for mutual recursion
Dynamic programming (which can involve either mutual or self recursion) doesn’t necessarily (or even usually) involve tail calls. Ditto for many other applications of mutual recursion. (And mutually recursive tail calls can still be written as an imperative loop, albeit with a merged function body.)
But yes, the possibility of an [explicit tail-call annotation](https://github.com/JuliaLang/julia/issues/4964#issuecomment-961932928) has been raised before, e.g. for people who want to write in functional styles such as continuation passing.
And of course, this has nothing to do with the code the OP of this thread is concerned with, which isn’t a tail call.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2024, 5:46pm UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/11 "2024-03-21T17:46:44Z")
You are right. It was the thread spawning. Seems I seriously miscalculated how many threads were going to be spawned.
---
### Author:  [@mnemnion](https://discourse.julialang.org/u/mnemnion)
#### Post date: [March 21, 2024, 8:08pm UTC](https://discourse.julialang.org/t/memory-allocation-in-recursion/111929/12 "2024-03-21T20:08:27Z")
> [@stevengj](#):
>
> Dynamic programming (which can involve either mutual or self recursion) doesn’t necessarily (or even usually) involve tail calls.
Many, even most, interesting dynamic programming techniques, can be implemented to use tail calls. Schemers have made a specialty of this, for obvious reasons. Of course, if they aren’t available in the first place, there’s no point.
> [@stevengj](#):
>
> Ditto for many other applications of mutual recursion. (And mutually recursive tail calls can still be written as an imperative loop, albeit with a merged function body.)
At the limit this boils down to a [well known finding](https://en.wikipedia.org/wiki/Turing_completeness) that any system which meets certain minimal standards can run any program.
Anything I do in Julia which uses multiple dispatch, for a less general example, I could write in a language which doesn’t have it. But it’s a very nice feature to have. When you talk about a merged function body, that’s manually writing a state machine with a bunch of labels and goto. Hardly a satisfactory solution. One might even say that writing efficient state machines which aren’t a single function containing a maze of gotos is the main value of tail call elimination!
> [@stevengj](#):
>
> But yes, the possibility of an [explicit tail-call annotation](https://github.com/JuliaLang/julia/issues/4964#issuecomment-961932928) has been raised before, e.g. for people who want to write in functional styles such as continuation passing.
Yeah I think that’s a great proposal… but it’s closed, and the only way it gets opened again is if people keep speaking up. Continuation-passing style is a choice way to write interpreters, and involves a tail call pretty much by definition. The alternatives are consuming the stack, or writing the entire interpreter as a single state machine (see above), and neither of those are good.
Or writing a bytecode interpreter with its own stack, but now we’re implementing a different program because we can’t write the one we want. Also no bueno.
> [@stevengj](#):
>
> And of course, this has nothing to do with the code the OP of this thread is concerned with, which isn’t a tail call.
I was a bit confused where the bit about TCO came from in the first place, yes. But here we are. Julia certainly _stack allocates_ memory in recursion, even when it doesn’t have to, and with no way of preventing it other than to not use recursion.
Anyway. Back to your regularly scheduled, um, program.