I was confused reading the docs (https://docs.julialang.org/en/stable/manual/types/#Mutable-Composite-Types-1), where it says that mutable structs “are generally allocated on the heap”. Reading this paragraph it wasn’t clear to me that eliding the allocation was guaranteed, or what is the rule to know when the allocation happens or not. I guess this paragraph says it, but it was hard to digest:
Mutable values, on the other hand are heap-allocated and passed to functions as pointers to heap-allocated values except in cases where the compiler is sure that there’s no way to tell that this is not what is happening.
Your reply clarifies this, thanks.
The array storage is a different question. Here I also don’t understand why an array of mutable struct (with size known at compile-time) cannot be stored contiguously? Is there a simple example showing why this optimization cannot be guaranteed?
It’s because of the semantics of mutables in Julia.
mutable struct Foo
x
end
a = Foo(1)
b = [a, a]
b[2].x = 10
@show a b
After running this code, there’s only one Foo object alive, whose value is 10. It would be impossible to preserve those semantics if b stored the Foo objects contiguously (since it would have to make two copies of the Foo in a
This reminds me of the distinction between struct and class in C#. But it is different from C++, where any type can be allocated on the heap (using new, malloc) or on the stack (if it is a local variable declaration), regardless of the type in question.
As usual for any discussion about allocation, you have to specify which level you are talking about. There are two very different levels, one is the language semantics and the other one is optimization. (I won’t talk about c# since I’ve basically never used it seriously, only as a VB replacement ~8 years ago.)
As for semantics level. There are differences between heap and stack allocation in C++. However, there’s no “stack” in julia semantics and conceptually, everything in julia are allocated the same way (you can call it the heap, but it really doesn’t matter). This is true for all julia objects, mutable or immutable, isbits or not.[1]
As for optimization level. There are actually less difference between C++ and julia, at least for the subset that can be expressed in both language easily. Both C++ (mordern compilers) and julia do extensive allocation elimination. Since julia does not give you any way to specify where you want to allocate something, it relies much heavily on the allocation elimination and also define the semantics such that the allocation can be elided in more cases more reliably (cases that you would have just use a stack variable in C++). This is where immutability/isbits/escape analysis comes in. In the end, the two languages could achieve a similar level of allocation in the final code (while compilers for both languages still both have cases to improve on for sure, more so for julia).
[1] Struct/Array ABI does couple the two levels slightly, but you can still view it as one of the many implementations allowed by the semantics that is favored by the optimization that could be done on it.
I think that what confused me was this sentence from the docs about mutable structs:
In order to support mutation, such objects are generally allocated on the heap, and have stable memory addresses.
This seems to imply that heap allocation is necessary for mutation, which is not true if I understand correctly what you have explained here. Perhaps this section of the docs could be worded better in the future.
Why these particular semantics were chosen for mutable struct vs. (immutable) struct in Julia? Why storing mutables as refs is a good thing? Since C# does this too, I suspect there are strong and possibly general arguments supporting this approach?
It says heap allocation is generally (read: usually) required for stable memory address (which represent object identity for mutable objects). So the logic is that, in order to support mutable, the only object identity you can have is the address (or if you want to take address out of the picture, you at least need a way to distinguish object constructed differently but have the same value), which means that you’ll usually need to heap allocate it.
The doc could be better, but it is also a bad idea to go deeply into optimization when introducing a concept. It’s of course very hard in this context to not talk about optimizations at all since some of the optimizations are “guaranteed” for type stable code but this part of the doc should (edit: not) go into all the details about what optimization can the compiler do.
After all, for non-escaping allocation, the compiler can literally do anything about the object including eliminate it (i.e. not allocating it at all). It’s also not wrong by saying that they are usually allocated on the heap since they are either allocated on the heap or not allocated at all (i.e. when they are allocated, it’s almost always on the heap).
It is very common for scripting language to only have one object passing semantics (by reference) and this is basically another way of saying assignment is a no-op or there’s no concept of stack/local variable in C in the language. (Note that this is basically the same as saying all objects are conceptually allocated on the heap.)
On top of this, immutable object seems to be a pretty standard concept and in this case is really efficient to allow arbitrary allocation for immutable objects so it makes sense to have it though I have no idea how it was originally decided…
(edit: pressed Ctrl-Enter by accident)
Why storing mutables as refs is a good thing?
It’s not a good thing. With the current computer architecture where values are stored in memory and pointers to those memory location are called pointer/reference, this is the only (or at least the simplest) thing you can do to keep track of object identity.
It doesn’t matter if x is concrete or isbits or not. It’s also not the compiler’s job to decide if something need to have a stable address, that’s the semantics. And all mutable object must have stable address, so it’s unclear what do you mean by “mutable but …”.
It will always occupy 16 bytes even though x and y may be modified to different numbers at any point in time. An array of such struct should have a fixed length i.e. number of elements x 16 bytes. So, why can’t Julia allocate this memory in the stack as a contiguous block of memory?
Object size has nothing to do with anything discussed in this thread. FWIW, fixed object size also has nothing to do with isbits. Almost all leaf types have fixed size in julia (with the exception of Array, Symbol, String and SimpleVector).
As mentioned many times above, the important thing is the identity of the object. Bare (i.e. without convert) assignments are always no-op so the object you load from the array must be exactly the same one you stored before. This is true for both mutable and immutable object. The only reason immutable object is allowed to be stored inline is because you couldn’t tell weather a copy has happened or not, since you couldn’t mutate the object and observe that different response from the copy and the original one like you could do with mutable object (i.e. if you mutate the copy, the orignal object won’t be mutated).
I’m not sure what’s your background but since your arguments could in principle be C++ based I would emphasise again that bare assignments being always no-op in julia is the major difference with C++. Every object is conceptually a pointer in julia though the immutability allows us to not implement it as such and provide a more machine and C/C++ friendly ABI for these types.
Objects on the stack also have stable memory address during their lifetime (until the function scope ends). If I understand correctly, the issue with objects that escape. In their case heap is the only way to guarantee a stable memory address.
… OK, so you shift from array (field) storage to local variables again.
Anyway, in general, for object that does not escape, the compiler can do whatever it wants. It usually isn’t necessary to talk about address, let alone stable address, in this context anymore.
That’s a pretty good guess. My previous background is mostly C and Java. (Today, I would say it’s Julia ) I haven’t done much coding in C for over 18 years, but my understanding is that if I have an array of structs then the data should occupy a contiguous memory space. That’s because C structs are value types.
As Julia struct’s are actually objects, they are generally referenced by pointers. But, when it’s immutable, the compiler can make copies for optimization reason - less indirection?
All field/slots are storing object reference and not values and so they in general have to be reference/pointer. However, when it’s immutable, it doesn’t have to. This part is correct.
What is a little bit inaccurate is that this is not only an optimization. For anything user observable without looking at compiled code like an array of struct, this is a decision made in the semantics of the language for performance reason. The compiler, for example, does not have the freedom to change the layout of most types/arrays so it could not do this “optimization”. It has observable effect and has to be defined beforehand.
I think I’ve mentioned this above already, but this is actually the only case where the mutability of the type makes a fundamental difference. The rule for the compiler is simply that the observable effect are the same. There are of course more user observable properties for a mutable object so there are fewer things that the compiler can do, but other than this, mutable type and immutable type does not make much difference for the compiler. In particular, the compiler can do copying for either muable or immutable objects when it see fit.
I checked if compiler really does optimize to llvm code that modifies in the immutable struct place without having to copy and it really works. pretty cool.
struct Pnt
a::Int64
b::Int64
c::Int64
d::Int64
e::Int64
f::Int64
g::Int64
end
function modify(arr::Vector{Pnt}, i::Int, v::Int64)
@inbounds arr[i] = Pnt(v, arr[i].b, arr[i].c, arr[i].d, arr[i].e, arr[i].f, arr[i].g)
#unsafe_store!(Ptr{Int64}(pointer(arr, 1)), v)
nothing
end
modify (generic function with 3 methods)
(Main.TempModule) julia> @code_llvm modify(arr, 1, 20)
; @ REPL[60]:1 within `modify`
define void @julia_modify_4537({}* noundef nonnull align 16 dereferenceable(40) %0, i64 signext %1, i64 signext %2) #0 {
top:
; @ REPL[60]:2 within `modify`
; ┌ @ essentials.jl:13 within `getindex`
%3 = add i64 %1, -1
%4 = bitcast {}* %0 to [7 x i64]**
%arrayptr47 = load [7 x i64]*, [7 x i64]** %4, align 8
; └
; ┌ @ array.jl:1021 within `setindex!`
%newstruct.sroa.0.0..sroa_idx = getelementptr inbounds [7 x i64], [7 x i64]* %arrayptr47, i64 %3, i64 0
store i64 %2, i64* %newstruct.sroa.0.0..sroa_idx, align 8
ret void
; └
}
) I haven’t done much coding in C for over 18 years, but my understanding is that if I have an array of structs then the data should occupy a contiguous memory space. That’s because C structs are value types.