ImmutableArrays by ianatol · Pull Request #42465 · JuliaLang/julia

ianatol · 2021-10-02T00:13:23Z

This PR extends #41777 to provide a dynamically sized immutable array ImmutableArray.

The ImmutableArray constructor creates an immutable copy of another array, allowing users to get the performance of a mutable array locally, but with the compositionality and safety of an immutable array at the inter-procedural level. In the cases where the compiler can prove (using info from a novel escape analysis pass) that the original array is dead after copying, this benefit comes at no cost to the user.

See the following for an example of a function that utilizes performant, mutating operations while only exposing an immutable array:

function simple()
    a = Vector{Float64}(undef, 5)
    for i = 1:5
        a[i] = i
    end
    return ImmutableArray(a)
end

Using information gathered by the escape analysis pass, the compiler can prove that a is dead after the return, and thus this function is neatly optimized to have the same memory allocation as one that returns a mutable object.

This rebases JuliaLang#31630 with several fixed and modifications. After JuliaLang#31630, we had originally decided to hold off on said PR in favor of implementing either more efficient layouts for tuples or some sort of variable-sized struct type. However, in the two years since, neither of those have happened (I had a go at improving tuples and made some progress, but there is much still to be done there). In the meantime, all across the package ecosystem, we've seen an increasing creep of pre-allocation and mutating operations, primarily caused by our lack of sufficiently powerful immutable array abstractions and array optimizations. This works fine for the individual packages in question, but it causes a fair bit of trouble when trying to compose these packages with transformation passes such as AD or domain specific optimizations, since many of those passes do not play well with mutation. More generally, we would like to avoid people needing to pierce abstractions for performance reasons. Given these developments, I think it's getting quite important that we start to seriously look at arrays and try to provide performant and well-optimized arrays in the language. More importantly, I think this is somewhat independent from the actual implementation details. To be sure, it would be nice to move more of the array implementation into Julia by making use of one of the abovementioned langugage features, but that is a bit of an orthogonal concern and not absolutely required. This PR provides an `ImmutableArray` type that is identical in functionality and implementation to `Array`, except that it is immutable. Two new intrinsics `Core.arrayfreeze` and `Core.arraythaw` are provided which are semantically copies and turn a mutable array into an immutable array and vice versa. In the original PR, I additionally provided generic functions `freeze` and `thaw` that would simply forward to these intrinsics. However, said generic functions have been omitted from this PR in favor of simply using constructors to go between mutable and immutable arrays at the high level. Generic `freeze`/`thaw` functions can always be added later, once we have a more complete picture of how these functions would work on non-Array datatypes. Some basic compiler support is provided to elide these copies when the compiler can prove that the original object is dead after the copy. For instance, in the following example: ``` function simple() a = Vector{Float64}(undef, 5) for i = 1:5 a[i] = i end ImmutableArray(a) end ``` the compiler will recognize that the array `a` is dead after its use in `ImmutableArray` and the optimized implementation will simply rewrite the type tag in the originally allocated array to now mark it as immutable. It should be pointed out however, that *semantically* there is still no mutation of the original array, this is simply an optimization. At the moment this compiler transform is rather limited, since the analysis requires escape information in order to compute whether or not the copy may be elided. However, more complete escape analysis is being worked on at the moment, so hopefully this analysis should become more powerful in the very near future. I would like to get this cleaned up and merged resonably quickly, and then crowdsource some improvements to the Array APIs more generally. There are still a number of APIs that are quite bound to the notion of mutable `Array`s. StaticArrays and other packages have been inventing conventions for how to generalize those, but we should form a view in Base what those APIs should look like and harmonize them. Having the `ImmutableArray` in Base should help with that.

simeonschaub · 2021-10-02T00:25:10Z

base/broadcast.jl

+    # Now handle the remaining values
+    # The typeassert gives inference a helping hand on the element type and dimensionality
+    # (work-around for #28382)
+    ElType′ = ElType === Union{} ? Any : ElType <: Type ? Type : ElType
+    RT = dest isa AbstractArray ? AbstractArray{<:ElType′, ndims(dest)} : Any


Not directly related to this PR, but might be a good opportunity to check whether this still holds true with the recent inference improvements.

src/builtins.c

base/abstractarray.jl

base/array.jl

base/broadcast.jl

base/compiler/ssair/passes.jl

…ry_opt!

base/array.jl

base/compiler/ssair/passes.jl

…to Core

This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base. You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1]. [^1]: The same documentation will be included into Julia's developer documentation by this commit. This escape analysis will hopefully be an enabling technology for various memory-related optimizations at Julia's high level compilation pipeline. Possible target optimization includes mutable ϕ-node aware SROA, `mutating_arrayfreeze` optimization (#42465), stack allocation of mutables, dead array elimination, finalizer elision and so on[^2]. [^2]: It would be also interesting if LLVM-level optimizations can consume some IPO information derived by this escape analysis to broaden optimization possibilities. The primary motivation for porting EA in this PR is to check its impact on latency as well as to get feedbacks from a broader range of developers. If there are no serious problems, EA will be used by #42465 for `mutating_arrayfreeze` optimization for `ImmutableArray` construction. This commit simply defines EA inside Julia base compiler and enables the existing test suite with it. The plan is to validate EA's accuracy and correctness and to check the latency impact by running EA before the existing SROA pass and checking if it can detect all objects eliminated by the SROA pass as "SROA-eliminatable".

ianatol · 2022-01-28T00:02:23Z

Setting this as a draft until #43800 is merged, since this relies on that and for now just has an outdated version to work internally.

This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base. You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1]. [^1]: The same documentation will be included into Julia's developer documentation by this commit. This escape analysis will hopefully be an enabling technology for various memory-related optimizations at Julia's high level compilation pipeline. Possible target optimization includes mutable ϕ-node aware SROA, `mutating_arrayfreeze` optimization (#42465), stack allocation of mutables, dead array elimination, finalizer elision and so on[^2]. [^2]: It would be also interesting if LLVM-level optimizations can consume some IPO information derived by this escape analysis to broaden optimization possibilities. The primary motivation for porting EA in this PR is to check its impact on latency as well as to get feedbacks from a broader range of developers. If there are no serious problems, EA will be used by #42465 for `mutating_arrayfreeze` optimization for `ImmutableArray` construction. This commit simply defines EA inside Julia base compiler and enables the existing test suite with it. The plan is to validate EA's accuracy and correctness and to check the latency impact by running EA before the existing SROA pass and checking if it can detect all objects eliminated by the SROA pass as "SROA-eliminatable".

This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base. You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1]. [^1]: The same documentation will be included into Julia's developer documentation by this commit. This escape analysis will hopefully be an enabling technology for various memory-related optimizations at Julia's high level compilation pipeline. Possible target optimization includes alias aware SROA (#43888), array SROA (#43909), `mutating_arrayfreeze` optimization (#42465), stack allocation of mutables, finalizer elision and so on[^2]. [^2]: It would be also interesting if LLVM-level optimizations can consume IPO information derived by this escape analysis to broaden optimization possibilities. The primary motivation for porting EA in this PR is to check its impact on latency as well as to get feedbacks from a broader range of developers. The plan is that we first introduce EA in this commit, and then merge the depending PRs built on top of this commit like #43888, #43909 and #42465 This commit simply defines and runs EA inside Julia base compiler and enables the existing test suite with it. In this commit, we just run EA before inlining to generate IPO cache. The depending PRs, EA will be reran after inlining to be used for various local optimizations.

ianatol · 2022-02-28T20:11:15Z

Superseded by #44381

simeonschaub reviewed Oct 2, 2021

View reviewed changes