# How to preallocate and reuse buffers for oft-repeated computation?
**URL:** https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915
**Category:** General Usage
**Tags:** question, performance, memory-allocation, profiling, speed-optimization
**Created:** [June 27, 2023, 9:24pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915 "2023-06-27T21:24:22Z")
**Posts on this page:** 16
**Page:** 1
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 27, 2023, 9:24pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/1 "2023-06-27T21:24:23Z")
In [How to optimise Julia code: A practical guide](https://viralinstruction.com/posts/optimise/), Jakob Nissen suggests that one way to optimize code + reduce allocations is to
- Preallocate buffers once and reuse them multiple times
I’m wondering if someone has a walkthrough of an actual example comparing a “repeatedly allocate” solution to a “preallocate buffers and reuse” solution. I think I understand the idea, but I’m wondering how to follow the advice in practice.
For example, I have a calculation like the following:
```julia
struct ResultData
value::Float64
result_type::Bool
end
function calculate_and_use(x, y, z)
if y > z
temp = ResultData(y + z, true)
else
temp = ResultData(y * z, false)
end
if temp.result_type
x + z
else
x - z
end
end
```
Please ignore the implementation details—`calculate_and_use` is any involved calculation that involves an allocation of an object, here played by `ResultData`, which has some overhead.
Let’s say `calculate_and_use` has to be called millions of times by some function, so each time there’s an allocation of a `ResultData` object which is then thrown away and, voila, re-allocated a split second later. (Not that this seems to matter, but `ResultData` could actually be a fixed-length `Vector{ResultData}` or similar, but in any case: it’s created, used, and then thrown away.)
What would be the analogue of pre-allocating a buffer in this context? Would I have some `global buf = ResultData(0.0,false)` that just gets overwritten? (But this violates “Use immutable structs over `mutable struct` when mutation is not needed,” as well as violating the dictum not to use `global`s.)
If not, then what is the right way to follow the preallocation advice in this context?
Or have I misunderstood the preallocation advice…and it is only applicable in other contexts?
Any suggestions appreciated; thank you!
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [June 27, 2023, 9:32pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/2 "2023-06-27T21:32:53Z")
> [@philip](#):
>
> Let’s say `calculate_and_use` has to be called millions of times by some function, so each time there’s an allocation of a `ResultData` object which is then thrown away and, voila, re-allocated a split second later.
`struct` objects are **not** generally allocated on the heap, so you don’t need to worry about them. See [the manual section on tracking allocations](https://docs.julialang.org/en/v1/manual/performance-tips/#Measure-performance-with-%5B@time%5D(@ref)-and-pay-attention-to-memory-allocation):
> […] _heap_ allocations […] are typically needed for either mutable objects or for creating/growing variable-sized containers (such as `Array` or `Dict`, strings, or “type-unstable” objects whose type is only known at runtime). Allocating (or deallocating) such blocks of memory may require an expensive system call (e.g. via `malloc` in C), and they must be tracked for garbage collection. In contrast, immutable values like numbers (except bignums), tuples, and immutable `struct`s can be stored much more cheaply, e.g. in stack or CPU-register memory, so one doesn’t typically worry about the performance cost of “allocating” them.
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 27, 2023, 9:39pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/3 "2023-06-27T21:39:08Z")
Fair enough and thanks; that’s interesting!
Alas I was being lazy and the reality is that several of the many, many objects I’m repeatedly allocating are `Dict`s and others are `Array`s.
I apologize that I think I oversimplified in my efforts to make the `MWE` `M` enough to be legible, but I think I still have the question notwithstanding that helpful background on `struct` allocation.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [June 27, 2023, 9:57pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/4 "2023-06-27T21:57:24Z")
Hard to say more without a specific example, but the generic advice is (a) avoid allocating temporary arrays (or other mutable data structures) at all in your inner loops (work in place, use tuples and staticarrays, ditch “vectorize everything” habits from Matlab and Numpy, …), and otherwise write in-place functions that act on a re-usable buffer array (passed as an _argument_, not as a global).
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 27, 2023, 10:47pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/5 "2023-06-27T22:47:27Z")
This is great advice.
I think my question could alternately be phrased as “what does _work in place_ mean”? Like is there an example / blog post / similar somewhere that can show the “in-place” version side-by-side with the “not-in-place” version?
For example above, if we pretend `temp` is a mutable data structure/temporary array that’s not supposed to be used at all in an inner loop, what would the “in-place” alternative to `temp` be?
I definitely believe that doing things in-place would be better, but I’m trying to understand what that actually means concretely: swap values in a global object that holds the values, or create the placeholder outside the function and pass it as an argument, or…?
Please let me know if that makes sense.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [June 27, 2023, 10:50pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/6 "2023-06-27T22:50:07Z")
>
---
### Author:  [@nsajko](https://discourse.julialang.org/u/nsajko)
#### Post date: [June 27, 2023, 11:07pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/7 "2023-06-27T23:07:45Z")
> [@philip](#):
>
> I think my question could alternately be phrased as “what does _work in place_ mean”?
There’s actually a Wikipedia page on the topic:
> **[In-place algorithm](https://en.wikipedia.org/wiki/In-place_algorithm)**
>
> In computer science, an in-place algorithm is an algorithm that operates directly on the input data structure without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
> In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, countin...
Keep in mind that only _hot_ loops need to be optimized. Keep a profiler handy.
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 27, 2023, 11:40pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/8 "2023-06-27T23:40:26Z")
@stevengj @nsajko thanks both for the links. I do understand how to mutate an object passed as an argument.
I’m trying to ask about the _paradigm_. Is the ideal paradigm to generate the object to serve as the placeholder/buffer at the global level? One function-call up? Different advice for different situations? etc.
I figured if there were concrete examples of this being done for certain functions it would help inspire a solution. So–not a blog post saying “here’s how to use mutable versus immutable structs” but a blog post saying (e.g.) “I optimized an implementation of { the Black-Scholes algorithm / the Newton-Raphson method / quicksort } to reduce allocations, here’s what the code looks like in the original version with allocations versus the revised version without them.”
Thanks and apologies for the unclear question.
---
### Author:  [@mrufsvold](https://discourse.julialang.org/u/mrufsvold)
#### Post date: [June 27, 2023, 11:43pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/9 "2023-06-27T23:43:00Z")
Just a silly example of converting an algorithm to in place would be
```julia
function add_one(arr)
return arr .+ 1
end
# In Julia, we add `!` to the end of in place/ mutating function names by convention
function add_one!(arr)
for i in eachindex(arr)
arr[i] = arr[i] + 1
end
end
```
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 27, 2023, 11:44pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/10 "2023-06-27T23:44:27Z")
Thanks all.
May I ask that we put this question on hold for a second and I’m going to provide a bigger MWE.
I’m clearly not explaining the question clearly. Stay tuned. 🙂
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [June 27, 2023, 11:51pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/11 "2023-06-27T23:51:51Z")
> [@philip](#):
>
> Is the ideal paradigm to generate the object to serve as the placeholder/buffer at the global level? One function-call up?
Almost certainly not global. It just needs to be somewhere outside of your critical inner loop(s).
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [June 27, 2023, 11:57pm UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/12 "2023-06-27T23:57:39Z")
You can find some examples on this thread, with the most common patterns to avoid, and what to do: [Common allocation mistakes](https://discourse.julialang.org/t/common-allocation-mistakes/66127)
---
### Author:  [@fatteneder](https://discourse.julialang.org/u/fatteneder)
#### Post date: [June 28, 2023, 8:36am UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/13 "2023-06-28T08:36:36Z")
Here is an artificial example on “how to optimize away allocations using in-place operations and buffers”:
A mental model I like to apply when optimizing allocations is to think about how one would write the same function in a language with manual memory management. Obviously, this only works if you know one well. I use `C` here and IMO everyone who programs in Julia should have touched `C` at least once before.
Consider
```julia
function compute_something(A::AbstractMatrix, vs::Vector{<:AbstractVector})
result = zero(eltype(A))
for v in vs
x = A * v # this creates a temporary matrix in every loop iteration
result += sum(x)
end
return result
end
```
“Mental transpilation to C” would give something like
```plaintext
double compute_something(double *A, double **vs, int An, int Am, int nvs) {
double result = 0.0;
for (int i = 0; i < nvs; i++) {
double *vi = vs+i;
double *x = malloc(sizeof(double) * An);
// matrix multiplication
for (int nn = 0; nn < An; nn++) {
result += x[nn];
}
free(x); x = NULL;
}
return result;
}
```
where I left out any `NULL` checks for clarity.
If you know `C` then you realize that the above is not idomatic, because you `malloc` and `free` `nvs` times a vector. Doing so in `C` might not be a bottleneck for your algorithm, but you still risk a memory leak.
In Julia, you don’t risk the memory leak, but the `malloc` and `free` work then all needs to be done by the `GC` and having the `GC` to do the free is in general more expensive than in `C` (because it needs to check if there are any references left to any of the objects that have been `malloc`ed before, somehow like that…).
So what you want to do here then is to move the `malloc, free` outside the loop.
Doing this in Julia is as easy as rewriting the above as
```julia
using LinearAlgebra
function compute_something(A::AbstractMatrix, vs::Vector{<:AbstractVector})
result = zero(eltype(A))
x = zeros(eltype(A), size(A)[1]) # make a buffer once
for v in vs
mul!(x, A, v) # inplace matrix multiplication from LinearAlgebra
result += sum(x)
end
return result
end
```
And if for some reason the allocation of the temporary `x` becomes also too expensive wrt the matrix multiplications in the loop, then you might even want to allocate `x` before you call `compute_something` and just pass it on as a buffer, e.g.
```julia
function compute_something_w_buffer(A::AbstractMatrix, vs::Vector{<:AbstractVector}, x::AbstractVector)
result = zero(eltype(A))
for v in vs
mul!(x, A, v)
result += sum(x)
end
return result
end
```
* * *
Doing the above needs practice, in particular when it comes to realizing which operations allocate, which don’t allocate and which can and cannot be made to not allocate.
But there are a ton of tools out there that can help you figure that out, like `BenchmarkTools, ProfileView, @code_warntype, Cthulhu` etc.
Lastly, the first things I like to check when optimizing allocs are (which is just a condensed version of the performance tips from the Julia docs):
- Do I perform any array operations like `=,*,+,-,/` without a `.`(broadcasting)?
- Do I perform any array slicing like `x[1:4,:]` without a `@views`? (IIRC optimizing this away only really works if you don’t pass your `view` to another function call that is **not** `@inline`d)
Usually not fixed by using in-place algorithms and buffers:
- Are there any type instabilities?
- Do I use any non-const globals?
* * *
I know that `result = zero(eltype(A))` is not optimal, because the `vs` might have different eltypes too, but this was not the focus of this example.
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 29, 2023, 1:40am UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/14 "2023-06-29T01:40:44Z")
This is excellent. I have much to digest and am doing so with excitement.
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [June 29, 2023, 1:42am UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/15 "2023-06-29T01:42:31Z")
Thank you! This is exactly the sort of before-after comparison I was looking for.
I am going to test out some alternatives and see what happens. I don’t have a good sense of whether my analogue of your `compute_something` v2 (the one with `x = zeros`) would end up much slower than v3 (the one with `x` as an argument), mapped onto my problem.
I will test and report back. Thank you!
---
### Author:  [@philip](https://discourse.julialang.org/u/philip)
#### Post date: [July 12, 2023, 10:15am UTC](https://discourse.julialang.org/t/how-to-preallocate-and-reuse-buffers-for-oft-repeated-computation/100915/16 "2023-07-12T10:15:48Z")
In the case I was trying to optimize, lots of profiling + editing + re-profiling etc. ended up revealing the creation of small arrays (mistake #3) as the binding issue. I switched over to StaticArrays wherever possible and achieved a significant speedup.