ImmutableArrays #42465

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

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 invoked again after inlining to be used for various local optimizations.

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 (JuliaLang#43888), array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#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 JuliaLang#43888, JuliaLang#43909 and JuliaLang#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 invoked again after inlining to be used for various local optimizations.

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 invoked again after inlining to be used for various local optimizations.

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 by 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 to Julia Base by this commit, and then merge the depending PRs built on top of this commit later. This commit simply defines EA inside Julia base compiler and enables the existing test suite with it. In this commit we don't run EA at all, and so this commit shouldn't affect Julia-level compilation latency. In the depending PRs, EA will run in two stages: - `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache - `Local EA`: run EA on post-inlining state to generate local escape information used for various optimizations In order to integrate `IPO EA` with our compilation cache system, this commit also implements a new `CodeInstance.argescapes` field that keeps the IPO-valid cache generated by `IPO EA`.

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 (JuliaLang#43888), array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#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 by 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 to Julia Base by this commit, and then merge the depending PRs built on top of this commit later. This commit simply defines EA inside Julia base compiler and enables the existing test suite with it. In this commit we don't run EA at all, and so this commit shouldn't affect Julia-level compilation latency. In the depending PRs, EA will run in two stages: - `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache - `Local EA`: run EA on post-inlining state to generate local escape information used for various optimizations In order to integrate `IPO EA` with our compilation cache system, this commit also implements a new `CodeInstance.argescapes` field that keeps the IPO-valid cache generated by `IPO EA`.

…ang#43565) This would be useful for Julia-level optimizations on arrays. Initially I want to have this in order to add array primitives support in EscapeAnalysis.jl, which should help us implement a variety of array optimizations including dead array allocation elimination, copy-elision from `Array` to `ImmutableArray` conversion (JuliaLang#42465), etc., but I found this might be already useful for us since this enables some DCE in very simple cases like: ```julia julia> function simple!(x::T) where T d = IdDict{T,T}() # dead alloc # ... computations that don't use `d` at all return nothing end simple! (generic function with 1 method) julia> @code_typed simple!("foo") CodeInfo( 1 ─ return Main.nothing ) => Nothing ``` This enhancement is super limited though, e.g. DCE won't happen when array allocation involves other primitive operations like `arrayset`: ```julia julia> code_typed() do a = Int[0,1,2] nothing end 1-element Vector{Any}: CodeInfo( 1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Int64}, svec(Any, Int64), 0, :(:ccall), Vector{Int64}, 3, 3))::Vector{Int64} │ Base.arrayset(false, %1, 0, 1)::Vector{Int64} │ Base.arrayset(false, %1, 1, 2)::Vector{Int64} │ Base.arrayset(false, %1, 2, 3)::Vector{Int64} └── return Main.nothing ) => Nothing ``` Further enhancement o optimize cases like above will be based on top of incoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.

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 (JuliaLang#43888), array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#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 by 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 to Julia Base by this commit, and then merge the depending PRs built on top of this commit later. This commit simply defines EA inside Julia base compiler and enables the existing test suite with it. In this commit we don't run EA at all, and so this commit shouldn't affect Julia-level compilation latency. In the depending PRs, EA will run in two stages: - `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache - `Local EA`: run EA on post-inlining state to generate local escape information used for various optimizations In order to integrate `IPO EA` with our compilation cache system, this commit also implements a new `CodeInstance.argescapes` field that keeps the IPO-valid cache generated by `IPO EA`.

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

Superseded by #44381

…ang#43565) This would be useful for Julia-level optimizations on arrays. Initially I want to have this in order to add array primitives support in EscapeAnalysis.jl, which should help us implement a variety of array optimizations including dead array allocation elimination, copy-elision from `Array` to `ImmutableArray` conversion (JuliaLang#42465), etc., but I found this might be already useful for us since this enables some DCE in very simple cases like: ```julia julia> function simple!(x::T) where T d = IdDict{T,T}() # dead alloc # ... computations that don't use `d` at all return nothing end simple! (generic function with 1 method) julia> @code_typed simple!("foo") CodeInfo( 1 ─ return Main.nothing ) => Nothing ``` This enhancement is super limited though, e.g. DCE won't happen when array allocation involves other primitive operations like `arrayset`: ```julia julia> code_typed() do a = Int[0,1,2] nothing end 1-element Vector{Any}: CodeInfo( 1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Int64}, svec(Any, Int64), 0, :(:ccall), Vector{Int64}, 3, 3))::Vector{Int64} │ Base.arrayset(false, %1, 0, 1)::Vector{Int64} │ Base.arrayset(false, %1, 1, 2)::Vector{Int64} │ Base.arrayset(false, %1, 2, 3)::Vector{Int64} └── return Main.nothing ) => Nothing ``` Further enhancement o optimize cases like above will be based on top of incoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.

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 (JuliaLang#43888), array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#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 by 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 to Julia Base by this commit, and then merge the depending PRs built on top of this commit later. This commit simply defines EA inside Julia base compiler and enables the existing test suite with it. In this commit we don't run EA at all, and so this commit shouldn't affect Julia-level compilation latency. In the depending PRs, EA will run in two stages: - `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache - `Local EA`: run EA on post-inlining state to generate local escape information used for various optimizations In order to integrate `IPO EA` with our compilation cache system, this commit also implements a new `CodeInstance.argescapes` field that keeps the IPO-valid cache generated by `IPO EA`.

simeonschaub reviewed Oct 2, 2021

View reviewed changes