# Why do these allocate?!
**URL:** https://discourse.julialang.org/t/why-do-these-allocate/105497
**Category:** Performance
**Tags:** tuple, memory-allocation, recursion
**Created:** [October 28, 2023, 10:39am UTC](https://discourse.julialang.org/t/why-do-these-allocate/105497 "2023-10-28T10:39:08Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@nsajko](https://discourse.julialang.org/u/nsajko)
#### Post date: [October 28, 2023, 10:39am UTC](https://discourse.julialang.org/t/why-do-these-allocate/105497/1 "2023-10-28T10:39:08Z")
The functions `shuf1` and `shuf2` are two different implementations of a Fisher-Yates shuffle for tuples. Why do both allocate, even in trivial cases? The recursion depth should be small and a compile-time constant and all types should likewise be inferrable, as far as I understand.
```julia
err_bounds(t::Tuple, i::Integer) = throw(BoundsError(t, i))
without_elem_at_index(t::Tuple{}, i::Integer) = err_bounds(t, i)
axis(c) = (only ∘ axes)(c)
function without_elem_at_index(t::Tuple{Any,Vararg{Any,n}}, i::Integer) where {n}
(i ∈ axis(t)) || err_bounds(t, i)
f = let t = t, i = i
j -> (j < i) ? t[j] : t[j + 1]
end
ntuple(f, Val(n))::NTuple{n,eltype(t)}
end
struct CatL end
struct CatR end
cat(t::Tuple, e, ::CatL = CatL()) = (e, t...)
cat(t::Tuple, e, ::CatR) = (t..., e)
shuf1(::Type, ::Any, r::Tuple, ::Tuple{}) = r
shuf1(::Type, ::Any, r::Tuple, s::Tuple{Any}) = cat(r, only(s))
function shuf1(::Type{T}, prg, r::Tuple, s::Tuple{Any,Any,Vararg{Any,n}}) where {T, n}
i = rand(prg, Base.OneTo(T(n + 2)::T))::T
done = cat(r, s[i])
todo = without_elem_at_index(s, i)
shuf1(T, prg, done, todo)
end
shuf2(::Type, ::Any, ::Tuple{}) = ()
function shuf2(::Type{T}, prg, t::Tuple{Any,Vararg{Any,n}}) where {T, n}
i = rand(prg, Base.OneTo(T(n + 1)::T))::T
todo = without_elem_at_index(t, i)
cat(shuf2(T, prg, todo), t[i])
end
using Random
shuf1(prg, t::Tuple) = shuf1(UInt8, prg, (), t)
shuf2(prg, t::Tuple) = shuf2(UInt8, prg, t)
let t = ntuple((_ -> rand()), Val(1)), prg = Xoshiro()
shuf1(prg, t)
shuf2(prg, t)
@allocated shuf1(prg, t)
@allocated shuf2(prg, t)
println(@allocated shuf1(prg, t))
println(@allocated shuf2(prg, t))
end
```
The behavior is the same with v1.9, v1.10, v1.11:
```julia-repl
julia> include("/tmp/mre.jl")
16
16
```
Doing something like this doesn’t even show my code in the stack, and it ends with a `Tuple{Float64}` GC entry:
```julia
let prg = Xoshiro(), t = (0.3,)
@profview_allocs shuf1(prg, t) sample_rate=1
end
```
---
### Author:  [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [October 28, 2023, 11:33am UTC](https://discourse.julialang.org/t/why-do-these-allocate/105497/2 "2023-10-28T11:33:11Z")
This seems to be some sort of artifact caused by `let` blocks being similar to, but not quite the same as a function body.
```julia
julia> let t = ntuple((_ -> rand()), Val(1)), prg = Xoshiro()
shuf1(prg, t)
shuf2(prg, t)
@allocated shuf1(prg, t)
@allocated shuf2(prg, t)
println(@allocated shuf1(prg, t))
println(@allocated shuf2(prg, t))
end
16
16
julia> let t = ntuple((_ -> rand()), Val(1)), prg = Xoshiro()
shuf1(prg, t)
shuf2(prg, t)
@allocated shuf1(prg, t)
@allocated shuf2(prg, t)
println(@allocated shuf1(prg, t))
println(@allocated shuf2(prg, t))
end
16
16
```
vs
```julia
julia> function foo(t = ((_ -> rand()), Val(1)), prg = Xoshiro())
shuf1(prg, t)
shuf2(prg, t)
@allocated shuf1(prg, t)
@allocated shuf2(prg, t)
println(@allocated shuf1(prg, t))
println(@allocated shuf2(prg, t))
end
foo (generic function with 1 method)
julia> foo()
0
1179901
julia> foo()
0
0
```
I think it’s something to do with a specialization being missed, but it’s hard to say since the code generated by `let` blocks is harder to inspect than functions.
---
### Author:  [@nsajko](https://discourse.julialang.org/u/nsajko)
#### Post date: [October 28, 2023, 12:01pm UTC](https://discourse.julialang.org/t/why-do-these-allocate/105497/3 "2023-10-28T12:01:55Z")
> [@Mason](#):
>
> ```julia
> julia> foo()
> 0
> 0
>
> ```
This is very interesting, however, when I replace the `let` block at the end of my example code with this, I still get `16` in all four lines of output:
```julia
t = ntuple((_ -> rand()), Val(1))
prg = Xoshiro()
shuf1(prg, t)
shuf2(prg, t)
@allocated shuf1(prg, t)
@allocated shuf2(prg, t)
println(@allocated shuf1(prg, t))
println(@allocated shuf2(prg, t))
println(@allocated shuf1(prg, t))
println(@allocated shuf2(prg, t))
```
So would this be an `@allocated` bug, then?
---
### Author:  [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [October 28, 2023, 12:11pm UTC](https://discourse.julialang.org/t/why-do-these-allocate/105497/4 "2023-10-28T12:11:54Z")
No, that’s just the natural result of accessing untyped global variables. If you enforce a type restriction it’s fine:
```julia
julia> t::Tuple{Float64} = ntuple((_ -> rand()), Val(1))
(0.42291917892985276,)
julia> prg::Xoshiro = Xoshiro()
Xoshiro(0xb6e71365f6eee4b4, 0x910e9e67004ff2d6, 0xb2e25798af336d03, 0x0f20f906d9d2ef02, 0x526573c658a46753)
```
```julia
julia> shuf1(prg, t)
(0.42291917892985276,)
julia> shuf2(prg, t)
(0.42291917892985276,)
julia> @allocated shuf1(prg, t)
0
julia> @allocated shuf2(prg, t)
0
julia> println(@allocated shuf1(prg, t))
0
julia> println(@allocated shuf2(prg, t))
0
julia> println(@allocated shuf1(prg, t))
0
julia> println(@allocated shuf2(prg, t))
0
```
---
### Author:  [@nsajko](https://discourse.julialang.org/u/nsajko)
#### Post date: [October 28, 2023, 12:58pm UTC](https://discourse.julialang.org/t/why-do-these-allocate/105497/5 "2023-10-28T12:58:36Z")
FTR `shuf1` still allocates for nontrivial tuple lengths. But I guess that’s OK for me given that `shuf2` is a simpler implementation anyway.