Performance regression for Union types in 1.7.0-rc1 #42754

goerch · 2021-10-22T08:17:31Z

The following program

mutable struct Node{K,D}
    parent::Union{Node{K,D},Nothing}
    left::Union{Node{K,D},Nothing}
    right::Union{Node{K,D},Nothing}
    key::K
    bf::Int8
    data::D
end

mutable struct AVLTree{K,D}
    root::Union{Node{K,D},Nothing}
end

@inline function rotate_left(t::AVLTree{K,D}, x::Node{K,D}, x_right::Node{K,D}) where {K,D}
    y = x_right

    if y.left !== nothing
        x.right = y.left
        y.left.parent = x
    else
        x.right = nothing
    end
    y.left = x

    xp = x.parent
    if xp === nothing
        t.root = y
    else
        if xp.left == x
            xp.left = y
        else
            xp.right = y
        end
    end

    y.parent = xp
    x.parent = y

    x.bf -= y.bf * (y.bf >= zero(Int8)) + one(Int8)
    y.bf += x.bf * (x.bf < zero(Int8)) - one(Int8)

    return y
end

t = AVLTree{Int, Nothing}(nothing)
x = Node{Int, Nothing}(nothing, nothing, nothing, 1, 0, nothing)
using BenchmarkTools
@btime rotate_left($t, $x, $x)

produces on Julia Version 1.6.3:

julia> @btime rotate_left($t, $x, $x)
  7.101 ns (0 allocations: 0 bytes)

and on 1.7.0-rc1:

julia> @btime rotate_left($t, $x, $x)
  638.982 ns (0 allocations: 0 bytes)

Related discussion: https://discourse.julialang.org/t/dynamic-dispatch-with-union-nothing/70174/3

KristofferC · 2021-10-22T08:21:36Z

Thanks for the info, I did a short update of the text to condense it a bit and make it explicit how to check the performance regression.

Looking at @code_warntype it seems that some calls that used to be inlined are no longer so:

- 3 ──       Base.setfield!(x, :right, nothing)
+ %6  = Base.setproperty!::typeof(setproperty!)
+ │    %7  = (isa)(%5, Nothing)::Bool
+ └───       goto #4 if not %7
+ 3 ── %9  = π (%5, Nothing)
+ │          invoke %6(_3::Node{Int64, Nothing}, :right::Symbol, %9::Nothing)

I will try bisect it.

KristofferC · 2021-10-22T09:31:44Z

Bisected to #39754, cc @Keno

aviatesk · 2021-10-22T09:38:17Z

Seems like non-inlined setproperty!s are union-split. So I guess what we need here is basically a way to use constant-prop'ed sources at union-split callsite (ref: #39305 (comment))
So in other word, we need to resolve this TODO (IIUC):

julia/base/compiler/ssair/inlining.jl

Lines 1226 to 1230 in 609a4a0

    
           # when multiple matches are found, bail out and later inliner will union-split this signature 
        
           # TODO effectively use multiple constant analysis results here 
        
           length(info.results) == 1 || return false 
        
           result = info.results[1] 
        
           isa(result, InferenceResult) || return false

```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximate inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ```

This commit complements #39754 and #39305: implements a logic to use constant-prop'ed results for inlining at union-split callsite. Currently it works only for cases when constant-prop' succeeded for all (union-split) signatures. > example ```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximated inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first ``` > before this commit ```julia 1 ─ %1 = Base.setproperty!::typeof(setproperty!) │ %2 = (isa)(a, Nothing)::Bool └── goto #3 if not %2 2 ─ %4 = π (a, Nothing) │ invoke %1(_2::X, 🅰️:Symbol, %4::Nothing)::Any └── goto #6 3 ─ %7 = (isa)(a, Int64)::Bool └── goto #5 if not %7 4 ─ %9 = π (a, Int64) │ invoke %1(_2::X, 🅰️:Symbol, %9::Int64)::Any └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` > after this commit ```julia CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ```

This commit complements #39754 and #39305: implements a logic to use constant-prop'ed results for inlining at union-split callsite. Currently it works only for cases when constant-prop' succeeded for all (union-split) signatures. > example ```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximated inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first ``` > before this commit ```julia CodeInfo( 1 ─ %1 = Base.setproperty!::typeof(setproperty!) │ %2 = (isa)(a, Nothing)::Bool └── goto #3 if not %2 2 ─ %4 = π (a, Nothing) │ invoke %1(_2::X, 🅰️:Symbol, %4::Nothing)::Any └── goto #6 3 ─ %7 = (isa)(a, Int64)::Bool └── goto #5 if not %7 4 ─ %9 = π (a, Int64) │ invoke %1(_2::X, 🅰️:Symbol, %9::Int64)::Any └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` > after this commit ```julia CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ```

