# Memory layout of structs with mutable fields

**URL:** <https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400>\
**Category:** Performance\
**Created:** [March 2, 2019, 7:21pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400 "2019-03-02T19:21:30Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [March 3, 2019, 1:41pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/21 "2019-03-03T13:41:05Z")

</div>

I was thinking of asking for a valid chunk of heap memory of the size for the amount of elements I want to fill in, and then copy paste the previously created ones into it.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [March 3, 2019, 1:44pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/22 "2019-03-03T13:44:34Z")

</div>

As far as I understood, this really is foremost about implementation issues, not about tradeoffs.

One of the most relevant cases is

```julia
struct some_wrapper{parentT, extra1, extra2, extra3}
parent::parentT
end

```

where `parentT` is non-bitstype, e.g. `Vector{Int}`.

Such objects should always be stored inline, both in arrays and in other `struct` or `mutable struct`, and only ever get heap-allocated in non-inferred code. There is no trade-off: We simply pay an extra object allocation plus pointer indirection for no gain.

I would be super happy if `struct` with a single non-singleton field could be special cased to simply be the pointer to the parent; then, all such abstractions would be guaranteed to be always zero-cost in type-stable settings (and afaict this would not even need changes to garbage collection).

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 1:49pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/23 "2019-03-03T13:49:45Z")

</div>

You can’t store references that way

---

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [March 3, 2019, 1:53pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/24 "2019-03-03T13:53:20Z")

</div>

Because? I actually have trouble finding what references exactly are in Julia, I thought they were kind of like gc registered pointers, can’t I move them around?

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 1:56pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/25 "2019-03-03T13:56:42Z")

</div>

> [@foobar\_lv2](#):
>
> As far as I understood, this really is foremost about implementation issues, not about tradeoffs.

Well, as I said above, there’s certainly cases where the performance issue is not a problem but that doesn’t make it not a tradeoff.

> [@foobar\_lv2](#):
>
> `struct` with a single non-singleton field

First note that that doesn’t fix the OP’s question.  
And this definitely come up in related discussion (I remember talking about it in at least 2 occasions).

It’ll be a very strange API. What stops you from stopping at one field for example. It’s almost certainly still a win for 2 fields. Additionally, `Tuple` of one element and of two element are going to have completely different layout.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 1:57pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/26 "2019-03-03T13:57:05Z")

</div>

Yes they are managed by the GC so you must not move them around without letting the GC know about it.

---

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [March 3, 2019, 2:00pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/27 "2019-03-03T14:00:04Z")

</div>

I guess I’m not meant to interact with the gc in any way?

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 2:02pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/28 "2019-03-03T14:02:21Z")

</div>

Well, even if you don’t interact with GC in any way the GC will still interact with you by freeing the objects behind you. Even if you keep them alive elsewhere the code you write won’t be directly comparable since it’s missing the few extra instructions when you are interacting with the GC.

---

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [March 3, 2019, 2:16pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/29 "2019-03-03T14:16:16Z")

</div>

Is the basic issue with moving references around that the GC tracks them through pointers to their memory position? Can I repoint those tracked pointers? – I’m getting a little offtopic

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 2:18pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/30 "2019-03-03T14:18:35Z")

</div>

