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

This post is ispired by the following discussions about mutability and stack-allocated arrays: Initializing an array of mutable objects is surprisingly slow - #6 by cnliao
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.

2 Likes

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.

2 Likes

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))

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 WIP: Make mutating immutables easier by Keno Ā· Pull Request #21912 Ā· JuliaLang/julia Ā· GitHub basically did.

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.

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.

2 Likes

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.

1 Like

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.

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?

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:

1 Like

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

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

I think so.