…st-prop'ed sources This commit complements #39754 and #39305: implements a logic to use constant-prop'ed results for inlining at union-split callsite. Currently it works only for cases when constant-prop' succeeded for all (union-split) signatures. > example ```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximated inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first ``` > before this commit ```julia CodeInfo( 1 ─ %1 = Base.setproperty!::typeof(setproperty!) │ %2 = (isa)(a, Nothing)::Bool └── goto #3 if not %2 2 ─ %4 = π (a, Nothing) │ invoke %1(_2::X, 🅰️:Symbol, %4::Nothing)::Any └── goto #6 3 ─ %7 = (isa)(a, Int64)::Bool └── goto #5 if not %7 4 ─ %9 = π (a, Int64) │ invoke %1(_2::X, 🅰️:Symbol, %9::Int64)::Any └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` > after this commit ```julia CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ```

optimizer: fix #42754, inline union-split const-prop'ed sources

…st-prop'ed sources This commit complements #39754 and #39305: implements a logic to use constant-prop'ed results for inlining at union-split callsite. Currently it works only for cases when constant-prop' succeeded for all (union-split) signatures. > example ```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximated inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first ``` > before this commit ```julia CodeInfo( 1 ─ %1 = Base.setproperty!::typeof(setproperty!) │ %2 = (isa)(a, Nothing)::Bool └── goto #3 if not %2 2 ─ %4 = π (a, Nothing) │ invoke %1(_2::X, 🅰️:Symbol, %4::Nothing)::Any └── goto #6 3 ─ %7 = (isa)(a, Int64)::Bool └── goto #5 if not %7 4 ─ %9 = π (a, Int64) │ invoke %1(_2::X, 🅰️:Symbol, %9::Int64)::Any └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` > after this commit ```julia CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ```

aviatesk · 2021-10-26T15:02:18Z

Here is the performance on #42805 (the backport branch):

