# How to support passing temporary buffers around

**URL:** <https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880>\
**Category:** Internals & Design\
**Tags:** memory-allocation, functions\
**Created:** [November 3, 2021, 2:45pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880 "2021-11-03T14:45:23Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 3, 2021, 2:45pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/1 "2021-11-03T14:45:24Z")

</div>

> [@Request for comments: a roadmap to faster sort() for primitive types using RadixSort](https://discourse.julialang.org/t/request-for-comments-a-roadmap-to-faster-sort-for-primitive-types-using-radixsort/70269/24):
>
> I wish someone created a syntax for non allocating function which is what’s really important for performance.  
> Something like `FunName!!()` maybe?  
> Then I’d say it would be great to make all base functions have a version which accepts pre allocated buffers from outside.
> 
> **Remark** : This takes discussion to a detour but it makes sense as a solution if we use allocating sort algorithm to be able to set input for the allocated buffers.

Right now if a user wants to re-use a pre-allocated buffer for sorting multiple data-sets of similar size and type, they must dig into sorting internals (e.g. calling `Sort.sort!(v, alg, ord)`, which bypasses the automatic `ord` construction from keyword arguments and the count-sort special case). Neither `sort.(v::Vector{Vector{Int}})`, `sort!.(v::Vector{Vector{Int}})`, nor even `sort!.(v::Matrix{Int}, dims=1)` re-use temporary buffers, likely because of how messy it is to pass them around right now.

Can we do better in sorting and other cases where temporary storage is sometimes or always needed?

Can the compiler/gc/other best-effort internals typically detect this re-use make it just as fast as manually passing the buffer?

Can we create a unified elegant system for passing temporary buffers in Base that package developers can use as a model?

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 3, 2021, 2:51pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/2 "2021-11-03T14:51:11Z")

</div>

If we do change the convention, I think it should be to indicate which mutating function _are_ allocating, not non-allocating. But I don’t think we should change the convention. I think the extra name convention is probably unnecessary, and could be misleading. Folks should benchmark if they want to know how fast a function is. Allocations may or may not be an issue depending on their use case.

That said, I still want the performance improvements from passing buffers around in base.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [November 3, 2021, 4:02pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/3 "2021-11-03T16:02:56Z")

</div>

Seems like good functionality to have. I can remember 2 distinct times where I would have wanted this. That being said, I think that [https://github.com/JuliaCollections/SortingAlgorithms.jl](https://github.com/JuliaCollections/SortingAlgorithms.jl) is the right place for it.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 3, 2021, 4:04pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/4 "2021-11-03T16:04:43Z")

</div>

Were both times sorting related? Does anyone have experience wanting this in a domain other than sorting?

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [November 3, 2021, 4:06pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/5 "2021-11-03T16:06:03Z")

</div>

> [@Lilith](#):
>
> Were both times sorting related?

Yes, of course. Isn’t that specifically what your post is about? Re-using temporary buffers when doing frequent or repeated sorting

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [November 3, 2021, 4:10pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/6 "2021-11-03T16:10:08Z")

</div>

Actually, it looks like [https://github.com/JuliaCollections/SortingAlgorithms.jl](https://github.com/JuliaCollections/SortingAlgorithms.jl) might already have this functionality? I’ve only just browed the code but it looks like the `ts` keyword argument to `sort!` might be doing just that?

---

<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:** [November 3, 2021, 4:52pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/7 "2021-11-03T16:52:28Z")

</div>

> [@Lilith](#):
>
> Does anyone have experience wanting this in a domain other than sorting?

A similar thing happens in linear algebra, where to have non-allocating functions one needs to call BLAS routines more directly, passing the auxiliary arrays.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 3, 2021, 5:27pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/8 "2021-11-03T17:27:12Z")

</div>

> [@tbeason](#):
>
> Isn’t that specifically what your post is about? Re-using temporary buffers when doing frequent or repeated sorting

I’m trying to also address other similar cases (edited OP for clarity on this)

> [@tbeason](#):
>
> might already have this functionality?

Yes, that is what I referred to in

> [@Lilith](#):
>
> they must dig into sorting internals (e.g. calling `Sort.sort!(v, alg, ord)` , which bypasses…

Unfortunately, the `ts` doesn’t actually get carried all the way to the public facing interface.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [November 4, 2021, 5:48am UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/9 "2021-11-04T05:48:40Z")

</div>

> [@lmiq](#):
>
> > [@Lilith](#):
> >
> > Does anyone have experience wanting this in a domain other than sorting?
> 
> A similar thing happens in linear algebra, where to have non-allocating functions one needs to call BLAS routines more directly, passing the auxiliary arrays.

I wish it was a widely used convention.  
Break a function into an initialization procedure which allocates the required data and the function itself which doesn’t allocate.  
Then any repeating calls will be non allocating.

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [November 5, 2021, 1:46am UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/10 "2021-11-05T01:46:00Z")

</div>

For example, I often do

```julia
function prepare_f(x)
    y = similar(x)

    function g(x)
          # fancy operation uses y
          return y
     end
    return g
end

```

Then I can repeatedly apply `g` very efficiently in some optimization etc.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 5, 2021, 3:53am UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/11 "2021-11-05T03:53:19Z")

</div>

Fun pattern! I wonder how good of a general solution it is (e.g. for use in Base)

Does this suffer from the issue that [`y`’s type cannot be inferred because the compiler can’t figure out that `g` doesn’t change `y`’s type](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-captured), and if so, what is the performance penalty? I suspect this could be a big deal if `y` is referenced a lot in `g` because `y` will have to be boxed.

(btw,

> [@roflmaostc](#):
>
> `return y`

Should this be `return x` or `return z`? )

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [November 5, 2021, 3:54pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/12 "2021-11-05T15:54:45Z")

</div>

You’re right, such patterns can lead to problems!

For example:

```julia
function gen_f(x)
    if true
        y = x .+ 1
    end 

    function f(a)
        a + y 
    end 
    return f
end

function gen_f_safe(x)
    if true
        y = x .+ 1
    end 

    f = let y = y 
        function f(a, y=y)
            a + y 
        end 
    end 
    return f
end

```

REPL:

```julia
julia> f = gen_f(10)
^[[Af (generic function with 1 method)

julia> @code_warntype f(1)
Variables
  #self#::typeof(f)
  a::Int64
  y::Union{}

Body::Any
1 ─ %1 = Core.getfield(#self#, :y)::Core.Box
│ %2 = Core.isdefined(%1, :contents)::Bool
└── goto #3 if not %2
2 ─ goto #4
3 ─ Core.NewvarNode(:(y))
└── y
4 ┄ %7 = Core.getfield(%1, :contents)::Any
│ %8 = (a + %7)::Any
└── return %8

julia> f_safe = gen_f_safe(10)
(::var"#f#2"{Int64}) (generic function with 2 methods)

julia> @code_warntype f_safe(1)
Variables
  #self#::var"#f#2"{Int64}
  a::Int64

Body::Int64
1 ─ %1 = Core.getfield(#self#, Symbol("#38#y"))::Int64
│ %2 = (#self#)(a, %1)::Int64
└── return %2

```

The cool thing is, that you can also change the _buffer_ (if you want to) in `f_safe`.

For me the big advantage is, that the user does not need how to create the buffer.  
Sometimes the buffer is non-obvious. Think about operations using broadcasting or `rfft` where the buffer has a different shape or `eltype`. On the other hand, `f_safe` might allocate a lot of memory.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 5, 2021, 4:48pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/13 "2021-11-05T16:48:20Z")

</div>

> [@roflmaostc](#):
>
> `f_safe` might allocate a lot of memory

By this I’m assuming you mean “own” i.e. as we keep `f_safe` around the memory will be in use.

If there are three two different functions `f`, and `g`, both of which mutate an array but require temporary storage `similar` to their input, and I want to compute `f(g(x))` for two different x of the same type and size, naively, I’ll allocate 4 times, with `gen_f_safe` or `gen_f` I’ll still allocate twice, while manual temporary storage passing can drop allocations to 1.

Perhaps some sort compiler pass or macro `@reuse_temporary` that can convert

```julia
temp1 = similar(x)
f(x, temp=temp1)
#temp 1 is never used again
temp2 = similar(x)
g(x, temp=temp2)

```

to

```julia
temp1 = similar(x)
f(x, temp=temp1)
temp2 = temp1 # or, as necessary, reinterpret(temp1) and maybe even resize!ing?
f(x, temp=temp2)

```

Which would let me use Base’s existing sorting methods without this problem:

```julia
@time sort!(rand(1000,1000), dims=1; alg=QuickSort); #2k allocs
@time sort!(rand(1000,1000), dims=1; alg=MergeSort); #5k allocs b.c. MergeSort takes temporary array

```

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [November 7, 2021, 8:27am UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/14 "2021-11-07T08:27:37Z")

</div>

Couldn’t we just add a keyword argument to whatever functions with some conventional name whose type is a `Vector{UInt8}` and which the function is free to resize, reshape and reinterpret however it needs to.

The caller can then preallocate an empty such vector and pass it in to repeated calls without needing to know how it will be used.

---

<div class="post-metadata">

**Author:** ![fverdugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fverdugo/32/9446_2.png) [@fverdugo](https://discourse.julialang.org/u/fverdugo)\
**Post date:** [November 7, 2021, 11:12am UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/15 "2021-11-07T11:12:48Z")

</div>

Hi @Lilith

In the [Gridap project](https://github.com/gridap/Gridap.jl) we have ended with a systematic way of allocating buffers for function evaluation and also for array indexing. Take a look at this preprint for all specific details: [[2109.12818] The software design of Gridap: a Finite Element package based on the Julia JIT compiler](https://arxiv.org/abs/2109.12818)

For calling functions (or any callable object) we introduced this syntax:

```julia
cache = return_cache(f,x...)
fx = evaluate!(cache,f,x...)

```

for a callable object `f` on the arguments in `x`.

By default we define

```julia
return_cache(f,args...) = nothing
evaluate!(::Nothing,f,args...) = f(args...)

```

So, any callable object can be called via the exteded syntax and by default we do not use the cache and simply call the function on the given arguments as usual. However, we have opened the door to reuse data at each function call by specialising functions `return_cache` and `evaluate!` for particular cases.

For instance, consider this function `f(x,y) = [x,y]`, just as a very simple example. If you don’t want to generate a new vector at each function call, you can define:

```julia
function return_cache(::typeof(f),x,y)
 [x,y]
end
function evaluate!(cache,::typeof(f),x,y)
  cache[1] = x
  cache[2] = y
  cache
end

```

and then you will get:

```julia
cache = return_cache(f,1,2) # New vector created here
fx = evaluate!(cache,f,10,20) # No vector created here
@assert fx == [10,20]
fx = evaluate!(cache,f,100,200) # No vector created here
@assert fx == [100,200]

```

This is essentially the idea. Note that this is thread safe since you can generate an independent buffer for each thread by calling `return_cache`. Note also that one needs to be aware that the result `fx` potentially takes ownership of some part of the state of the cache. So, one might need to generate several caches e.g.

```julia
c1 = return_cache(f,1,2)
c2 = return_cache(f,1,2)
for ((x1,y1),(x2,y2)) in zip([(1,2),(10,20)],[(10,20),(100,200)] )
  fx1 = evaluate!(c1,f,x1,y1)
  fx2 = evaluate!(c2,f,x2,y2)
  @assert fx1 == 10*fx2
end

```

If we consider just a single cache, then `fx1` and `fx2` would be the same object.

This mechanism is pretty useful for our use cases and we are happy with it after been using it for a while.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 7, 2021, 3:14pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/16 "2021-11-07T15:14:30Z")

</div>

@cjdoris I really like your idea! I think this could be a good convention. The name used in sorting internals right now is `ts`, but I think it might need to change if it becomes public facing. `workspace` , `temp`, `scratch_space`, and `scratch` seem viable.

> [@cjdoris](#):
>
> a `Vector{UInt8}` and which the function is free to resize, reshape and reinterpret however it needs to

Perhaps resizing down should be discouraged in order to better support this:

```julia
temp = UInt8[]
sort!(big, temp=temp)
for small in smalls
    sort!(small, temp=temp)
end
sort!(big2, temp=temp)

```

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 7, 2021, 3:38pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/17 "2021-11-07T15:38:59Z")

</div>

Hi @fverdugo,

What advantages does your method present over @cjdoris’s? As I see it, cjdoris’s `Vect{UInt8}`s can also be shared between any two functions that follow the convention while yours’ only allows sharing between functions that have the same `cache` type. Is the `cache`. From a user perspective, I think this is

```julia
function sort_two_vectors(vec1::T, vec2::T) where T <: AbstractVector
    cache = return_cache(sort!, vec, rev=true, alg=MergeSort)
    evaluate!(cache, sort!, vec1, rev=true, alg=MergeSort)
    evaluate!(cache, sort!, vec2, rev=true, alg=MergeSort)
end

```

is more boilerplate, more new functions, harder to understand than, and even less powerful than

```julia
function sort_two_vectors(vec1, vec2)
    workspace = UInt8[]
    sort!(vec1, rev=true, alg=MergeSort, workspace=workspace)
    sort!(vec2, rev=true, alg=MergeSort, workspace=workspace)
end

```

> [@fverdugo](#):
>
> be aware that the result `fx` potentially takes ownership of some part of the state of the cache

I prefer to guarantee not to do this. We have mutation and the `!` convention to support returning something that owns part of the input of a function, and I think temporary workspaces can exist separate from that. In your toy example, we can instead define:

```julia
function f!(cache, a, b)
  cache[1] = a
  cache[2] = b
  cache
end

```

and then you will get

```julia
cache = f(1,2) # New vector created here
fx = f!(cache,10,20) # No vector created here
@assert fx == [10,20]
fx = f!(cache,100,200) # No vector created here
@assert fx == [100,200]

```

---

<div class="post-metadata">

**Author:** ![fverdugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fverdugo/32/9446_2.png) [@fverdugo](https://discourse.julialang.org/u/fverdugo)\
**Post date:** [November 7, 2021, 5:56pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/18 "2021-11-07T17:56:16Z")

</div>

I think that the key part is return\_cache. It automatically generates the buffer for a given function f. This works for any function f without knowing which this function is. In general the buffer can be way more complex than a vector of ints and each function can work on a different type of buffer.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 7, 2021, 6:05pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/19 "2021-11-07T18:05:39Z")

</div>

You’re mixing the terms “buffer” and “cache”. What exactly to you mean? I’m trying to talk about scratch space in memory that a function needs read and write to in order to compute its answer.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [November 7, 2021, 6:15pm UTC](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880/20 "2021-11-07T18:15:32Z")

</div>

This sort of scratch space is used in Julia’s `sort` and `sort!` and in BLAS routines. It is also referred to as “auxiliary storage”.

Do you have an example of where this type of storage couldn’t be `reinterpret`ed from a `Vector{UInt8}` and where functions would have to use mutually incompatible types of auxiliary storage?

[Next page](https://discourse.julialang.org/t/how-to-support-passing-temporary-buffers-around/70880.md?page=2)