Inference regression on 1.7-RC2 and master (relative to 1.6.3) #42839

Sacha0 · 2021-10-28T21:45:22Z

@NHDaly (🙏) and I reduced the following out of a regression on Julia 1.7-RC2. Happily, on Julia 1.6.3:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.3 (2021-09-23)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
Variables
  #self#::Core.Const(cat_storage_type)
  #unused#::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})

Body::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Core.Const((Tuple{UInt8, UInt8, UInt8},))
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
└──      return %3

While on 1.7-RC2:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.0-rc2 (2021-10-20)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at REPL[1]:3
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Core.Const(cat_storage_type)
  _::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{<:Tuple}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Tuple{Type}
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Type{<:Tuple}
└──      return %3

And on several day old master:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.8.0-DEV.702 (2021-10-10)
 _/ |\__'_|_|_|\__'_|  |  master/82257229c9 (fork: 1 commits, 18 days)
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at REPL[1]:3
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Core.Const(cat_storage_type)
  _::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{<:Tuple}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Tuple{Type}
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Type{<:Tuple}
└──      return %3

The text was updated successfully, but these errors were encountered:

Sacha0 · 2021-10-28T22:42:47Z

Tested on fresh master (c054dbc) just now, persists.

Sacha0 · 2021-10-29T00:52:36Z

It might be worth noting that this (though naughty) works:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.0-rc2 (2021-10-20)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |

julia> begin
           cat_storage_type(::Type{T}) where T = T
           cat_storage_type(::Type{T}) where {T<:Tuple} = Tuple{_cat_storage_type_tuple(T)...}

           _cat_storage_type_tuple(::Type{Tuple{}}) = ()
           function _cat_storage_type_tuple(::Type{T}) where {T<:Tuple}
               Base.@_pure_meta
               return (
                   cat_storage_type(fieldtype(T, 1)),
                   _cat_storage_type_tuple(Base.tuple_type_tail(T))...,
               )
           end
       end
_cat_storage_type_tuple (generic function with 2 methods)

julia> @code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})
MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at REPL[1]:3
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Core.Const(cat_storage_type)
  _::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}}
1 ─ %1 = Core.tuple(Main.Tuple)::Core.Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Core.Const((Tuple{UInt8, UInt8, UInt8},))
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Core.Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
└──      return %3

vtjnash · 2021-10-29T03:09:36Z

It is perhaps worth noting that the internal tuple_type_tail function was deprecated and is not supported anymore (in favor of ntuple and fieldtype typically)

KristofferC · 2021-10-29T10:22:54Z

A bisect might be useful here.

Sacha0 · 2021-10-29T16:07:38Z

It is perhaps worth noting that the internal tuple_type_tail function was deprecated and is not supported anymore (in favor of ntuple and fieldtype typically)

Thanks for letting me know! I was aware of tuple_type_head's deprecation to fieldtype(T, 1), but not of tuple_type_tail's deprecation. On master tuple_type_tail seems to still live in tuple.jl without a deprecation warning; perhaps we should move it to deprecated.jl etc? :)

NHDaly · 2021-10-29T17:35:13Z

For the deprecation, do you mean we should replace it with something like this?:

julia> T = NTuple{8, Int8}; Tuple(fieldtype(T,i) for i in 2:fieldcount(T))
(Int8, Int8, Int8, Int8, Int8, Int8, Int8)

Or if that's not what you mean, can you expand on what we should replace it with? Thanks

EDIT: oh, whoops, also this isn't even computing the same thing, so ignore this.

vtjnash · 2021-10-29T17:46:07Z

Usually now we try to avoid forming the tuple of types, by using ntuple(...) on the values, or another existing call such as convert

Sacha0 · 2021-10-29T19:33:51Z

A bisect might be useful here.

Kicked one off 🍿, will report back.

Sacha0 · 2021-10-29T21:24:04Z

Bisect points to

commit c2ec70cd1842b53f45ac72ea74c94f008adbc7b3
Author: Jameson Nash <[email protected]>
Date:   Thu Apr 8 23:10:57 2021 -0400

    inference: limit single-level nested `Type` signature (#40379)

    Previously `type_more_complex` returns `false` for `Type{Type{...}}`
    compared against `Type{...}`. Per comment there, this should return `true`,
    but the code was ordered incorrect (it was also missing support for
    Vararg, after the recent changes).

    Fixes #40336

    Co-authored-by: Shuhei Kadowaki <[email protected]>

ChenNingCong · 2021-10-30T12:16:32Z

Cross ref: #42835 and my comment on 42835 issue at discourse

It seems this is also caused by type_more_complex function and Type. And if you change inference order, type inference succeeds. I test following code in Julia 1.8-DEV (in a fresh session), where type inference of cat_storage_type(Tuple{NTuple{3, UInt8}}) also fails.

@code_warntype cat_storage_type(Tuple{NTuple{1, UInt8}}) 
@code_warntype cat_storage_type(Tuple{NTuple{2, UInt8}})
@code_warntype cat_storage_type(Tuple{NTuple{3, UInt8}})

Then we get:

MethodInstance for cat_storage_type(::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}})
  from cat_storage_type(::Type{T}) where T<:Tuple in Main at /home/chenningcong/Documents/Code/juliaCode/TypeInferenceDebugger/src/debugger.jl:244