> [@louisponet](#):
>
> Is the basic issue with moving references around that the GC tracks them through pointers to their memory position? Can I repoint those tracked pointers?

Errr I’m actually not sure what do you actually mean… But in any case, the answer is most definitely no. We don’t have any julia API to manage object references. (other than accessing/assigning fields/arrays)

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [March 3, 2019, 2:40pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/31 "2019-03-03T14:40:01Z")

</div>

> [@yuyichao](#):
>
> It’ll be a very strange API.

So what? Let the perfect not be the enemy of the good. Adding type information to some parent without adding data is a common enough pattern, and the performance tradeoff is completely unambiguous.

> [@yuyichao](#):
>
> What stops you from stopping at one field for example. It’s almost certainly still a win for 2 fields. Additionally, `Tuple` of one element and of two element are going to have completely different layout.

```struct
some_ref::T 
big_payload::NTuple{500, UInt64} 
end

```

is a possible counterexample to deciding inlining on the number of fields. Furthermore, if multiple fields can get inlined, then somebody would need teach the garbage collector that arrays can contain a mix of pointers and non-pointers. For this special case, this issue goes away.

The single-pointer special case would not distinguish the layout of one and two-element tuples; for example, types like `Tuple{Vector{Int}, Nothing, Missing, Val{42}}` or `Tuple{Tuple{typeof(sum), Vector{Int}}, Val{0}}` would still be inline (because we only have one non-singleton element). Singleton fields are important for parametric types that have a field `<:Function`: You must have this as a field in order to correctly work on closures, but in the case of standard functions, it is a singleton that is not stored at all.

The next generalization would be: `struct` that is pointer-homogeneous (all fields are concrete (esp. non-`Union`) references or singletons, and size \< N) get inlined (apply recursively). There is no possibility of instantiating objects that would become circular, so this is well-defined. This would still require no change in the garbage collector.

edit: The proposed optimization could be alternatively described as: Always collapse immutable pointer chains. This would never increase storage demands, and would not require gc changes.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 2:55pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/32 "2019-03-03T14:55:09Z")

</div>

> [@foobar\_lv2](#):
>
> Let the perfect not be the enemy of the good.

That’s a very bad arguement. It’s not perfect vs good here since it’s not just a simple optimization. You **WILL** get people confused by doing this.

> [@foobar\_lv2](#):
>
> is a possible counterexample to deciding inlining on the number of fields.

So basically what you are proposing is completely irrelevant to this thread.

> [@foobar\_lv2](#):
>
> teach the garbage collector that arrays can contain a mix of pointers and non-pointers

That’s trivial. The codegen and runtime part is much harder.

> [@foobar\_lv2](#):
>
> would still be inline (because we only have one non-singleton element).

What? I’m talking about `Tuple{BigInt}` and `Tuple{BigInt,BigInt}` have completely different behavior.

> [@foobar\_lv2](#):
>
> `struct` that is pointer-homogeneous (all fields are concrete (esp. non- `Union` ) references or singletons, and size \< N)

And that’s exactly the bad direction.

> [@foobar\_lv2](#):
>
> There is no possibility of instantiating objects that would become circular, so this is well-defined.

Why not? `struct A x::A y::A end`?

> [@foobar\_lv2](#):
>
> This would still require no change in the garbage collector.

I don’t know why everyone keep mentioning the GC. The GC is actually the easiest part since it’s very strictly controlled code. The runtime and codegen handling is much harder. Still, most of the pieces are there but it’s just not a good time to make the change and partial changes like what you propose here is just very “dirty” and without a clear definition of where it should stop, making it unpredictable.

---

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [March 3, 2019, 2:58pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/33 "2019-03-03T14:58:38Z")

</div>

It seems that right now, to do what I want to do, the easiest way is to just create indeed the version with a pointer to arrays stored separately, and manage the validness of those pointers myself.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 3:02pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/34 "2019-03-03T15:02:52Z")

</div>

Don’t do that. It’s at most a premature optimization.

---

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [March 3, 2019, 3:04pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/35 "2019-03-03T15:04:48Z")

</div>

I agree, it’s more a theoretical idea.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 3:06pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/36 "2019-03-03T15:06:50Z")

</div>

Now depending on your actual usage, you might be able to use two separate arrays for the two fields, i.e. StructOfArrays. That is **still** a pre-mature optimization if you do that **now** but once you know **everything** about your usage it’s very an valid optimization that you can apply, unlike the one you proposed, which seems to bypass everything in julia.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 3:09pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/37 "2019-03-03T15:09:32Z")

</div>

> [@yuyichao](#):
>
> Why not? `struct A x::A y::A end` ?

And I’ll add that even a single field will have the same issue. So one additional minor argument is that Jeff really didn’t like the rule related to circular references even though we proved that it can be decided at type definition time.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [March 3, 2019, 3:30pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/38 "2019-03-03T15:30:27Z")

</div>

> [@yuyichao](#):
>
> Why not? `struct A x::A y::A end` ?

And how do you instantiate an object of type `A`? You would need an inner constructor that permits uninitialized fields (and whether fields can be uninitialized is part of the type information).

> [@yuyichao](#):
>
> without a clear definition of where it should stop, making it unpredictable.

Clear definition: Collapse all concrete immutable always-initialized pointer chains. Whenever you would store `x::T` and `T` is concrete, immutable, non-isbits, cannot have uninitialized fields and has `sizeof(T) == sizeof(Ptr{Nothing})`, then store the contents of `x` instead of a reference to an object of type `T` with the contents of `x`.

Sizes of structs or tuples, whether they are pointer or bitstype, sizes of fields, etc all do not change. Sizes of arrays, and whether they are pointer-type do not change. Only change is that intermediate objects in pointer chains that can be reconstructed from type-information become implicit instead of explicit.

But obviously you know far better how difficult such a change would be!

I am only arguing that this optimization/change would be an unambiguous improvement that would affect a lot of code.

If such an optimization is beyond current dev resources, or too difficult, well, that’s a very good reason for not having it! Or if the reason is “that would make the C interface too complicated”, sure. But I completely disbelieve claims like “this would be an ambiguous performance trade-off”.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 3, 2019, 3:33pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/39 "2019-03-03T15:33:26Z")

</div>

> [@foobar\_lv2](#):
>
> You would need an inner constructor that permits uninitialized fields

Yes?

> [@foobar\_lv2](#):
>
> whether fields can be uninitialized is part of the type information

No it’s not. It’s only used for optimization now and not part of any API.

> [@foobar\_lv2](#):
>
> I am only arguing that this optimization/change would be an unambiguous improvement that would affect a lot of code.

I agree, I’m only saying it’s a big and “dirty” change, and together with all change of similar nature, it’s not a good time to do it without doing other changes first.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [March 3, 2019, 4:09pm UTC](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400/40 "2019-03-03T16:09:14Z")

</div>

> [@yuyichao](#):
>
> No it’s not. It’s only used for optimization now and not part of any API.

Thanks for explaining that!

> [@yuyichao](#):
>
> I agree, I’m only saying it’s a big and dirty change, and together with all change of similar nature, it’s not a good time to do it without doing other changes first.

I’ll disagree on “dirty”, but more interestingly: Could you elaborate on the other changes that should come first?

One issue is what you brought up: whether a field can be null wants to become a proper part of the type information, not just a mere optimization: `struct foo x::foo end` is uninhabited / has no instances, i.e. is equivalent to `Union{}`, and `struct bar x::bar bar()=new() bar(v::bar)=new(v) end` is effectively a peano-style natural number. Both are semantically very different types, and that wants to be reflected in the type information. That’s just an issue of making this info (that is already accessible) part of the official API, and potentially fixing some user-facing syntax (e.g. type definitions would get an optional `@dereferenceable x::T` or `@nullable x::T` to make this part explicit for people who don’t want to rely on the compiler to decide whether a field can be nullpointer)

A second issue that you explained to me some time ago is that access to possible nullpointers maybe wants to be handled via cpu trap, instead of runtime checks and throws. Big change for codegen that waits on better llvm support, but I don’t see how this directly relates.

What else are the changes that should be done first?

[Previous page](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400.md?page=1)

[Next page](https://discourse.julialang.org/t/memory-layout-of-structs-with-mutable-fields/21400.md?page=3)