julia> @code_typed rotate_left(t, x, x)
CodeInfo(
1 ── %1  = Base.getfield(x_right, :left)::Union{Nothing, Node{Int64, Nothing}}
│    %2  = (%1 === Main.nothing)::Bool
│    %3  = Core.Intrinsics.not_int(%2)::Bool
└───       goto #13 if not %3
2 ── %5  = Base.getfield(x_right, :left)::Union{Nothing, Node{Int64, Nothing}}
│    %6  = (isa)(%5, Nothing)::Bool
└───       goto #4 if not %6
3 ──       Base.setfield!(x, :right, nothing)::Nothing
└───       goto #7
4 ── %10 = (isa)(%5, Node{Int64, Nothing})::Bool
└───       goto #6 if not %10
5 ── %12 = π (%5, Node{Int64, Nothing})
│          Base.setfield!(x, :right, %12)::Node{Int64, Nothing}
└───       goto #7
6 ──       Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{}
└───       unreachable
7 ┄─ %17 = Base.getfield(x_right, :left)::Union{Nothing, Node{Int64, Nothing}}
│    %18 = Base.setproperty!::typeof(setproperty!)
│    %19 = (isa)(%17, Nothing)::Bool
└───       goto #9 if not %19
8 ── %21 = π (%17, Nothing)
│          invoke %18(%21::Nothing, :parent::Symbol, _3::Node{Int64, Nothing})::Any
└───       goto #12
9 ── %24 = (isa)(%17, Node{Int64, Nothing})::Bool
└───       goto #11 if not %24
10 ─ %26 = π (%17, Node{Int64, Nothing})
│          Base.setfield!(%26, :parent, x)::Node{Int64, Nothing}
└───       goto #12
11 ─       Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{}
└───       unreachable
12 ┄       goto #14
13 ─       Base.setfield!(x, :right, nothing)::Nothing
14 ┄       Base.setfield!(x_right, :left, x)::Node{Int64, Nothing}
│    %34 = Base.getfield(x, :parent)::Union{Nothing, Node{Int64, Nothing}}
│    %35 = (%34 === Main.nothing)::Bool
└───       goto #16 if not %35
15 ─       Base.setfield!(t, :root, x_right)::Node{Int64, Nothing}
└───       goto #24
16 ─ %39 = π (%34, Node{Int64, Nothing})
│    %40 = Base.getfield(%39, :left)::Union{Nothing, Node{Int64, Nothing}}
│    %41 = (isa)(%40, Nothing)::Bool
└───       goto #18 if not %41
17 ─       goto #21
18 ─ %44 = (isa)(%40, Node{Int64, Nothing})::Bool
└───       goto #20 if not %44
19 ─ %46 = π (%40, Node{Int64, Nothing})
│    %47 = (%46 === x)::Bool
└───       goto #21
20 ─       Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{}
└───       unreachable
21 ┄ %51 = φ (#17 => false, #19 => %47)::Bool
└───       goto #23 if not %51
22 ─ %53 = π (%34, Node{Int64, Nothing})
│          Base.setfield!(%53, :left, x_right)::Node{Int64, Nothing}
└───       goto #24
23 ─ %56 = π (%34, Node{Int64, Nothing})
└───       Base.setfield!(%56, :right, x_right)::Node{Int64, Nothing}
24 ┄ %58 = (isa)(%34, Nothing)::Bool
└───       goto #26 if not %58
25 ─       Base.setfield!(x_right, :parent, nothing)::Nothing
└───       goto #29
26 ─ %62 = (isa)(%34, Node{Int64, Nothing})::Bool
└───       goto #28 if not %62
27 ─ %64 = π (%34, Node{Int64, Nothing})
│          Base.setfield!(x_right, :parent, %64)::Node{Int64, Nothing}
└───       goto #29
28 ─       Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{}
└───       unreachable
29 ┄       Base.setfield!(x, :parent, x_right)::Node{Int64, Nothing}
│    %70 = Base.getfield(x, :bf)::Int8
│    %71 = Base.getfield(x_right, :bf)::Int8
│    %72 = Base.getfield(x_right, :bf)::Int8
│    %73 = Base.sle_int(0, %72)::Bool
│    %74 = Core.bitcast(Core.Int8, %73)::Int8
│    %75 = Core.and_int(%74, 1)::Int8
│    %76 = Base.mul_int(%71, %75)::Int8
│    %77 = Base.add_int(%76, 1)::Int8
│    %78 = Base.sub_int(%70, %77)::Int8
│          Base.setfield!(x, :bf, %78)::Int8
│    %80 = Base.getfield(x_right, :bf)::Int8
│    %81 = Base.getfield(x, :bf)::Int8
│    %82 = Base.getfield(x, :bf)::Int8
│    %83 = Base.slt_int(%82, 0)::Bool
│    %84 = Core.bitcast(Core.Int8, %83)::Int8
│    %85 = Core.and_int(%84, 1)::Int8
│    %86 = Base.mul_int(%81, %85)::Int8
│    %87 = Base.sub_int(%86, 1)::Int8
│    %88 = Base.add_int(%80, %87)::Int8
│          Base.setfield!(x_right, :bf, %88)::Int8
└───       return x_right
) => Node{Int64, Nothing}

julia> @benchmark rotate_left($t, $x, $x)
BenchmarkTools.Trial: 10000 samples with 999 evaluations.
 Range (min … max):  8.689 ns … 30.630 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     8.809 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   8.852 ns ±  0.431 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                  ▁ █                                         
  ▂▁▁▁▁▁▁▁▁▁▂▁▁▁▂▁█▃█▆▁▅▁▄▁▅▁▄▄▁▃▁▃▁▄▁▄▂▃▃▁▃▁▃▁▃▂▃▃▁▂▁▂▁▂▁▂▂ ▃
  8.69 ns        Histogram: frequency by time        9.01 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

commit c054dbc Author: Shuhei Kadowaki <40514306+aviatesk@users.noreply.github.com> Date: Fri Oct 29 01:31:55 2021 +0900 optimizer: eliminate allocations (JuliaLang#42833) commit 6a9737d Author: Jeff Bezanson <jeff.bezanson@gmail.com> Date: Thu Oct 28 12:23:53 2021 -0400 fix JuliaLang#42659, move `jl_coverage_visit_line` to runtime library (JuliaLang#42810) commit c762f10 Author: Marc Ittel <35898736+MarcMush@users.noreply.github.com> Date: Thu Oct 28 12:19:13 2021 +0200 change `julia` to `julia-repl` in docstrings (JuliaLang#42824) Co-authored-by: Michael Abbott <32575566+mcabbott@users.noreply.github.com> commit 9f52ec0 Author: Dilum Aluthge <dilum@aluthge.com> Date: Thu Oct 28 05:30:11 2021 -0400 CI (Buildkite): Update all rootfs images to the latest versions (JuliaLang#42802) * CI (Buildkite): Update all rootfs images to the latest versions * Re-sign all of the signed pipelines commit 404e584 Author: DilumAluthgeBot <43731525+DilumAluthgeBot@users.noreply.github.com> Date: Wed Oct 27 21:11:04 2021 -0400 🤖 Bump the Statistics stdlib from 74897fe to 5256d57 (JuliaLang#42826) Co-authored-by: Dilum Aluthge <dilum@aluthge.com> commit c74814e Author: Jeff Bezanson <jeff.bezanson@gmail.com> Date: Wed Oct 27 16:34:46 2021 -0400 reset `RandomDevice` file from `__init__` (JuliaLang#42537) This prevents us from seeing an invalid `IOStream` object from a saved system image, and also ensures the files are opened once for all threads. commit 05ed348 Author: Jeff Bezanson <jeff.bezanson@gmail.com> Date: Wed Oct 27 15:24:17 2021 -0400 only visit nonfunction_mt once when traversing method tables (JuliaLang#42821) commit d71b77d Author: DilumAluthgeBot <43731525+DilumAluthgeBot@users.noreply.github.com> Date: Tue Oct 26 20:39:08 2021 -0400 🤖 Bump the Downloads stdlib from 5f1509d to dbb0625 (JuliaLang#42811) Co-authored-by: Dilum Aluthge <dilum@aluthge.com> commit b4fddc1 Author: DilumAluthgeBot <43731525+DilumAluthgeBot@users.noreply.github.com> Date: Tue Oct 26 14:46:20 2021 -0400 🤖 Bump the Pkg stdlib from bc32103f to 26918395 (JuliaLang#42806) Co-authored-by: Dilum Aluthge <dilum@aluthge.com> commit 6a386de Author: Dilum Aluthge <dilum@aluthge.com> Date: Tue Oct 26 12:15:51 2021 -0400 CI (Buildkite): make sure to hit ignore any unencrypted repo keys, regardless of where they are located in the repository (JuliaLang#42803) commit 021a6b5 Author: Shuhei Kadowaki <40514306+aviatesk@users.noreply.github.com> Date: Wed Oct 27 01:08:33 2021 +0900 optimizer: clean up inlining test code (JuliaLang#42804) commit 16eb196 Merge: 21ebabf 1510eaa Author: Shuhei Kadowaki <40514306+aviatesk@users.noreply.github.com> Date: Tue Oct 26 23:25:41 2021 +0900 Merge pull request JuliaLang#42766 from JuliaLang/avi/42754 optimizer: fix JuliaLang#42754, inline union-split const-prop'ed sources commit 21ebabf Author: Kristoffer Carlsson <kcarlsson89@gmail.com> Date: Tue Oct 26 16:11:32 2021 +0200 simplify code loading test now that TOML files are parsed with a real TOML parser (JuliaLang#42328) commit 1510eaa Author: Shuhei Kadowaki <aviatesk@gmail.com> Date: Mon Oct 25 01:35:12 2021 +0900 optimizer: fix JuliaLang#42754, inline union-split const-prop'ed sources This commit complements JuliaLang#39754 and JuliaLang#39305: implements a logic to use constant-prop'ed results for inlining at union-split callsite. Currently it works only for cases when constant-prop' succeeded for all (union-split) signatures. > example ```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximated inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first ``` > before this commit ```julia CodeInfo( 1 ─ %1 = Base.setproperty!::typeof(setproperty!) │ %2 = (isa)(a, Nothing)::Bool └── goto #3 if not %2 2 ─ %4 = π (a, Nothing) │ invoke %1(_2::X, 🅰️:Symbol, %4::Nothing)::Any └── goto #6 3 ─ %7 = (isa)(a, Int64)::Bool └── goto #5 if not %7 4 ─ %9 = π (a, Int64) │ invoke %1(_2::X, 🅰️:Symbol, %9::Int64)::Any └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` > after this commit ```julia CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` commit 4c3ae20 Author: Chris Foster <chris42f@gmail.com> Date: Tue Oct 26 21:48:32 2021 +1000 Make Base.ifelse a generic function (JuliaLang#37343) Allow user code to directly extend `Base.ifelse` rather than needing a special package for it. commit 2e388e3 Author: Shuhei Kadowaki <aviatesk@gmail.com> Date: Mon Oct 25 01:30:09 2021 +0900 optimizer: eliminate excessive specialization in inlining code This commit includes several code quality improvements in inlining code: - eliminate excessive specializations around: * `item::Pair{Any, Any}` constructions * iterations on `Vector{Pair{Any, Any}}` - replace `Pair{Any, Any}` with new, more explicit data type `InliningCase` - remove dead code

This commit complements JuliaLang#39754 and JuliaLang#39305: implements a logic to use constant-prop'ed results for inlining at union-split callsite. Currently it works only for cases when constant-prop' succeeded for all (union-split) signatures. > example ```julia julia> mutable struct X # NOTE in order to confuse `fieldtype_tfunc`, we need to have at least two fields with different types a::Union{Nothing, Int} b::Symbol end; julia> code_typed((X, Union{Nothing,Int})) do x, a # this `setproperty` call would be union-split and constant-prop will happen for # each signature: inlining would fail if we don't use constant-prop'ed source # since the approximated inlining cost of `convert(fieldtype(X, sym), a)` would # end up very high if we don't propagate `sym::Const(:a)` x.a = a x end |> only |> first ``` > before this commit ```julia CodeInfo( 1 ─ %1 = Base.setproperty!::typeof(setproperty!) │ %2 = (isa)(a, Nothing)::Bool └── goto #3 if not %2 2 ─ %4 = π (a, Nothing) │ invoke %1(_2::X, 🅰️:Symbol, %4::Nothing)::Any └── goto #6 3 ─ %7 = (isa)(a, Int64)::Bool └── goto #5 if not %7 4 ─ %9 = π (a, Int64) │ invoke %1(_2::X, 🅰️:Symbol, %9::Int64)::Any └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ``` > after this commit ```julia CodeInfo( 1 ─ %1 = (isa)(a, Nothing)::Bool └── goto #3 if not %1 2 ─ Base.setfield!(x, :a, nothing)::Nothing └── goto #6 3 ─ %5 = (isa)(a, Int64)::Bool └── goto #5 if not %5 4 ─ %7 = π (a, Int64) │ Base.setfield!(x, :a, %7)::Int64 └── goto #6 5 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{} └── unreachable 6 ┄ return x ) ```

KristofferC added performance Must go faster regression Regression in behavior compared to a previous version labels Oct 22, 2021

aviatesk assigned Keno and aviatesk Oct 22, 2021

aviatesk added good first issue Indicates a good issue for first-time contributors to Julia compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) labels Oct 22, 2021

KristofferC removed the good first issue Indicates a good issue for first-time contributors to Julia label Oct 22, 2021

This was referenced Oct 22, 2021

Eliminating dynamic dispatch performance bottleneck krynju/AVLTrees.jl#19

Open

Performance regression from Julia 1.6.3 and 1.8.0-DEV krynju/AVLTrees.jl#18

Closed

aviatesk closed this as completed in 1510eaa Oct 26, 2021

aviatesk added a commit that referenced this issue Oct 26, 2021

Merge pull request #42766 from JuliaLang/avi/42754

16eb196

optimizer: fix #42754, inline union-split const-prop'ed sources

aviatesk mentioned this issue Oct 26, 2021

backport #42766 into backports-release-1.7 #42805

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Performance regression for Union types in 1.7.0-rc1 #42754

Performance regression for Union types in 1.7.0-rc1 #42754

goerch commented Oct 22, 2021 •

edited by KristofferC

Loading

KristofferC commented Oct 22, 2021 •

edited

Loading

KristofferC commented Oct 22, 2021

aviatesk commented Oct 22, 2021 •

edited

Loading

aviatesk commented Oct 26, 2021

Performance regression for Union types in 1.7.0-rc1 #42754

Performance regression for Union types in 1.7.0-rc1 #42754

Comments

goerch commented Oct 22, 2021 • edited by KristofferC Loading

KristofferC commented Oct 22, 2021 • edited Loading

KristofferC commented Oct 22, 2021

aviatesk commented Oct 22, 2021 • edited Loading

aviatesk commented Oct 26, 2021

goerch commented Oct 22, 2021 •

edited by KristofferC

Loading

KristofferC commented Oct 22, 2021 •

edited

Loading

aviatesk commented Oct 22, 2021 •

edited

Loading