Static Parameters
  T = Tuple{Tuple{UInt8, UInt8, UInt8}}
Arguments
  #self#::Const(cat_storage_type)
  _::Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
Body::Type{Tuple{Tuple{UInt8, UInt8, UInt8}}}
1 ─ %1 = Core.tuple(Main.Tuple)::Const((Tuple,))
│   %2 = Main._cat_storage_type_tuple($(Expr(:static_parameter, 1)))::Const((Tuple{UInt8, UInt8, UInt8},))
│   %3 = Core._apply_iterate(Base.iterate, Core.apply_type, %1, %2)::Const(Tuple{Tuple{UInt8, UInt8, UInt8}})
└──      return %3

With this strategy you can infer arbitrarily large tuple, the following code infers @code_warntype cat_storage_type(Tuple{NTuple{10, UInt8}}):

for i in 1:10
  @code_warntype cat_storage_type(Tuple{NTuple{i, UInt8}})
end

But if you skip over some number (>=3) then inference fails:

for i in 1:5
  @code_warntype cat_storage_type(Tuple{NTuple{i, UInt8}})
end
@code_warntype cat_storage_type(Tuple{NTuple{7, UInt8}})

Contrasted to In Julia 1.6.1, the inference of arbitrarily large tuple succeeds in any order of evaluation.

I guess the patch that @Sacha0 quotes strengthens recursion detection and causes Julia stops to make progress with N=3, even type inference actually won't get into infinite loop. So maybe fixing type_more_complex can also fix #42835

NHDaly · 2021-11-01T19:51:17Z

I don't exactly see how the case that @Sacha0 posted in the OP on this issue should be affected by the change that #40379 (pointed to by bisect) was meant to make.

It seems that #40379 was trying to fix #40336, where inference itself could get stuck in a loop because it wasn't detecting that Type{Type{T}} was more complex than Type{T}.

But the code in @Sacha0's original post doesn't seem to ever introduce Type{...} wrappers, so I guess it shouldn't be affected?

Do you think that PR accidentally now catches other patterns as being an increase in complexity that it didn't mean to?

vtjnash · 2022-08-10T17:58:49Z

I checked on master, and this infers concretely again. Although I will note that Base.tuple_type_tail is deprecated, since it can lead to problems with correctness (#42839 (comment)).

JeffBezanson added the compiler:inference Type inference label Oct 29, 2021

Sacha0 added the regression Regression in behavior compared to a previous version label Oct 31, 2021

This was referenced Nov 2, 2021

inference: relax type_more_complex for Type #42901

Merged

Backport #42901 to 1.7 (without #42583) #42965

Closed

vtjnash closed this as completed Aug 10, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Inference regression on 1.7-RC2 and master (relative to 1.6.3) #42839

Inference regression on 1.7-RC2 and master (relative to 1.6.3) #42839

Sacha0 commented Oct 28, 2021

Sacha0 commented Oct 28, 2021

Sacha0 commented Oct 29, 2021

vtjnash commented Oct 29, 2021

KristofferC commented Oct 29, 2021

Sacha0 commented Oct 29, 2021

NHDaly commented Oct 29, 2021 •

edited

Loading

vtjnash commented Oct 29, 2021

Sacha0 commented Oct 29, 2021

Sacha0 commented Oct 29, 2021

ChenNingCong commented Oct 30, 2021

NHDaly commented Nov 1, 2021

vtjnash commented Aug 10, 2022

Inference regression on 1.7-RC2 and master (relative to 1.6.3) #42839

Inference regression on 1.7-RC2 and master (relative to 1.6.3) #42839

Comments

Sacha0 commented Oct 28, 2021

Sacha0 commented Oct 28, 2021

Sacha0 commented Oct 29, 2021

vtjnash commented Oct 29, 2021

KristofferC commented Oct 29, 2021

Sacha0 commented Oct 29, 2021

NHDaly commented Oct 29, 2021 • edited Loading

vtjnash commented Oct 29, 2021

Sacha0 commented Oct 29, 2021

Sacha0 commented Oct 29, 2021

ChenNingCong commented Oct 30, 2021

NHDaly commented Nov 1, 2021

vtjnash commented Aug 10, 2022

NHDaly commented Oct 29, 2021 •

edited

Loading