# \[RFC/ANN\] Restacker.jl: A workaround for the heap-allocated-immutable problem?

**URL:** <https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037>\
**Category:** Package Announcements\
**Tags:** package, announcement\
**Created:** [February 23, 2020, 2:29am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037 "2020-02-23T02:29:46Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 23, 2020, 2:29am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/1 "2020-02-23T02:29:46Z")

</div>

I generalized and packaged up [a workaround I’ve been using in Transducers.jl](https://github.com/tkf/Transducers.jl/blob/9471e306f0421b572aa419ca471ad53de8306cd0/src/processes.jl#L714-L727) (see below for an explanation) to avoid using heap-allocated immutables when they contain some heap-allocated objects. It’s not registered yet, but I wonder if it is a reasonable workaround:

- Is there already a (packaged) solution like this?
- Is it a “safe” solution? (Other than the usual caveat of using `@generated` and lowered IR.)

I’ll register this package if there is no package out there that already does this and if this approach is not completely broken.

Quoting the [README](https://github.com/tkf/Restacker.jl):

* * *

In Julia (as of 1.4) immutable objects containing heap-allocated objects _may not_ be stack-allocated sometimes⁽¹⁾ and that’s why using something like `view` can degrade performance substantially. Restacker.jl provides an API

```
immutable_object = restack(immutable_object)

```

to put `immutable_object` in the stack and avoid this performance pitfall.

⁽¹⁾ It seems that this tends to happen when such an object crosses non-inlined function call boundaries. See also [this](https://discourse.julialang.org/t/stack-allocation-for-structs-with-heap-references/2293) and [this](https://discourse.julialang.org/t/immutables-with-reference-fields-why-boxed/7706) discussions in Discourse and also this old PR [JuliaLang/julia#18632](https://github.com/JuliaLang/julia/pull/18632).

## Example

Consider simple computation kernel

```julia
@noinline function f!(ys, xs)
    @inbounds for i in eachindex(ys, xs)
        x = xs[i]
        if -0.5 < x < 0.5
            ys[i] = 2x
        end
    end
end

```

This works great with raw-`Array` but the performance with `view`ed array is not great:

```julia
julia> using BenchmarkTools

julia> xs = randn(10_000);

julia> @benchmark f!($(zero(xs)), $xs)
BenchmarkTools.Trial:
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 1.989 μs (0.00% GC)
  median time: 2.033 μs (0.00% GC)
  mean time: 2.189 μs (0.00% GC)
  maximum time: 6.785 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 10

julia> @benchmark f!($(view(zero(xs), :)), $(view(xs, :)))
BenchmarkTools.Trial:
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 47.223 μs (0.00% GC)
  median time: 49.227 μs (0.00% GC)
  mean time: 51.072 μs (0.00% GC)
  maximum time: 133.803 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1

```

It turned out that `restack`ing the destination array `ys` is enough to fix the problem in `f!` above:

```julia
using Restacker

@noinline function g!(ys, xs)
    ys = restack(ys)
    @inbounds for i in eachindex(ys, xs)
        x = xs[i]
        if -0.5 < x < 0.5
            ys[i] = 2x
        end
    end
end

```

Calling this function on `view` is now as fast as the raw-`Vector` version:

```julia
julia> @benchmark g!($(view(zero(xs), :)), $(view(xs, :)))
BenchmarkTools.Trial:
  memory estimate: 48 bytes
  allocs estimate: 1
  --------------
  minimum time: 2.021 μs (0.00% GC)
  median time: 2.097 μs (0.00% GC)
  mean time: 2.265 μs (0.00% GC)
  maximum time: 6.663 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 10

```

Notice the slight increase in the memory consumption. This is because `restack` re-creates the object in the stack.

See more examples in [`benchmark/`](https://github.com/tkf/Restacker.jl/tree/master/benchmark) directory.

## How it works

Consider an immutable type:

```julia
struct ABC{A,B,C}
    a::A
    b::B
    c::C
end

```

Then

```julia
abc = restack(abc)

```

is equivalent to

```julia
abc = ABC(
    restack(abc.a),
    restack(abc.b),
    restack(abc.c),
)

```

For mutable object like `x :: Array`, `restack` return the input as-is.

In general, `restack` is an identity function such that

```julia
restack(x) === x

```

Notice the triple-equality `===`. It means that `restack` does not change the behavior of the program while it may benefit run-time performance by sacrificing the memory consumption (slightly) and compile-time.

(Side notes: There is an even more experimental function `Restacker.unsafe_restack` to re-construct `mutable struct` as well. This is unsafe because it breaks the identity (`===`) and breaks the assumption of the code relying on `finalize`.)

Under the hood, `restack` on `struct` types work by directly invoking the [`new` expression](https://docs.julialang.org/en/latest/devdocs/ast/#Expr-types-1). This skips evaluating user-defined constructors and minimizes the run-time overhead.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 23, 2020, 4:45am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/2 "2020-02-23T04:45:56Z")

</div>

x-ref more analysis by Valentin on the example above:

[https://github.com/JuliaLang/julia/issues/34847](https://github.com/JuliaLang/julia/issues/34847)

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [February 23, 2020, 10:37am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/3 "2020-02-23T10:37:38Z")

</div>

> may not be stack-allocated sometimes

To clarify, it’s not that wrappers _sometimes_ can’t be put on the stack; it’s that when when the wrapper doesn’t “escape” (all uses of the wrapper are local to the fully-inlined function), the compiler typically elides creation of the wrapper. That is, it performs all the operations that are written in terms of wrapper operations instead directly on the parent object being wrapped. There’s more information about this here: [performance - Unexpected memory allocation when using array views (julia) - Stack Overflow](https://stackoverflow.com/questions/47590839/unexpected-memory-allocation-when-using-array-views-julia/47607539#47607539).

The performance hit you noticed goes way beyond the heap-allocated-immutable problem, because it’s interfering with the ability of the compiler to do proper alias analysis. The slowdown is mostly due to the fact that it’s generating worse code, not that it’s allocating a little blob of memory.

> I’ll register this package if there is no package out there that already does this and if this approach is not completely broken.

Speaking personally, I don’t think we want Restack.jl as part of our coding lifestyle, because a “do-nothing” package that magically helps performance seems like code-smell. But as a quite surprising discovery prompting an analysis that may improve the compiler ([Missing TBAA information on view · Issue #34847 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/34847)) this is great! Nice detective work by you & Valentin. How on earth did you discover that this helped?

Of course, if this is something that will take a couple of years to fix, then it might be worth registering Restack.jl. But I think it would be much better for the long term to just wait a bit and see whether the fix comes relatively quickly.

---

<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:** [February 23, 2020, 3:42pm UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/4 "2020-02-23T15:42:33Z")

</div>

> [@tim.holy](#):
>
> Speaking personally, I don’t think we want Restack.jl as part of our coding lifestyle, because a “do-nothing” package that magically helps performance seems like code-smell. But as a quite surprising discovery prompting an analysis that may improve the compiler ([https://github.com/JuliaLang/julia/issues/34847](https://github.com/JuliaLang/julia/issues/34847)) this is great! Nice detective work by you & Valentin. How on earth did you discover that this helped?

I strongly agree with this statement. I was personally even more surprised by [https://github.com/tkf/Restacker.jl/blob/master/benchmark/bench\_unique.jl](https://github.com/tkf/Restacker.jl/blob/master/benchmark/bench_unique.jl) where the `restack` on the return variable allows us to ellide an allocation in the loop (probably because it is no longer escaping the function).  
Personally I want to see every case where `restack` works analyzed and understood so that the Julia compiler gets better and we don’t need “magic” compiler annotations. I have the same feeling about `@avx` and `@simd` (the latter is useful due to the semantics of reductions). I am happy to attempt to triage these things and at least give an educated guess on examples where this helps.

---

<div class="post-metadata">

**Author:** ![PhilipV](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/philipv/32/6852_2.png) [@PhilipV](https://discourse.julialang.org/u/PhilipV)\
**Post date:** [February 23, 2020, 4:01pm UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/5 "2020-02-23T16:01:45Z")

</div>

I’d personally be curious to how this relates to UnsafeArrays.jl when working with views. From a very high level point of view they both seem to be eliding the allocations when you use views, but would they lead to different speed ups?

I should benchmark…

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [February 23, 2020, 10:13pm UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/6 "2020-02-23T22:13:22Z")

</div>

> [@tkf](#):
>
> Is there already a (packaged) solution like this?

> [@PhilipV](#):
>
> how this relates to UnsafeArrays.jl when working with views

UnsafeArrays tackles the same problem - heap-allocated views (and similar structures containing with array references), but in a different way: UnsafeArrays replaces standard `Array`s by pointer-based `UnsafeArray`s (which are bitstypes and stack-allocated), while protecting the original array from GC. All views, etc., on `UnsafeArray`s are automatically stack allocated as well. This is very efficient, esp. with highly muli-threaded code, but also somewhat dangerous, because it is the user’s responsibility to ensure that no `UnsafeArray`s escapes it’s `@uviews` environment (which protects the original `Array` from GC).

I don’t have a mechanism in `UnsafeArrays` that rewrites existing structs (like `_restack`) does (but I’ve been thinking about it). Is is possible to add `@uviews` support to a custom struct by implementing `UnsafeArrays.unsafe_uview`, though (`ArraysOfArrays` implements this interface, for example). Maybe Restacker could offer a similar interface for types that are too complex for the automatic `_restack`, and need custom code?

Long-term I hope both UnsafeArrays and Restacker (nice approach) will just be stop-gaps, of course, until Julia supports stack-allocation of immutables that contain heap-references. As core-counts continue to increase, that will become more and more important. I believe there’s been some progress with this, recently, is that correct?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [February 23, 2020, 11:25pm UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/7 "2020-02-23T23:25:29Z")

</div>

> [@tim.holy](#):
>
> Speaking personally, I don’t think we want Restack.jl as part of our coding lifestyle, because a “do-nothing” package that magically helps performance seems like code-smell.

I _totally_ agree with this. It is exactly why I initially called this function [`darkritual`](https://github.com/tkf/Transducers.jl/blob/9471e306f0421b572aa419ca471ad53de8306cd0/src/processes.jl#L714-L727); I am sacrificing my sanity to get some performance improvements. I think this is an unfortunate reality that you sometimes need this kind of do-nothing “nudge” to the compiler (e.g., [FastClosures.jl](https://github.com/c42f/FastClosures.jl)). I do want to throw away this kind of hacks as soon as possible . But if I can write “zero-cost” abstractions with a little hack like this, I think the situation is not so horrible.

By the way, fortunately for us, there is an open PR to fix (some of?) the problem:

> <https://github.com/JuliaLang/julia/pull/34126>

So let’s hope that we can forget about it pretty soon.

> [@tim.holy](#):
>
> The performance hit you noticed goes way beyond the heap-allocated-immutable problem, because it’s interfering with the ability of the compiler to do proper alias analysis.

As @vchuravy mentioned [above](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/4), there is a (possibly) different class of problem “solvable” by `restack`. Here, just [re-creating `Tuple{Set{Int}, Vector{Int}}` _at the end of the function_](https://github.com/tkf/Restacker.jl/blob/be9f2bb99d6e68b31f8e5cb37e54ba761b18ea70/benchmark/bench_unique.jl#L37) somehow helps the compiler generating a better code. It seems this case is more related to your post on StackOverflow?

> [@oschulz](#):
>
> > [@tkf](#):
> >
> > Is there already a (packaged) solution like this?
> 
> > [@PhilipV](#):
> >
> > how this relates to UnsafeArrays.jl when working with views
> 
> UnsafeArrays tackles the same problem

Thanks, that’s a good point. I think UnsafeArrays.jl is a more direct solution if you know you are working on arrays. Restacker.jl is more general as it works with any objects (e.g., there is an example with `Set`). But, due to this generality, I imagine it is likely less powerful than UnsafeArrays.jl in some situations.

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [December 28, 2021, 4:24am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/8 "2021-12-28T04:24:35Z")

</div>

Does [https://github.com/JuliaLang/julia/pull/42465](https://github.com/JuliaLang/julia/pull/42465) solve the problems listed in this thread?

* * *

Edit: @foobar_lv2 are your issues from [Immutables with reference-fields: Why boxed? - #19 by foobar\_lv2](https://discourse.julialang.org/t/immutables-with-reference-fields-why-boxed/7706/19) solved?

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [December 28, 2021, 5:17am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/9 "2021-12-28T05:17:02Z")

</div>

As far as I understand, this was already resolved in [Julia v1.5](https://docs.julialang.org/en/v1.5/NEWS/). The `NEWS` entry cites [#34126](https://github.com/JuliaLang/julia/pull/34126) [#33886](https://github.com/JuliaLang/julia/pull/33886) as relevant to the improvement.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [January 29, 2022, 4:37am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/10 "2022-01-29T04:37:42Z")

</div>

You can always check it yourself to see if it still matters. The benchmark `unique` is fixed by Julia 1.5. But benchmark `filter_map` still shows the difference as of current Julia `master`:

```julia
julia> VERSION
v"1.8.0-DEV.1429"

julia> include("benchmark/benchmarks.jl")

julia> result = run(SUITE; verbose = true)
...
2-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "unique" => 2-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "norestack" => Trial(4.380 μs)
          "restack" => Trial(4.440 μs)
  "filter_map" => 2-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "norestack" => Trial(42.820 μs)
          "restack" => Trial(5.839 μs)

```

Edit: As a slightly different and more “real world” example, I revisited this recently and the benchmark in [https://github.com/JuliaFolds/Transducers.jl/pull/504](https://github.com/JuliaFolds/Transducers.jl/pull/504) shows that the previous observation [https://github.com/JuliaFolds/Transducers.jl/pull/459](https://github.com/JuliaFolds/Transducers.jl/pull/459) still holds.

---

<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:** [January 30, 2022, 10:28am UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/11 "2022-01-30T10:28:22Z")

</div>

I don’t know anything about this or the vocabulary, so I want to ask how restack is improving the performance of filter\_map.

Are some immutables being heap-allocated in the norestack version? I know immutables are typically stack/inline-allocated since v1.5, but I never completely ruled out the compiler deciding to heap-allocate in extreme cases, is this what’s happening?

What is a pointer-free type, is that like an isbitstype?

If possible, try to dumb it down a lot for me, I really don’t know anything about the compiler or how it can be tweaked.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [January 30, 2022, 6:22pm UTC](https://discourse.julialang.org/t/rfc-ann-restacker-jl-a-workaround-for-the-heap-allocated-immutable-problem/35037/12 "2022-01-30T18:22:11Z")

</div>

For further analysis please see:

[https://github.com/JuliaLang/julia/issues/34847](https://github.com/JuliaLang/julia/issues/34847)