Stack allocation of `isbits` types in Julia

4
votes

Summary of question and answers

Objects of a particular type, say

type Foo
    a::A
    b::B
end

can be stored in either of two ways:

  • Inlined (aka by value): in this case, the statement "variable foo::Foo is stored at location x" effectively means we have a variable foo.a::A at location x and a variable foo.b::B at location x + sizeof(A) (technically the addresses could be a bit more complicated, but that's irrelevant for our purposes).

  • Referenced (aka by reference): "foo::Foo is stored at location x" means the location x contains a pointer fooptr::Ptr{Foo} such that there is a variable foo.a::A at location fooptr and foo.b::B at location fooptr + sizeof(A).

Unlike other languages (I'm looking at you, C/C++), Julia decides by itself whether to store variables inlined or referenced, and it does so based on the properties of the type:

  • mutable types -> referenced,
  • immutable types -> referenced if at least one of its fields is referenced, inlined otherwise.

There are at least two reasons for this rule:

  • StefanKarpinski's answer: The garbage collector needs be able to find all pointers to heap-allocated objects on the stack. Currently, Julia ensures this by storing all such pointers on a separate "shadow stack", but if we allowed composite types containing pointers to be placed on the stack then such a neat separation would no longer be possible. Instead, the compiler would need to look for pointers among other variables which poses technical difficulties.

  • yuyichao's answer: Julia requires the inline/reference decision to be made on a per-type rather than per-object basis, which means a hypothetical type 

    immutable A
    a::A
end

    would have to be infinitely big if we insisted on inlining it. So we would either have to forbid such recursive immutable types, or we could at most allow non-recursive immutable types to be inlined.

Original question

My understanding of memory management in Julia is:

  • mutable types -> heap-allocated,
  • immutable types and tuples -> stack-allocated unless one of their fields is heap-allocated (i.e. mutable).

I don't quite understand the rationale for this behaviour, however. I've read somewhere that the problem with stack-allocating immutables with pointers to mutables is that then the garbage collector might consider the mutables unreachable and destroy them prematurely. On the other hand, if we place the immutable on the heap then there will still be a pointer to the mutables, so it might seem like we avoided the problem, but actually we just shifted it to making sure that now the immutable itself will not be destroyed.

Can anyone explain this to me who has only very superficial knowledge of how garbage collection works?

2
garbage-collectionjulia
We would not forbid recursive type, just compute at type definition time that it is "loopy" in a predictable way and make all parameterization of the type non-inline. - yuyichao
That works too, although it does sound like a lot of effort just to allow immutable types to be referenced. - gTcV
Well, we'll need a way to determine this anyway so it's just a difference between throwing an error and not. - yuyichao
And you now need two fields to mark whether the type is mutable and whether it is inlined. Basically the point is that allowing recursive immutables makes the rules more complicated, and I fail to see where I would really benefit from this extra complication. - gTcV
Beause a immutable type is useful for other things including catching errors when you accidentally write to a field you didn't intended; letting the compiler hoist a load since the object will not change. We're also in no shortage of the negligible amount of memory needed to store one more bit that'll never be modified at runtime. - yuyichao

2 Answers

6
votes

The problem with stack-allocation of objects which reference other objects is knowing that they need to be traced during garbage collection. The simplest way to do this is what Julia does: heap allocate the objects and "root" them using "shadow stack" which is pushed and popped in sync with the actual stack. This introduces a fair bit of overhead and forces these objects to be heap allocated.

A more sophisticated approach that avoids the overhead of a shadow stack and heap allocation is to stack allocated these objects and then scan the stack which doing garbage collection and follow references from objects in the stack to objects on the heap. However, this requires knowing which objects in the stack are pointers to objects on the heap – in general, non heap-allocated objects are not guaranteed to be kept intact or contiguous in registers or the stack. One approach to doing this is called "conservative stack scanning" which entails assuming during gc that any value on the stack which looks like it could be a pointer to an object on the heap actually is. That approach has been successfully used in applications like Safari's JavaScript engine, but it's not without it's challenges. We've contemplated using conservative stack scanning in Julia, and an initial effort to do so was started but the effort was never completed.

References:

5
votes

There are multiple issues/concepts that are frequently mixed together whenever this is brought up.

  1. mutable or non-pointerfree immutable doesn't necessarily mean heap allocation, we already have optimization passes to elide some of the optimizations and are working on improving them further.

  2. The object layout ABI is an user visible behavior and not something an optimization pass can easily change (unless it can prove that the local optimization it wants to do does not escape). The current ABI is that only isbits immutable will be stored inline (and "stack allocated" when used as local variable). There's a fundamental limitation of lifting the requirement of pointerfree-ness for inlined object, i.e. the necessity to handle recursive types. It is impossible to make all types in a reference circle stored inline and the loop has to be broken somewhere if we want to make some of them inlined. I believe we do have a consistent and predictable model to do this though whether this is desireable is another issue.

    This is somewhat related to performance but not always. Stored inline means more copy so it's hard to make sure there's no regression if we do the switch.

    Edit: And I should also mention that pointer-free is a sufficient condition for cycle free and is easier to compute, which is partly why we are currently using it to break inlining cycles.

  3. GC support. This is basically the easiest part. It's very easy to make GC recognize pointers on the stack. It just needs to be done if we decide to change the object layout ABI.

    Edit: And I should add that "GC support" is needed because we currently only support a limited / simple stack layout for object reference (i.e. an array of pointers). It's this that needs to be improved.