# Stack allocation for structs with heap references

**URL:** <https://discourse.julialang.org/t/stack-allocation-for-structs-with-heap-references/2293>\
**Category:** Internals & Design\
**Created:** [February 24, 2017, 9:57pm UTC](https://discourse.julialang.org/t/stack-allocation-for-structs-with-heap-references/2293 "2017-02-24T21:57:39Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![davidanthoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/davidanthoff/32/223493_2.png) [@davidanthoff](https://discourse.julialang.org/u/davidanthoff)\
**Post date:** [February 24, 2017, 9:57pm UTC](https://discourse.julialang.org/t/stack-allocation-for-structs-with-heap-references/2293/1 "2017-02-24T21:57:39Z")

</div>

> [@Julia motivation: why weren't Numpy, Scipy, Numba, good enough?](https://discourse.julialang.org/t/julia-motivation-why-werent-numpy-scipy-numba-good-enough/2236/29):
>
> a crucial optimization will be the whole stack vs heap for structs that contain “pointers” to heap-allocated memory: these iterators need to create a crazy number of wrappers for operations working on small chunks of arrays.

I just want to point out that this optimization should also help [Query.jl](https://github.com/davidanthoff/Query.jl) a lot, I also iterate like mad over small immutables that can hold references to heap allocated stuff. I just tried to find an issue or PR that gives the latest status/efforts/plans on that front but didn’t really find something. I’d be quite interested in learning about the current plans on this, any pointer would be most welcome.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [February 24, 2017, 10:11pm UTC](https://discourse.julialang.org/t/stack-allocation-for-structs-with-heap-references/2293/2 "2017-02-24T22:11:33Z")

</div>

> [@Julia motivation: why weren't Numpy, Scipy, Numba, good enough?](https://discourse.julialang.org/t/julia-motivation-why-werent-numpy-scipy-numba-good-enough/2236/30):
>
> I just want to point out that this optimization should also help Query.jl a lot, I also iterate like mad over small immutables that can hold references to heap allocated stuff. I just tried to find an issue or PR that gives the latest status/efforts/plans on that front but didn’t really find something. I’d be quite interested in learning about the current plans on this, any pointer would be most welcome.

> <https://github.com/JuliaLang/julia/pull/18632>
>
> The codegen/gc part of this is basically working.
> I'm now wondering about seman…tics and I'd like us to discuss the following issues a bit before I clean up the code and we start the review (there is a bunch of duplicate paths in codegen that can be merged together/simplified and some things are plain wrong and/or inefficient).
> 
> This patch allows us to unbox most immutables. By unbox I mean : allocate/store them on the stack, inline them in other objects and inline them in arrays.
> Why most ? There are (for now) two problems : cycles and #undef.
> 
> Cycles are a fundamental problem, if A has a field of type B and B of type A, we obviously can't inline them into each other. The cycle needs to be broken, the annoying part is that it should be done in a predictable way. For now, on this PR, it's done in DFS order which means that for example the layout of B will differ if we ever instantiated an A before. Not good. Proposal I remember about that (Jameson @ juliacon iirc) was to make types boxed iff they are part of any field cycle.
> \`#undef\` is annoying because it makes a difference at the julia level between \`isbits\` types and other immutables. To minimize breakage I've gone the route of preserving the current behavior.
> 
> So if A has a pointer field and we make, e.g., an uninitialized array of A, this branch uses the nullity of the field of A as a marker that the corresponding slot in the array is #undef. This only works if the field of a valid instance of A can never be null, i.e., if \`A.ninitialized \>= field\_index\_of\_the\_ptr\_field\`.
> 
> This makes most code (at least all the test suite :-)) work but I think the following rules are really weird :
> 
> A type \`T\` will be inlined into fields/arrays and stack allocated if
> \- it is immutable
> \- it is not possible to reach itself through a sequence of field access
> \- it has at least one never-#undef pointer field or no pointer fields at all
> 
> The only difference between a type that is boxed or not is memory layout, but I'd assume that we want that to be easily predictable since for example people routinely interface with C.
> 
> A proposed alternative by Yichao was to make it entierly opt-in and error out if inlining was not possible. I'm worried this will lead to yet-another-annotation that people will sprinkle everywhere.
> 
> For performance, specially crafted tests (like summing lines of a very skinny matrix using subarrays) show some improvements by avoiding gc allocation. Not super satisfying for now and casual inspection of generated asm shows a lot of stack movement. We can work on that though, probably by improving llvm's visibility of our rooting mechanism and/or just using statepoints.
> 
> (to sweeten the deal I've thrown in improved undef ref errors)

---

<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 25, 2017, 6:40am UTC](https://discourse.julialang.org/t/stack-allocation-for-structs-with-heap-references/2293/3 "2017-02-25T06:40:53Z")

</div>

This is definitely something I am looking forward to as well, but it requires someone with a deep understanding of how Julia GC is working and requires some non trivial work (e.g. stack scanning). AFAIK nobody is currently actively working on it.