# Loops, allocations and helping the coder

**URL:** <https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733>\
**Category:** Internals & Design\
**Created:** [October 8, 2023, 6:18pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733 "2023-10-08T18:18:05Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Paul\_Soderlind](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paul_soderlind/32/1753_2.png) [@Paul\_Soderlind](https://discourse.julialang.org/u/Paul_Soderlind)\
**Post date:** [October 8, 2023, 6:18pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/1 "2023-10-08T18:18:05Z")

</div>

One of the performance pitfalls in Julia is allocations, especially in loops. For instance, with lots of arrays being created inside a long loop.

This can be handled by creating “workspaces” and then filling/overwriting the arrays inside the loop. Unfortunately, however, that often leads to code that looks clumsy and it’s certainly not straightforward for users with a non-CS background (scientists, say).

Therefore, my question: could “compiler” development possibly help the users with this? For instance, by letting `local X` inside a loop mean that that `X` is created in the first iteration and subsequently any `X = ` will lead to mutating the existing `X`?

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [October 8, 2023, 6:43pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/2 "2023-10-08T18:43:39Z")

</div>

I wouldn’t really recommend it to beginners, but my package [GitHub - MasonProtter/Bumper.jl: Bring Your Own Stack](https://github.com/MasonProtter/Bumper.jl) is specifically designed for speeding up this pattern of allocating intermediate arrays, using them, then deallocating them soon afterwards.

---

<div class="post-metadata">

**Author:** ![vchuravy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vchuravy/32/8_2.png) [@vchuravy](https://discourse.julialang.org/u/vchuravy)\
**Post date:** [October 8, 2023, 7:10pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/3 "2023-10-08T19:10:17Z")

</div>

There is a set of optimizations a sufficiently smarter optimizer can do. We are sometimes to hoist and allocation outside of a loop / or sink it outside that loop.

This currently only happens for Julia objects and not arrays and it happens fairly late in the pipeline (LLVM passes).

I do believe that we should be able to do a whole host of memory based optimizations in the compiler, especially now that we have effect and escape analysis on the higher level, but we may still need alias analysis.

I have a old and stale PR up for loop invariant code motion, but we probably need much better infrastructure to work with loops in the compiler first. At the time I got frustrated by how annoying it was to insert a basic block.

I do think the situation has much improved now and implementing LICM may be a good project to learn more about how the Julia compiler works.

---

<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:** [October 8, 2023, 7:22pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/4 "2023-10-08T19:22:04Z")

</div>

> [@Paul\_Soderlind](#):
>
> For instance, by letting `local X` inside a loop mean that that `X` is created in the first iteration and subsequently any `X = ` will lead to mutating the existing `X`?

This particular proposal would break backwards compatibility, which is a no-go:

> [@PSA: Julia is not at that stage of development anymore](https://discourse.julialang.org/t/psa-julia-is-not-at-that-stage-of-development-anymore/44872):
>
> You heard about this brand new exciting programming language called Julia and have some suggestions for how it should work. Wonderful! We’re happy to have you here and help you learn the language and listen to your ideas! However, please be aware that “new” is a relative term. Yes, Julia is newer than, say, C, which was first created in 1972 and standardized in 1989. It is not, however, new in the sense that it is still being freely designed and changed in arbitrary ways. Julia development start…

---

<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:** [October 8, 2023, 7:25pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/5 "2023-10-08T19:25:27Z")

</div>

> [@Paul\_Soderlind](#):
>
> Therefore, my question: could “compiler” development possibly help the users with this?

[This](https://discourse.julialang.org/t/option-to-completely-disallow-dynamic-allocation/1417) seems like one possible feature that could help, in addition to the already existing features like the allocation profilers.

---

<div class="post-metadata">

**Author:** ![Paul\_Soderlind](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paul_soderlind/32/1753_2.png) [@Paul\_Soderlind](https://discourse.julialang.org/u/Paul_Soderlind)\
**Post date:** [October 8, 2023, 7:44pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/6 "2023-10-08T19:44:09Z")

</div>

It’s not a proposal (as I am not qualified to make one). Rather, just an attempt to explain a general idea/question. (Of course we cannot change `local`, so let’s call it `local2`.)

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 8, 2023, 11:06pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/7 "2023-10-08T23:06:31Z")

</div>

> [@Paul\_Soderlind](#):
>
> Therefore, my question: could “compiler” development possibly help the users with this? For instance, by letting `local X` inside a loop mean that that `X` is created in the first iteration and subsequently any `X = ` will lead to mutating the existing `X`?

Problem is this isn’t _just_ a compiler development, this actually changes language semantics in a breaking way. You can get around that with a new keyword like `local2`, but you really shouldn’t add irreversible changes to a language if you don’t have to. In this case, we really don’t have to, not even with a macro. Allocating `X` before the loop and writing mutation code in the loop is clearer and less effort than patching allocation code with keywords and hoping the compiler knows what you intend it to do.

Forgetting about the manual keyword, escape analysis could hypothetically help heap reuse if it recognizes that each `X` does not outlive the iteration’s scope. It’s easy for us to intend that, but it’s hard to enforce that throughout our method calls and for the compiler to efficiently prove. And if `X = ` has unfixed sizes, allocations still need to happen for some resizings.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [October 9, 2023, 11:07am UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/8 "2023-10-09T11:07:57Z")

</div>

> [@Benny](#):
>
> Allocating `X` before the loop and writing mutation code in the loop is clearer and less effort

Not always; especially when you have to calculate types for a container.

I am sympathetic to @Paul_Soderlind’s problem, as I often encounter it when solving economic models. Specifically, a lot of calculations for heterogeneous agent models require work arrays which I can reuse for many calls of a function, eg

```julia
function calculate_moments_for_agent_type(model, type::Integer, work_buffers)
    # I need work buffers from here on
    ...
    # and I don't care what happens to them after
end

function calculate_aggregate_moments(model)
    work_buffers = allocate_work_buffers(model) # ideally this could be outside
    mapreduce(i -> calculate_moments_for_agent_type(model, i, work_buffers),
              add_moments, model.agent_types)
end

```

The problem is most acute when I want to use type-based AD (ForwardDiff), parallel threads so that each gets to use one work buffer one at a time, and the lifetime of buffers does not coincide with functions. It is of course manageable, but a pain in the neck.

Bumper.jl looks promising though, I just haven’t had a chance to evaluate it in large codebases. But if it works, it would solve my problem.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 9, 2023, 12:28pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/9 "2023-10-09T12:28:43Z")

</div>

> [@Tamas\_Papp](#):
>
> Not always; especially when you have to calculate types for a container.

I think I’m misunderstanding this, because if the array in every iteration doesn’t have the same element type, then it would be impossible to refactor to reuse of 1 array across iterations. Doesn’t sound like an issue for a bump allocator to allocate and free.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [October 9, 2023, 12:37pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/10 "2023-10-09T12:37:42Z")

</div>

I’m confused because your phrasing sounds like you are disagreeing with Tamas, but then you seem to just be restating his point: just preallocating an array and re-using it can be really awkward if you want to use it to store different types in different places.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [October 9, 2023, 12:57pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/11 "2023-10-09T12:57:20Z")

</div>

> [@Benny](#):
>
> if the array in every iteration doesn’t have the same element type

In practice it is restricted to a few types (eg `Float64`, and the corresponding `ForwardDiff.Dual{nightmare}`), or maybe `BigFloat` when I am doing numerical debugging. Within the same evaluation, it is the same type.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [October 9, 2023, 1:11pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/12 "2023-10-09T13:11:33Z")

</div>

> [@Tamas\_Papp](#):
>
> or maybe `BigFloat` when I am doing numerical debugging. Within the same evaluation, it is the same type.

Just a side note if you’re trying to evaluate whether [Bumper.jl](https://github.com/MasonProtter/Bumper.jl) will work for you, only `isbits` types are supported in Bumper.jl. You could use something like [MultiFloats.jl](https://github.com/dzhang314/MultiFloats.jl) though since those are `isbits`, or just replace calls to `alloc(BigFloat, buf, size...)` with calls to `Array{BigFloat}(undef, size...)` while testing.

I see now I didn’t mention that anywhere in the README, so I’ll fix that now.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 9, 2023, 1:30pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/13 "2023-10-09T13:30:47Z")

</div>

Oh I was just confused why it was mentioned because the use case sounded impossible to do with the array-reuse scheme I was talking about, whether it’s manual or transformed from allocation-per-iteration code. But it seems like it’s not actually what I imagined.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [October 9, 2023, 1:36pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/14 "2023-10-09T13:36:37Z")

</div>

You can do it with array re-use, you just need a `reinterpret` step. In fact, I had a version of Bumper.jl which worked just fine using only `reinterpret` and `view`, but it was too slow because of inefficiencies in working with `reinterpret`ed arrays. It was still faster than heap allocating new arrays for a lot of use-cases, but it was a lot slower than using `PtrArray`s.

---

<div class="post-metadata">

**Author:** ![mrufsvold](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrufsvold/32/31600_2.png) [@mrufsvold](https://discourse.julialang.org/u/mrufsvold)\
**Post date:** [October 9, 2023, 6:23pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/15 "2023-10-09T18:23:42Z")

</div>

On one project, I have a long async pipeline that needs arrays that flow all the way through. I created an “array manager” channel that allocates a new array when you call `take` on it, and when you call `put(manager, arr)`, it empties the array and offers it to the next call for `take`

It had me wondering if there was anyway for GC to link into the array allocator so that you don’t need allocate from scratch every time. Instead of `freeing` them, repurpose the allocated memory. Then have some kind of heuristic for freeing “stale” allocations if they aren’t needed after a while.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [October 9, 2023, 7:40pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/16 "2023-10-09T19:40:47Z")

</div>

Why does it have to allocate every time? Why not store the array in the channel and just mutate it?

---

<div class="post-metadata">

**Author:** ![TI36XPro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ti36xpro/32/33658_2.png) [@TI36XPro](https://discourse.julialang.org/u/TI36XPro)\
**Post date:** [October 9, 2023, 7:53pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/17 "2023-10-09T19:53:15Z")

</div>

Just to give you another perspective. My background is engineering, not CS.

> [@Paul\_Soderlind](#):
>
> This can be handled by creating “workspaces” and then filling/overwriting the arrays inside the loop. Unfortunately, however, that often leads to code that looks clumsy and it’s certainly not straightforward for users with a non-CS background (scientists, say).

Not sure I agree. I think it is a matter of learning how to write performant code. The same lesson could apply in writing performant C (allocating an array once, passing the pointer around, then refilling as needed). In my experience, writing code this way is not particularly clumsy compared to any other style.

If you want to write performant code I think you should have to learn some of the basic best practices to writing good code, knowing a little bit about the software & hardware and why allocation is slow. [This](https://www.juliabloggers.com/what-scientists-must-know-about-hardware-to-write-fast-code/) post comes to mind.

---

<div class="post-metadata">

**Author:** ![mrufsvold](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrufsvold/32/31600_2.png) [@mrufsvold](https://discourse.julialang.org/u/mrufsvold)\
**Post date:** [October 9, 2023, 9:30pm UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/18 "2023-10-09T21:30:48Z")

</div>

Sorry, I was a unclear! It allocates a new array if none have been returned yet when `take` is called. Once the arrays start getting returned, it just serves as a queue for preallocated arrays! Since I have multiple jobs working in parallel, there are usually something like `ntasks` allocated arrays, but it depends on the timing of when one task is finishing and the next is starting.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [October 10, 2023, 8:46am UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/19 "2023-10-10T08:46:29Z")

</div>

> [@TI36XPro](#):
>
> The same lesson could apply in writing performant C (allocating an array once, passing the pointer around, then refilling as needed).

The problem in practice is that Julia’s type system is orders of magnitudes richer than C, and you run into this if your code uses packages that make use of it. Specifically, the same lines of source code will not necessarily run with the same types.

Idiomatic Julia code relies on semi-automatic type calculations and these do not mesh well with pre-allocated arrays. It can be made to work, but it is not as easy as you imagine.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [October 10, 2023, 9:11am UTC](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733/20 "2023-10-10T09:11:26Z")

</div>

> [@mrufsvold](#):
>
> It had me wondering if there was anyway for GC to link into the array allocator so that you don’t need allocate from scratch every time. Instead of `freeing` them, repurpose the allocated memory. Then have some kind of heuristic for freeing “stale” allocations if they aren’t needed after a while.

Julia’s garbage collector already does that.

```julia-repl
julia> length(unique(x -> pointer(zeros(10_000)), 1:10_000))
576

```

if I allocate 10,000 arrays in a row each of which as 10,000 entries, there’s only 576 unique pointers. This is called object pooling, and it’s generally only worth it for big arrays, e.g. here’s what happens when I do length `100`:

```julia-repl
julia> length(unique(x -> pointer(zeros(100)), 1:10_000))
10000

```

but there’s a lot of other stuff involved in gabage collection that makes things slow other than just the allocation of an array. In fact, allocation is the fastest part, it’s setting things up so that memory can be tracked and freed that is generally slow.

[Next page](https://discourse.julialang.org/t/loops-allocations-and-helping-the-coder/104733.md?page=2)