Why mutable structs are allocated on the heap?

From https://docs.julialang.org/en/latest/manual/types/#Mutable-Composite-Types-1:

In order to support mutation, such objects are generally allocated on the heap, and have stable memory addresses.

If I define:

mutable struct MyT
x::Int
end 

and then use MyT inside a function, such as:

function f(x::Int) 
q = MyT(x);
q.x += 1
return q.x
end

I would expect q to be allocated on the stack, because it is a local variable that does not change type and MyT is isbits. But it is not:

@btime f(1) # 3.781 ns (1 allocation: 16 bytes)

Why?

1 Like

Julia has many optimisations, eliminating unnecessary allocations is one of them.

But in this case the allocation seems unnecessary, yet it occurs. Or am I missing something?

Sorry, on 0.7 this optimization is much more effective:

julia> @btime f(1)
  1.503 ns (0 allocations: 0 bytes)
2

julia> VERSION
v"0.7.0-rc3.3"
2 Likes

Is there an easy to state rule to know when something will be allocated on the heap vs. the stack? If not, is there a macro (something like @code_warntype) that alerts me when a variable is heap allocated?

0.6:

julia> @code_typed f(1)
CodeInfo(:(begin
        q = $(Expr(:new, :(Main.MyT), :(x))) # line 3:
        SSAValue(0) = (Base.add_int)((Core.getfield)(q, :x)::Int64, 1)::Int64
        (Core.setfield!)(q, :x, SSAValue(0))::Int64 # line 4:
        return (Core.getfield)(q, :x)::Int64
    end))=>Int64

0.7

julia> @code_typed f(1)
CodeInfo(
3 1 ─ %1 = (Base.add_int)(x, 1)::Int64          │╻ +
  └──      goto #3 if not false                 │
  2 ─      nothing::Nothing                     │
4 3 ─      return %1                            │
) => Int64

Can see that the new call creating the mutable type is elided.

7 Likes

Thanks.

One more question. If I have a vector of mutable structs such as this one (which only contain isbits fields), the vector will be a pointer to a list of pointers to the structs, or a single pointer to a single chunk of memory with all the structs?

They will not lie contiguously in memory.

Is there a way to force a contiguous block? Like for instance perhaps casting the Vector to a Tuple might be a good idea in this case?

Don’t use mutable

Just to elaborate on this a bit: if you want a contiguous array of structs, then they need to be immutable. But suppose you want to change a field in one of those structs? The Julian way to do it is to copy the whole struct over and then count on compiler optimizations to elide needless work. For example, here is a function (not tested) that changes one field of a struct that lives inside of an array:

    struct A
        a::Int
        b::Bool
    end

    function changeb!(v::Vector{A}, ind, newb::Bool)
        v[ind] = A(v[ind].a, newb)
        nothing
    end

For a struct that has many fields, this can get awkward. I wrote a macro a long time ago to automatically generate the above kind of code, but I haven’t used it recently, and I’m not sure it works any more. I suspect someone else may have a package for this purpose.

1 Like

Can they lie contiguously in memory when all attributes of the mutable struct are fixed length eg bits type?

https://github.com/simonster/StructsOfArrays.jl

A little bit off-topic: this might be useful if you want every field in the immutable struct stored contiguously in memory.

2 Likes

The issue of mutable/immutable structs is orthogonal to the issue of whether its fields are bits/nonbits. In other words, a particular mutable struct may have only bits objects, but it is still mutable (one can change the fields individually). Similarly, an immutable struct may have nonbits entries, but it is still immutable (one cannot change the fields individually). In terms of the memory layout, for both mutable and immutable, a nonbits field is stored via a pointer inside the struct, whereas a bits field is stored directly. (Note: the compiler is allowed to emit code that implements these properties differently for the purpose of improving performance as long as the results are indistinguishable from this description.)

For an array of structs, as Kristoffer Carlsson said, there is contiguous memory layout only for immutable structs. And if those immutable structs contain nonbits fields, then each struct object in the array internally will have pointers, so the data in the array may still be scattered.

1 Like

Note that Julia isbits returns false for a mutable struct, even if all the fields are isbits. I agree with the distinction of mutable/immutable vs. bits/nonbits… but then why isbits behaves like this?

This explains it quite well I think:

help?> isbits
search: isbits isbitstype disable_sigint

  isbits(x)

  Return true if x is an instance of an isbitstype type.

help?> isbitstype
search: isbitstype

  isbitstype(T)

  Return true if type T is a "plain data" type, meaning it is immutable and contains no references to other values,
  only primitive types and other isbitstype types. Typical examples are numeric types such as UInt8, Float64, and
  Complex{Float64}. This category of types is significant since they are valid as type parameters, may not track
  isdefined / isassigned status, and have a defined layout that is compatible with C.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> isbitstype(Complex{Float64})
  true

  julia> isbitstype(Complex)
  false
2 Likes

Setfeild.jl does this.

I’m still a bit confused about why mutable structs, even if all its fields are isbits, might require heap allocation. If a variable is defined in a function scope, and not returned, it can be safely deleted after the function scope exits. Then what’s wrong with stack allocating it (whether it is of mutable or immutable type, but with all fields of isbits type so it has a compile-time defined size), as long as its inside a function? Is there a simple example where this does not work?

Eliding allocations when a non isbits struct is created and known not to escape is an optimization that is already happening.

But the discussion above was about how they will be stored in an Array?