Should we have freeze and thaw

[Tokazama]

I've seen freeze(x) and thaw(x) thrown around for making x immutable and mutable, respectively. I'm not sure if we should wait for base to formalize the ImmutableArray approach, or if it's worth have some common syntax for that right now. I'm not sure if we're ever going to get much petter than this pattern:

function foo(x)
    y = similar(x)
    foo!(y, x)
    if ismutable(x)
        return y
    else
        return freeze(y)
    end
end
# change values of `y`
foo!(y, x) = ...

Which might be fine if we can ensure that freeze(y) and similar(x) are close so that the compiler can easily figure out what to allocate to the stack and elide unnecessary allocations.

[ChrisRackauckas]

I'm not sure it should go here. I'm not sure those will be general terms applied to any array, or what exactly the side effects will be. This should be "wait and see" for now.

[chriselrod]

FWIW, my experimentation didn't show llvm actually use invariant information to optimize in the cases I wanted it to/thought it should.

Although there is still a lot of higher level value, e.g.
a) AD
b) Can be useful for organizing code, e.g. if you rely on a ton of mutating functions, it can help with organization to freeze those arrays you're relying on not being mutated.

[Tokazama]

I'm not sold on the terms at all but it's what I've seen used in several places. If we clearly need that functionality now and in the future it might be worth further discussion. I'm thinking of a very limited implementation of we did it, that would have a simplistic fall back. If the default method required anything involved it probably isn't a good fit.

Most of the other people working on this sort of thing seem to be doing deep compiler stuff just for ImmutableArray. It would be nice to have a more generic approach so we could do this with other types of collects. I figured Chris elrod would be the person that had the most knowledge and interest concerning how this could be implemented appropriately outside of base.

[AriMKatz]

There's also @tkf 's https://github.com/tkf/Mutabilities.jl which is very general.

If you really want to do controlled mutability (and other effects) correctly, then you can't do better (IMO) than using algebraic effect handlers. I don't know if that requires static semantics, given that we already have effect tracking and there are some algebraic effects packages in Julia below.

Armed with that structure, users could control the interactions between effects and control flow. The compiler could then reliably know which loops are legal to parallelize and fuse (inline + beta reduction). Then if functions are written in terms of those loops, you'd get kernel fusion for free in many cases, without a whole bunch of fusion rules.

https://arxiv.org/abs/2110.07493#:~:text=Algebraic%20effects%20and%20handlers%20support,effects%20to%20be%20executed%20sequentially.

^ that's a more extensible version of what dex currently does, and it's part of the work they're planning to incorporate into the language.

Some packages in julia (though don't have the parallel semantics of the above paper):

https://github.com/MikeInnes/Effects.jl
https://github.com/JuliaFunctional/ExtensibleEffects.jl

and a Juliacon talk: https://www.youtube.com/watch?v=pj7-rNyz3J8

Could also make life easier for AD and other compiler passes

[Tokazama]

Thanks @AriMKatz. If defining a generic version of freeze required explicit knowledge of a more complicated system of effects, then I think this might be the wrong place.

[AriMKatz]

I don't think that it does (though not sure). I think freeze and thaw are "cheaper" ways to get a subset of what a full effect handling system would provide.

Ideally we'd have an array IR, effect system and some way of reliably propagating array shapes and metadata. That would be the best way to solve array performance (biased for the DL use case), while keeping code generic and amenable to AD. Maybe that's too invasive or expensive, but could be a good long term vision.

In the meantime it probably makes sense to have simpler verbs to handle generic immutable objects.

[Tokazama]

I guess my question really comes down to this: Given the the following code can we guarantee that MVector{N,eltype(x}}() and freeze(out) don't end up with two separate allocations.

foo(op, x) = _foo(ArrayInterface.static_length(x), op, x)
function _foo(::StaticInt{N}, op, x)
    out = MVector{N,eltype(x}}()
    for i in 1:N
        out[i] = op(x[i])
    end
    as_immutable(out)
end

We get around this right now by manually unrolling the loop but requiring this code be explicitly different is problematic and requires knowledge of types within StaticArrays. The following pattern is more generic and maintainable in the long run.

function_foo(op, x)
    N = ArrayInterface.static_length(x)
    out = alloc(eltype(x}, N)
    for i in 1:N
        out[i] = op(x[i])
    end
    if ArrayInterface.can_setindex(x)
        return out
    else
        return as_immutable(out)
    end
end

Things like loop unrolling and shape propagation can probably be handled separately, but if we can't overcome initial allocations for the mutable collection when we return the immutable one, then I worry about how useful this will be. I mean, we could say that it allows generic support for StaticArrays in code but if it doubles our allocations then it negates the utility of StaticArrays.

[AriMKatz]

I think this is more a question for folks working on escape analysis like @ianatol and @aviatesk