# Preallocated variable length buffer with known maximum length

**URL:** <https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550>\
**Category:** General Usage\
**Created:** [August 8, 2020, 6:30am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550 "2020-08-08T06:30:50Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 6:30am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/1 "2020-08-08T06:30:51Z")

</div>

In this code snippet:

```julia
n = 9
buf = Int[]
sizehint!(buf, n)

function foo(buf)
  empty!(buf)

  for i in 1:rand(1:n)
    push!(buf, rand(1:n))
  end
end

```

I intended to preallocate `buf`, so it `foo(buf)` can be called without further allocations. I failed because:

```julia
julia> @btime foo($buf)
  367.466 ns (10 allocations: 350 bytes)

```

Is there a solution to this problem?

**EDIT**

This is a closer version of `foo` to what I’m working with:

```julia
function foo(buf)
  empty!(buf)

  while length(buf) < rand(1:n)
    push!(buf, rand(1:n))
  end
end

```

The length of `buf` is unpredictable, but not exceeding `n`.

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [August 8, 2020, 6:42am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/2 "2020-08-08T06:42:11Z")

</div>

I think you can use `resize!` and then normal `setindex` syntax instead of push, which has more complex logic (because you deliberately set the hinted size, which `push` doesn’t know and has to check every time)

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 6:54am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/3 "2020-08-08T06:54:52Z")

</div>

> [@jules](#):
>
> I think you can use `resize!`

It doesn’t help:

```julia
function foo1(buf)
  j = rand(1:n)
  resize!(buf, j)

  for i in 1:j
    buf[i] = rand(1:n)
  end
end

```

still allocates:

```julia
julia> @btime foo1($buf)
  370.968 ns (10 allocations: 339 bytes)

```

Additionally, earlier version of `foo` was a bit too simplistic. I don’t really know the new buffer size at the beginning as it suggested. This is closer to the reality of my algorithm:

```julia
function foo(buf)
  empty!(buf)

  while length(buf) < rand(1:n)
    push!(buf, rand(1:n))
  end
end

```

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [August 8, 2020, 7:14am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/4 "2020-08-08T07:14:22Z")

</div>

Don’t use n as global variable

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 7:44am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/5 "2020-08-08T07:44:05Z")

</div>

Thank you:

```julia
julia> @btime foo($buf)
  75.193 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 7:57am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/6 "2020-08-08T07:57:30Z")

</div>

Now I’m scratching my head trying to figure out why… Is there any other reason for compiler to call allocate than pushing to array, which already used all preallocated memory?

Another option to avoid allocation is to parametrize `foo` with `n`:

```julia
function foo(buf, n)
  empty!(buf)

  while length(buf) < rand(1:n)
    push!(buf, rand(1:n))
  end
end

```

Is the compiler trying to be too smart for its own good?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [August 8, 2020, 9:44am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/7 "2020-08-08T09:44:38Z")

</div>

> [@pauljurczak](#):
>
> Is the compiler trying to be too smart for its own good?

No 🙂

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 10:00am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/8 "2020-08-08T10:00:05Z")

</div>

Why would compiler care what is inside `getnum()`? Can it just check if allocation is needed inside `push` call?

```julia
n = 9
buf = Int64[]
sizehint!(buf, n)

getnum() = rand(1:n)

function bar(buf)
  empty!(buf)

  while length(buf) < getnum()
    push!(buf, getnum())
  end
end

```

```julia
julia> @btime bar($buf)
  268.148 ns (7 allocations: 234 bytes)

```

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [August 8, 2020, 10:04am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/9 "2020-08-08T10:04:56Z")

</div>

I think the problem is that if n is a global and not a const, the getnum function is not guaranteed to return an int because it needs to be prepared for n to be mutated to anything else. That’s why getnum is not type stable and to deal with that some helper data structures that cause allocations are needed

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [August 8, 2020, 10:07am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/10 "2020-08-08T10:07:36Z")

</div>

> [@pauljurczak](#):
>
> Why would compiler care what is inside `getnum()` ?

Because you run that function so the compiler has to care?

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 10:12am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/11 "2020-08-08T10:12:43Z")

</div>

Changing it to:

```julia
const n = 9

```

still causes allocations.

My point is that `foo` and `bar` can be executed without needing allocations. Why is that for some external conditions compiler produces allocations and for others it doesn’t? The control and data flow are identical with and without allocations.

Also:

```julia
n = 9

function baz()
  println(typeof(rand(1:n)))
end

julia> baz()
Int64

```

so the type seems to be stable. I also tried:

```julia
getnum()::Int64 = rand(1:n)

```

and allocations are still there.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 10:27am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/12 "2020-08-08T10:27:54Z")

</div>

I meant, why compiler analysis of `getnum()` determines whether allocation will be performed? I see that unknown return type of `getnum` as mentioned by @jules could necessitate that, but it is not the case, is it?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [August 8, 2020, 10:36am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/13 "2020-08-08T10:36:55Z")

</div>

> [@pauljurczak](#):
>
> I meant, why compiler analysis of `getnum()` determines whether allocation will be performed?

Because if things are global then certain optimizations are not available, values might have to be boxed etc.

> [@pauljurczak](#):
>
> Changing it to:
> 
> ```julia
> const n = 9
> 
> ```
> 
> still causes allocations.

Not for me:

```julia
julia> @time bar(buf) # compilation allocations
  0.058862 seconds (65.22 k allocations: 3.386 MiB, 9.11% gc time)

julia> @time bar(buf)
  0.000004 seconds

```

* * *

> [@pauljurczak](#):
>
> Also:
> 
> ```julia
> n = 9
> 
> function baz()
> println(typeof(rand(1:n)))
> end
> 
> julia> baz()
> Int64
> 
> ```
> 
> so the type seems to be stable. I also tried:
> 
> ```julia
> getnum()::Int64 = rand(1:n)
> 
> ```
> 
> and allocations are still there.

What you did there with the `typeof` does nothing for checking type stability. Use `@code_warntype`. Also, a type assert doesn’t help with the fact that `n` is a global that you use.

It really seems you should read [Performance Tips · The Julia Language](https://docs.julialang.org/en/v1.5/manual/performance-tips/) carefully. Counting the exact number of allocations in type unstable code is pretty pointless, it’s mostly counting implementaion details.

---

<div class="post-metadata">

**Author:** ![pauljurczak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pauljurczak/32/921_2.png) [@pauljurczak](https://discourse.julialang.org/u/pauljurczak)\
**Post date:** [August 8, 2020, 11:00am UTC](https://discourse.julialang.org/t/preallocated-variable-length-buffer-with-known-maximum-length/44550/15 "2020-08-08T11:00:39Z")

</div>

> [@kristoffer.carlsson](#):
>
> Use `@code_warntype`

Thanks, now it makes sense:

```julia
julia> @code_warntype foo(buf)
Variables
  #self#::Core.Compiler.Const(foo, false)
  buf::Array{Int64,1}

Body::Nothing
1 ─ Main.empty!(buf)
2 ┄ %2 = Main.length(buf)::Int64
│ %3 = (1:Main.n)::Any
│ %4 = Main.rand(%3)::Any
│ %5 = (%2 < %4)::Any
└── goto #4 if not %5
3 ─ %7 = (1:Main.n)::Any
│ %8 = Main.rand(%7)::Any
│ Main.push!(buf, %8)
└── goto #2
4 ─ return

```

Globals can be so evil!