Make immutable mutable again - or make arrays of structures stack-allocated

array
memory-allocation
data_structures

#1

This post is ispired by the following discussions about mutability and stack-allocated arrays: Initializing an array of mutable objects is surprisingly slow
Fortran vs Julia stack allocated arrays
Why mutable structs are allocated on the heap?
Mutate NTuple at position
Way to have a function "mutate an immutable" without much performance loss

And the actual issue is: WIP: Make mutating immutables easier

It seems to me that many people get confused with mutability, fixed-sized types and stack-allocation, but the point is, we can overwrite whole immutable objects, but not change their parts.

If so, maybe this issue can be resolved by adding another atomic type qualifier, along with mutable and immutable?

atomic struct Foo
    x::Int
    y::Int
end

The atomic treats every field change to be equivalent to the entire structure overwrite. But, knowing that the only one field is changed, it is optimized to only one field overwrite?

This has more consistent syntax with the other functions, since we do not need to have special write syntax, such as Setfield.jl or MArray at StaticArrays.jl, so the same functions can be used for immutables, mutables and atomic types, and we can explicitly define, for which types we want to be able to overwrite individual fields.


Generic functions between mutability
Memory layout of structs with mutable fields
#2

That is currently the definition of struct, so that’s currently in theory feasible to add without needing to change anything. The links are typically arguing for a breaking change to (weakening of) that memory model. A more thorough analysis of the approach you mention would be helpful (and eventually PRs to implement the necessary optimizations mentioned “optimized to only one field overwrite”) and the next step to drive those issues forward. It could even be a good GSOC project for someone.


#3

Making this a property of the type is an intriguing alternative. But it seems to introduce ambiguity into some syntactic constructs which are currently unambiguous:

atomic struct X
    a::Int
    b::Int
end

function foo(x)
    y = x
    # Now the following line is syntactically ambiguous 
    x.a = 10
    # Means one of the following?
    setfield!(x, :a, 10) # If `x` is a `mutable struct X`; mutates `y`
    x = X(10, x.b)       # If `x` is a `atomic struct X`; doesn't mutate `y`

    # The value of `y` depends on whether `X` is atomic or not.
    return y
end

foo(X(1,1))

#4

So to avoid this ambiguity, wouldn’t it be better to distinguish this special kind of “replace it all” update with actual syntax? Which is what I thought https://github.com/JuliaLang/julia/pull/21912 basically did.


#5

As I mentioned many time, syntax with this semantics is totally fine as long as,

  1. The syntax should make it clear it’s assigning to the variable, not the field, i.e. a = a@(b = 2) is fine, a@b = 2 or a.b = 2 are not.

  2. This must not be used for StaticArray or anything similar. That’s a regression.


#6

I’ve been wanting to use functions that “may mutate argument but returned value must be used”. For example, in this case I want (say) setfield!! which does setfield! for mutable struct and Setfield.set for struct. Similarly, I want to use setindex!! for writing algorithms that can be used for Array and StaticArray. Having push!! that can be used for both mutable and persistent data structure would also be great.


#7

I’ve been wanting to use functions that “ may mutate argument but returned value must be used”

Yes, this makes a lot of sense. I kind of like setindex!! but find it hard not to read as “mutate, the argument. No; really mutate it.” :slight_smile:

Did you try using MArray recently, by the way? This has really gotten a lot more efficient in julia 1.0 and I’m often surprised by how the compiler is able to avoid allocations completely even with MArray. It’s not a complete solution to the problems though.


#8

push?! appears like a fitting name.

Syntax-wise, compared to Keno’s original proposal, we could probably simplify: a.b.c[d][e].f @= rhs could mean: Take the rightmost mutable access; that element gets modified and replaced by a new immutable, where the appropriate parts to the right have been replaced by rhs and all other fields/indices are unchanged. If there is no mutable thing at all, then we replace a with a new object. If the compiler can prove that no other references exist to some immutable non-bitstype that gets replaced, then it can feel free to update the immutable in-place. In other words, there is no reason for the user to specify the point of mutation, like a.b.c@d.e = rhs: If we start copy-replacing at any position that is not right-most, then we play havoc with user expectations about what parts are shared after the update, and by refusing to define convenient replace-by-updated sytax for any mutable thing we also protect people from mistaken copies.

If at all possible, it would be very nice if the interplay between @ and dot-syntax resulted in a way of writing code for a @= b .+ c or maybe a @.= b.+c that uses the Base.GMP.MPZ in-place operations if a happens to be BigInt and just works for Int.


#9

Ok, so the actual question is, should it be the same syntax with ambiguous behaviour in some specific cases, or should it have different syntax with the need to rewrite every function on it.

Anyway, I will argue that it’s ambiguous. If you define atomic type, you expect it to work differently inside functions - you can treat that as some hidden function specialization. Another way is to treat it like a single number, not a complex atomic type.

So, the same function will break with immutable and have different behaviour on atomic and mutable types - these are 3 dirrefent behaviours. For me it’s clear that for atomic case you always have a deep copy, and a reference copy for mutable case.

Is that sufficient to resolve ambiguities?

By the way, I don’t sure if compiler is optimizing copies on immutable types to just referencing it wihout making the actual copy.

I can provide another example similar to 2: an array of immutable structures. In case of different syntax we should somehow specialize any function in the form:

function addone!(a) #specialize for mutables
    for i =1:length(a)        
        a[i].b += 1
    end
end

function addone!(a) #specialize for immutables
    for i =1:length(a)
        a[i]@(b += 1)
    end
end

This can become inconvenient for anyone who would work with contigious mutable arrays - and this is a pretty frequent case, especially in terms of performance! (see related threads above)

Another solution to have consistent syntax: maybe the compiler should determine if there are no ambiguities (copies of that struct) inside a function and just reinterpret a[i].b += 1 to a[i]@(b += 1), but in ambiguous cases it should return an error and ask to fix the syntax manually?


#10

Interesting! I don’t use MArray much so I didn’t know that. But to be honest I kind of like that Julia gives me an “excuse” to do functional programming when performance matters :slight_smile:


#11

If function_name?! is a valid syntax that would be awesome.


#12

It’s an error so could in principle be changed, right?

julia> fun?!(x) = x
ERROR: syntax: space required before "?" operator

julia> fun⁈(x) = x # unicode
ERROR: syntax: invalid character "⁈" near column 5

#13

I think so.