# How the compiler decides which allocation is eliminated?
**URL:** https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127
**Category:** Internals & Design
**Created:** [November 26, 2024, 9:43pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127 "2024-11-26T21:43:20Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [November 26, 2024, 9:43pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/1 "2024-11-26T21:43:21Z")
Consider three functions:
```julia
foo1() = (Vector() ; 0)
foo2() = (Vector(undef, 2^50) ; 0)
foo3() = (Vector(undef, -1) ; 0)
```
On the current master, creation of `Vector` seems to be eliminated in `foo1`, `foo2`, and not eliminated in `foo3` :
```julia
julia> @code_native debuginfo=:none dump_module=false foo1()
.text
endbr64
mov rax, qword ptr [rcx + 56]
ret
nop dword ptr [rax]
julia> @code_native debuginfo=:none dump_module=false foo2()
.text
endbr64
mov rax, qword ptr [rcx + 56]
ret
nop dword ptr [rax]
julia> @code_native debuginfo=:none dump_module=false foo3()
.text
push rbp
mov rbp, rsp
mov rax, qword ptr [r13 + 16]
mov rax, qword ptr [rax + 16]
mov rax, qword ptr [rax]
movabs rax, offset jl_alloc_genericmemory
movabs rdi, offset jl_system_image_data
mov rsi, -1
call rax
xor eax, eax
pop rbp
ret
```
How does the compiler decide which code to eliminate here? Thanks for the answer!
I bring this example because both `foo2` and `foo3` (edit: _should_) have apparently observable effects (OOM and ArgumentError, resp.), yet the behaviour is different.
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 26, 2024, 10:04pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/2 "2024-11-26T22:04:33Z")
OutOfMemoryError is an error that isn’t modeled (i.e. the 2nd example runs if you have enough RAM). The difference between `foo2` and `foo3` is that `foo3` errors, while `foo2` is just sometimes run on a computer without good enough specs.
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [November 26, 2024, 10:24pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/3 "2024-11-26T22:24:09Z")
I see. I guess it is reasonable with OutOfMemoryError. Are there other errors that are not modeled?
A follow-up question: do you know why vector creation is not eliminated in `foo4` here :
(edit: what I mean is, if without the memory store the allocation can be eliminated, how does the memory store prevent elimination?)
```julia
julia> foo4() = (x = Vector{Int}(undef, 1); @inbounds x[1] = 1; 0)
foo4 (generic function with 1 method)
julia> @code_native debuginfo=:none dump_module=false foo4()
.text
push rbp
mov rbp, rsp
mov rax, qword ptr [r13 + 16]
mov rax, qword ptr [rax + 16]
mov rax, qword ptr [rax]
movabs rax, offset jl_alloc_genericmemory
movabs rdi, offset jl_system_image_data
mov esi, 1
call rax
mov rax, qword ptr [rax + 8]
mov qword ptr [rax], 1
xor eax, eax
pop rbp
ret
nop dword ptr [rax]
```
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 26, 2024, 10:37pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/4 "2024-11-26T22:37:55Z")
The only other error Jeff and I can think of that isn’t modeled is StackOverflow. (The reasoning is that ~any code theoretically can throw those, and they don’t exist within the Turing machine model of a machine).
For your followup, see [make `memorynew` intrinsic by oscardssmith · Pull Request #55913 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/55913) which does make `foo4` removable (but isn’t quite able to remove `foo5`)
```julia
function foo5()
v = Vector{Int}(undef, 2^50)
v[1] = 5
v[1]
end
```
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [November 26, 2024, 10:53pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/5 "2024-11-26T22:53:23Z")
> [@Oscar\_Smith](#):
>
> The only other error Jeff and I can think of that isn’t modeled is StackOverflow
Perhaps also `InterruptException`, in some sense? Say,
```julia
function foo6()
try
# Expected to run for a long time
for i in 1:2^30 end
catch
# We hope this runs when Ctrl + C is pressed
println("Interrupted, printing useful stats: ...")
end
end
julia> @code_native debuginfo=:none foo6()
.text
.file "foo6"
.section .ltext,"axl",@progbits
.globl julia_foo6_2370 # -- Begin function julia_foo6_2370
.p2align 4, 0x90
.type julia_foo6_2370,@function
julia_foo6_2370: # @julia_foo6_2370
; Function Signature: foo6()
# %bb.0: # %top
push rbp
mov rbp, rsp
xor eax, eax
pop rbp
ret
.Lfunc_end0:
```
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [November 26, 2024, 10:54pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/6 "2024-11-26T22:54:37Z")
> For your followup, see [make `memorynew` intrinsic by oscardssmith · Pull Request #55913 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/55913) which does make `foo4` removable
That is amazing.
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 26, 2024, 11:11pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/7 "2024-11-26T23:11:08Z")
> Perhaps also `InterruptException`
yeah, that too.
---
### Author:  [@giordano](https://discourse.julialang.org/u/giordano)
#### Post date: [November 26, 2024, 11:14pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/8 "2024-11-26T23:14:12Z")
> [@Oscar\_Smith](#):
>
> (but isn’t quite able to remove `foo5`)
Where’s the definition of `foo5`? Curiously, in this thread I only see `foo1`, `foo2`, `foo3`, `foo4`, and `foo6`.
---
### Author:  [@Keno](https://discourse.julialang.org/u/Keno)
#### Post date: [November 26, 2024, 11:16pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/9 "2024-11-26T23:16:30Z")
See [What to do about asynchronous exceptions · Issue #52291 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/52291) for discussion on asynchronous exceptions.
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 26, 2024, 11:24pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/10 "2024-11-26T23:24:13Z")
@giordano [How the compiler decides which allocation is eliminated? - #4 by Oscar\_Smith](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/4) has been edited so that the `foo4` that was supposed to be `foo5` is.
---
### Author:  [@giordano](https://discourse.julialang.org/u/giordano)
#### Post date: [November 26, 2024, 11:35pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/11 "2024-11-26T23:35:22Z")
```julia
julia> code_llvm((); debuginfo=:none) do
v = Vector{Int}(undef, 251)
v[1] = 5
v[1]
end
```
```llvm
; Function Signature: var"#110"()
define i64 @"julia_#110_4587"() #0 {
L37:
ret i64 5
}
```
```julia
julia> code_llvm((); debuginfo=:none) do
v = Vector{Int}(undef, 252)
v[1] = 5
v[1]
end
```
```llvm
; Function Signature: var"#113"()
define i64 @"julia_#113_4592"() #0 {
L37:
%pgcstack = call ptr inttoptr (i64 4333010700 to ptr)(i64 4333010736) #11
%ptls_field = getelementptr inbounds i8, ptr %pgcstack, i64 16
%ptls_load = load ptr, ptr %ptls_field, align 8
%"Memory{Int64}[]" = call ptr @jl_alloc_genericmemory_unchecked(ptr %ptls_load, i64 2016, ptr nonnull @"+Core.GenericMemory#4594.jit")
store i64 252, ptr %"Memory{Int64}[]", align 8
fence syncscope("singlethread") release
%memory_data_ptr = getelementptr inbounds { i64, ptr }, ptr %"Memory{Int64}[]", i64 0, i32 1
%memory_data = load ptr, ptr %memory_data_ptr, align 8
store i64 5, ptr %memory_data, align 8
ret i64 5
}
```
what happens at size 252 that makes the allocation stick? It’s also a weird cutoff value, not being an exact power of 2, or an adjacent number (although it’s nearby, for some definition of closeness)
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 26, 2024, 11:37pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/12 "2024-11-26T23:37:30Z")
the thing that happens is the allocation moves from being a pool allocation to a malloc (the weird size is that the number of bytes for the Memory is 16+8\*elsize), and dealing with that case would have required me to write another ~50 lines of LLVM to model the other allocation path, and I want to get an initial version of this merged and go from there.
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [November 26, 2024, 11:50pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/13 "2024-11-26T23:50:38Z")
> [@Oscar\_Smith](#):
>
> For your followup, see [make `memorynew` intrinsic by oscardssmith · Pull Request #55913 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/55913) which does make `foo4` removable (but isn’t quite able to remove `foo5`)
A layman question: if I understand right, the PR eagerly evaluates the allocation, sometimes. For eliminating the allocation and the store in `foo4`, should there be a more high-level mechanism? Say, since the array is local to that function, and there are no loads from the array, eliminate the stores (which are dead anyway), and then eliminate the allocation ?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 27, 2024, 12:11am UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/14 "2024-11-27T00:11:31Z")
The hardest part about this is proving that the array is local (especially because BoundsErrors currently escape the array).
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [November 27, 2024, 10:22am UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/15 "2024-11-27T10:22:02Z")
I see, thanks. I guess inbounds access is in fact proven, but is not used for optimization yet? Note `getelementptr inbounds` :
```julia
julia> function foo8()
b = Vector{Int}(undef, 3)
b[2] = 3
0
end
julia> @code_llvm debuginfo=:none foo8()
; Function Signature: foo8()
define i64 @julia_foo8_4126() #0 {
L18:
%"Memory{Int64}[]" = call ptr @jl_alloc_genericmemory(ptr nonnull @"+Core.GenericMemory#4128.jit", i64 3)
%memory_data_ptr = getelementptr inbounds { i64, ptr }, ptr %"Memory{Int64}[]", i64 0, i32 1
%memory_data = load ptr, ptr %memory_data_ptr, align 8
%memoryref_data4 = getelementptr inbounds i8, ptr %memory_data, i64 8
store i64 3, ptr %memoryref_data4, align 8
ret i64 0
}
```
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [November 27, 2024, 1:07pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/16 "2024-11-27T13:07:08Z")
you’re just seeing LLVM performing the proof of inboundsness. the reason why the memorynew pr is needed is LLVM doesn’t know that jl\_alloc\_genericmemory doesn’t leak the array it creates since it’s an arbitrary C function
---
### Author:  [@sadish-d](https://discourse.julialang.org/u/sadish-d)
#### Post date: [December 13, 2024, 4:57am UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/17 "2024-12-13T04:57:17Z")
I came across something similar with tuples today. Looks like the compiler skips the tuple creation in `g1` but not in `g2`:
```julia
g1() = (ntuple(i -> 1, 10); 0)
g2() = (ntuple(i -> 1, 11); 0)
@code_llvm debuginfo = :none g1()
# define i64 @julia_g1_1199() #0 {
# top:
# ret i64 0
# }
@code_llvm debuginfo = :none g2()
# define i64 @julia_g2_1211() #0 {
# top:
# %0 = call nonnull {}* @j__ntuple_1213(i64 signext 11)
# ret i64 0
# }
```
---
### Author:  [@danielwe](https://discourse.julialang.org/u/danielwe)
#### Post date: [December 13, 2024, 5:48am UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/18 "2024-12-13T05:48:37Z")
Take a look at the implementation of `ntuple` ([julia/base/ntuple.jl at v1.11.2 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/blob/v1.11.2/base/ntuple.jl#L17-L38)):
```julia
@inline function ntuple(f::F, n::Integer) where F
# marked inline since this benefits from constant propagation of `n`
t = n == 0 ? () :
n == 1 ? (f(1),) :
n == 2 ? (f(1), f(2)) :
n == 3 ? (f(1), f(2), f(3)) :
n == 4 ? (f(1), f(2), f(3), f(4)) :
n == 5 ? (f(1), f(2), f(3), f(4), f(5)) :
n == 6 ? (f(1), f(2), f(3), f(4), f(5), f(6)) :
n == 7 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7)) :
n == 8 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8)) :
n == 9 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9)) :
n == 10 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9), f(10)) :
_ntuple(f, n)
return t
end
function _ntuple(f::F, n) where F
@noinline
(n >= 0) || throw(ArgumentError(LazyString("tuple length should be ≥ 0, got ", n)))
([f(i) for i = 1:n]...,)
end
```
The outer function will be inlined, and since `n` is a compile-time constant the branches are eliminated. For `n <= 10` that only leaves a hardcoded tuple instantiation, which is clearly side-effect-free and can be eliminated. For `n > 10` what’s left is a call to a type-unstable inner function that allocates an intermediate array and has a branch that throws. So I think your observation is explained by the completely different code you end up with in the two cases, rather than general compiler heuristics with regard to tuples.
---
### Author:  [@sadish-d](https://discourse.julialang.org/u/sadish-d)
#### Post date: [December 13, 2024, 3:12pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/19 "2024-12-13T15:12:12Z")
Makes sense. I guess the compiler can’t get rid of the tuple creation because it could throw an error. If you lie and tell it that creating the tuple never throws an error, it seems to get rid of it and any accompanying intermediate array creation.
```julia
function f()
Base.@assume_effects :nothrow g() = ntuple(i -> 1, 11)
g()
return 0
end
@code_llvm debuginfo = :none f()
# define i64 @julia_f_884() #0 {
# top:
# ret i64 0
# }
```
---
### Author:  [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [December 13, 2024, 3:41pm UTC](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127/20 "2024-12-13T15:41:51Z")
If you used `ntuple(f, Val(N))` instead, then it’ll compile away from any(?) `N`.
```julia-repl
julia> g3() = (ntuple(i -> 1, Val(11)); 0);
julia> @code_llvm g3()
; Function Signature: g3()
; @ REPL[27]:1 within `g3`
define i64 @julia_g3_20024() #0 {
top:
ret i64 0
}
```
```julia-repl
julia> g4() = (ntuple(i -> 1, Val(111)); 0);
julia> @code_llvm g4()
; Function Signature: g4()
; @ REPL[29]:1 within `g4`
define i64 @julia_g4_20028() #0 {
top:
ret i64 0
}
```
[Next page](https://discourse.julialang.org/t/how-the-compiler-decides-which-allocation-is-eliminated/123127.md?page=2)