making `.=` work for immutable types?

[stevengj]

One question that arose in our class yesterday was whether we can make .= usable in generic code that is supposed to work for both arrays and numbers, or arrays and immutable arrays like @andyferris's StaticArrays.jl.

Right now, x .= f.(y) turns into broadcast!(f, x, y), so there is no way the broadcast call can be made to work for immutables.

One option would be to turn x .= f.(y) into x = broadcast!(f, x, y). Then, if you have an immutable type, you could define a broadcast! method that just ignores the second argument and calls broadcast(f, y) and it would work. This is kind of an abuse of broadcast!, though, and requires that library authors implement methods for all immutable types that they want to use with .=. Also, I'm not sure if there are any problematic performance implications to the extra assignment in the mutable case?

Probably a better option would be to turn x .= f.(y) into

if isimmutable(x)
    x = broadcast(f, y)
else
    broadcast!(f, x, y)
end

and assume that the compiler can optimize out the isimmutable check if typeof(x) is known. This has the advantage that it will automatically work with every immutable type without requiring explicit definition of broadcast! methods. Is there any downside?

[stevengj]

isimmutable is probably not quite the right function here, since e.g. it returns true for view. May we could have a broadcast_isimmutable(x) = isimmutable(x) function that can be overloaded to false for types that support broadcast!.

[bramtayl]

Although this seems like it could work, if .= semantically means mutate in place, then this behavior would be unexpected?

[stevengj]

The semantics would be redefined to "mutate in-place if contents are mutable". I agree that this is a downside, but it's unfortunate not to be able to write generic code that is efficient for both Vector and SVector, for example

[andyferris]

Although this seems like it could work, if .= semantically means mutate in place, then this behavior would be unexpected?

The semantics of a := b (here, a .= b) that I was aiming for was: "replace a in-place with b".

It gets complicated with immutables with multiple bindings to the same value, but assuming that there is only one reference to a (we hadn't written c = a earlier) and inference has deduced an isbits type for a, then what would happen is the same stack space would often be overwritten with the new value (just as an immutable variable does within a loop). Thus for immutable types, I think what you want is a := b converted to a = convert(typeof(a), b) (the type of a is unchanged by the operation, otherwise we can't replace it in-place - it would be part of the semantic that a is a modified object of the same type).

For mutables (heap-allocated), the memory is mutated, not reallocated. The type of a also stays constant, as now.

For non-isbits immutables, we have to re-allocate because of the limitations of current compiler technology, but this would go away automatically once they are inlined. But the type can stay constant.

Fusing := with .op for broadcast makes heaps of sense, so .= might be a better choice of operator to make this clear, rather than introducing a new :=. But yes, we definitely would be changing slightly the meaning of .= if we did that.

broadcast_isimmutable(typeof(x)) could be a @pure function that people can extend in their own code, like a trait.

[StefanKarpinski]

I worry that people would write correct code for mutables this way and then apply them to immutables and get subtly different semantics, giving incorrect behavior. I still believe that a large part of the reason that generic code in Julia "just works" is that we've been really strict about semantics being completely uniform in the language (e.g. the classic "why can't x += y mutate x when x is mutable?" and "why can't we just have mutable value types?" debates). Would it be better to express this by wrapping an immutable in a Ref and passing it through the code that requires a mutable? Assuming, of course, that such an idiom could be made to be just as efficient as the purely immutable version.

[andyferris]

I'm ok with that, in fact that could be the most beautiful way to do it, but I'd need escape analysis or a "linear type" ref in order to have an immutable array remain stack allocated. (I'm not sure if linear/unique types could be a third option besides type and immutable and still follow the current binding semantics of Julia... but we could avoid a heck of a lot of GC doing that).

OTOH, the OP seemed like something that works now.

[ChrisRackauckas]

Would it be better to express this by wrapping an immutable in a Ref and passing it through the code that requires a mutable? Assuming, of course, that such an idiom could be made to be just as efficient as the purely immutable version.

I have looked into this solution a lot in JuliaDiffEq. The reason is that we also have to handle user-defined function, which is either du=f(t,u) or f!(t,u,du) (matches FORTRAN not Julia convention for mutating) depending on whether the problem is on mutables or immutables. If we could performantly use a Ref, then everything could be the second form (which also uses .= in the methods). Until then, we have to keep separate methods for mutables and immutables since putting everything in a Ref came out to be about 3x slower. If you have a way to speed up the use of Ref, then it's the holy grail here.

[JeffBezanson]

It's important to note an asymmetry here: immutable objects cannot provide mutating semantics, but mutable objects can be used in an immutable way, and reusing their space efficiently is "just" an optimization. It's clear that the long term goal should be to make it less necessary to use mutation just for performance. The main way I can see to do this is to automate tracking of whether you have the last reference to a value. For example, given

x = f(x, y)

where this is the only reference to x, the compiler could generate

release!(x)
temp = f(x, y)
reference!(temp)
x = temp

and f could check something like isshared(x) to see if it can overwrite it. This probably requires using a bit in the object header, but I feel it's worth it. This can be done conservatively --- in any case where we're not sure we can just keep the value marked as shared.

[andyferris]

Right, I've been thinking about this a lot lately.

We currently have type inference, and better type inference means less boxes (and better performance)

We could follow that by "reference inference" and if it can prove certain things about object lifetimes, this step would make certain transformations (perhaps like above) and could annotate to use unique references, non-mutating references, weak references, reference-counting, etc, for itself and for during the codegen phase (which would stack allocate mutables if the annotations indicate that is safe/performant, etc). When its not sure, the standard GC could be invoked like now. Implementing better "reference inference" would mean less GC usage and less (but not zero) heap allocation. If you wrote your code in a way such that every object lifetime could be inferred, object deletion could become fully deterministic for that code. (I believe you guys have thought of this under the name of "escape analysis", but I had only seen this discussed for the purpose of stack allocation of mutables).

Having extra bits in the header is a bit like reference-counting, which could be invoked when the "reference inference" step feels this would be more performant than tracing GC, but I think just inferring unique references at compile-time and making it deterministic at run-time would be a nicer first step (and more generalizable to a fully-fledged reference inference engine).

The cool thing is that we would more-or-less inherit some of the nice properties of Rust on an opt-in basis (similar to static typing is opt-in in Julia but dynamic by default/fallback; in this context tracing GC is the default/fallback).

[andyferris]

could check something like isshared(x) to see if it can overwrite it. This probably requires using a bit in the object header,

So I think of this as a bit like the proposed improvement to Union{A,B} which would have a bit-flag to say if the data is A or B. I.e. a "shared" bit-flag might be the case you invoke when you have proved there are either 1 or 2 references, or there is some loop with a branch/function call and you don't know if a second reference will be taken in a given iteration or not.

But there are big wins to be made in the fully-inferable cases (where you can prove there is exactly one reference/binding, for example), since you can skip tracing GC for these cases entirely, and I would argue to deal with them first. But maybe that is a lot of work compared to your suggestion...

[StefanKarpinski]

Having extra bits in the header is a bit like reference-counting

This is sometimes known as "approximate reference counting" where you distinguish only between "there are additional references" and "there are not additional references". You can also do things like support values 0, 1, 2, 3+ using two bits and the semantics are that if the refcount ever goes to 3 it doesn't come back – in which case the object gets GC'ed as normal.