search

tonyhffong / Lint.jl

A lint tool for Julia code
Other
168 stars 33 forks source link

Lint takes too long on base/expr.jl #242

Open ikirill opened 6 years ago

ikirill commented 6 years ago

I'm using julia's base/expr.jl (which is only 343 lines, counting comments) just as an example to do some testing on, but lintfile takes a seriously unreasonable amount of time. This makes it much harder to use Lint.jl as a plugin to a text editor, because half an hour is not nearly responsive enough.

julia> import Lint; @time Lint.lintfile("/Users/kirill/Sandboxes/github/julia/base/expr.jl")

...
(I omitted STDERR output like this)
WARNING: Base.repeated is deprecated, use Base.Iterators.repeated instead.
  likely near no file:237
Lint doesn't understand @nospecialize x as an argument
...

1786.928789 seconds (3.38 G allocations: 152.721 GiB, 4.01% gc time)
/Users/kirill/Sandboxes/github/julia/base/expr.jl:42 E131 @nospecialize x: Lint does not understand argument #2
/Users/kirill/Sandboxes/github/julia/base/expr.jl:48 E131 @nospecialize x: Lint does not understand argument #3
/Users/kirill/Sandboxes/github/julia/base/expr.jl:57 E131 @nospecialize x: Lint does not understand argument #4
/Users/kirill/Sandboxes/github/julia/base/expr.jl:335 E321 x: use of undeclared symbol
/Users/kirill/Sandboxes/github/julia/base/expr.jl:341 E321 __module__: use of undeclared symbol
/Users/kirill/Sandboxes/github/julia/base/expr.jl:374 E321 __module__: use of undeclared symbol
/Users/kirill/Sandboxes/github/julia/base/expr.jl:335 I340 arg: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:252
/Users/kirill/Sandboxes/github/julia/base/expr.jl:335 I340 args: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:302
/Users/kirill/Sandboxes/github/julia/base/expr.jl:335 I340 s: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:12
/Users/kirill/Sandboxes/github/julia/base/expr.jl:335 I340 s: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:15
/Users/kirill/Sandboxes/github/julia/base/expr.jl:335 I340 sym: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:252
/Users/kirill/Sandboxes/github/julia/base/expr.jl:342 I340 m: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:48
/Users/kirill/Sandboxes/github/julia/base/expr.jl:364 I340 m: unused local variable, defined at /Users/kirill/Sandboxes/github/julia/base/expr.jl:57
ikirill commented 6 years ago

When I run it with @profile, there's some suspicious output that includes stuff like this, which I don't understand, but it looks pathological:

                      968 /Users/kirill/.julia/v0.6/Lint/src/guesstype.jl:85; guesstype(::Expr, ::Lint.LintContext)
                       968 /Users/kirill/.julia/v0.6/Lint/src/statictype.jl:81; infertype(::Function, ::Array{DataType,1})
                        968 /Users/kirill/.julia/v0.6/Lint/src/statictype.jl:98; infertype(::Function, ::Tuple{DataType,DataType})
                         961 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                          959 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                           957 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                            955 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                             952 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                              950 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                               947 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                                945 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                                 942 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                                  940 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} where N)
                                   938 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} whe...
                                    936 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} wh...
                                     934 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} wh...
                                      933 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} w...
                                       931 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} w...
                                        930 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N} ...
                                         930 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N}...
                                          928 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N}...
                                           926 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N...
                                            924 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,N...
                                             922 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T,...
                                              920 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T...
                                               919 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where T...
                                                917 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where ...
                                                 915 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where ...
                                                  913 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} where...
                                                   911 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} wher...
                                                    909 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} wher...
                                                     907 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} whe...
                                                      905 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} whe...
                                                       903 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} wh...
                                                        901 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} w...
                                                         899 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} w...
                                                          897 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} ...
                                                           895 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T} ...
                                                            893 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T}...
                                                             891 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T...
                                                              889 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{T...
                                                               886 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{...
                                                                884 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type{...
                                                                 881 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Type...
                                                                  879 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Typ...
                                                                   877 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Typ...
                                                                    875 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Ty...
                                                                     873 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{Ty...
                                                                      871 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{T...
                                                                       868 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{...
                                                                        866 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg{...
                                                                         863 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg...
                                                                          862 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vararg...
                                                                           860 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Varar...
                                                                            858 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vara...
                                                                             855 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Vara...
                                                                              854 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Var...
                                                                               852 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Var...
                                                                                849 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::Va...
                                                                                 847 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::V...
                                                                                  845 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::V...
                                                                                   843 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::...
                                                                                    841 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ::...
                                                                                     840 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, :...
                                                                                      838 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ...
                                                                                       835 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T, ...
                                                                                        834 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T,...
                                                                                         833 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T,...
                                                                                          831 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where T...
                                                                                           830 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where ...
                                                                                            829 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where ...
                                                                                             828 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where...
                                                                                              825 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} where...
                                                                                               823 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} wher...
                                                                                                822 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} whe...
                                                                                                 821 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} whe...
                                                                                                  819 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} wh...
                                                                                                   817 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} wh...
                                                                                                +1 815 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} wh...

...
omitted ~600 lines
...

                                                                                              +613 1 ./promotion.jl:7; typejoin(::Any, ::Type{T} where T, ::Type{T} whe...
TotalVerb commented 6 years ago

Thanks for this profile output. I think we need some heuristics for when to bother inferring the types of things.

ikirill commented 6 years ago

I want to point out that even just the trivial check in(Any, Base.return_types(...)) cuts down the time from 1700 to 130 seconds (see 04da125, not that it's a solution). Here's the type of thing for which typejoin takes too long (this example is 0.7s, but it runs over and over again):

const t1 = Any[Tuple{}, Bool, Bool, Bool, Bool, Bool, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int16, Int16, Int16, Int16, Int16, Int16, Int16, Int16, Int16, Int16, Int16, Int16, Int32, Int32, Int32, Int32, Int32, Int32, Int32, Int32, Int32, Int32, Int32, Int32, Int64, Int64, Int64, Int64, Int64, Int64, Int64, Int64, Int64, Int64, Int64, Int64, Int128, Int128, Int128, Int128, Int128, Int128, Int128, Int128, Int128, Int128, Int128, Int128, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt16, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt32, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt64, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, UInt128, Float16, Any, Float16, Float16, Float16, Float16, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float32, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Char, Char, Array{UInt8,1}, Array{UInt8,1}, String, String, String, String, String, Cstring, Cstring, Cwstring, Ptr{Int32}, Array{Char,1}, Symbol, VersionNumber, Any, VersionNumber, Base.Libc.FILE, BigInt, BigInt, BigInt, BigInt, BigInt, BigInt, BigInt, BigInt, BigInt, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, BigFloat, Rational{BigInt}, Union{}, Base.Random.UUID, Base.Test.GenericString, Base.LibGit2.Consts.OBJECT, Base.LibGit2.Consts.DELTA_STATUS, Base.LibGit2.Consts.GIT_MERGE, Base.LibGit2.Consts.GIT_MERGE_FILE, Base.LibGit2.Consts.GIT_MERGE_FILE_FAVOR, Base.LibGit2.Consts.GIT_MERGE_PREFERENCE, Base.LibGit2.Consts.GIT_MERGE_ANALYSIS, Base.LibGit2.Consts.GIT_REBASE_OPERATION, Base.LibGit2.Consts.GIT_SUBMODULE_IGNORE, Base.LibGit2.Consts.GIT_REPOSITORY_OPEN, Base.LibGit2.Consts.GIT_BRANCH, Base.LibGit2.Consts.GIT_FILEMODE, Base.LibGit2.Consts.GIT_CREDTYPE, Base.LibGit2.Consts.GIT_FEATURE, Base.LibGit2.Consts.GIT_CONFIG, Base.LibGit2.Consts.GIT_OPT, Base.LibGit2.Consts.GIT_PROXY, Base.LibGit2.Error.Code, Base.LibGit2.Error.Class, Base.LibGit2.GitSignature, Array{String,1}, Base.Dates.CompoundPeriod, Base.Dates.Week, Base.Dates.Week, Base.Dates.Week, Base.Dates.Week, Base.Dates.Week, Base.Dates.Week, Base.Dates.Week, Base.Dates.Day, Base.Dates.Day, Base.Dates.Day, Base.Dates.Day, Base.Dates.Day, Base.Dates.Day, Base.Dates.Day, Base.Dates.Day, Base.Dates.Hour, Base.Dates.Hour, Base.Dates.Hour, Base.Dates.Hour, Base.Dates.Hour, Base.Dates.Hour, Base.Dates.Hour, Base.Dates.Minute, Base.Dates.Minute, Base.Dates.Minute, Base.Dates.Minute, Base.Dates.Minute, Base.Dates.Minute, Base.Dates.Minute, Base.Dates.Second, Base.Dates.Second, Base.Dates.Second, Base.Dates.Second, Base.Dates.Second, Base.Dates.Second, Base.Dates.Second, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Millisecond, Base.Dates.Microsecond, Base.Dates.Microsecond, Base.Dates.Microsecond, Base.Dates.Microsecond, Base.Dates.Microsecond, Base.Dates.Microsecond, Base.Dates.Microsecond, Base.Dates.Nanosecond, Base.Dates.Nanosecond, Base.Dates.Nanosecond, Base.Dates.Nanosecond, Base.Dates.Nanosecond, Base.Dates.Nanosecond, Base.Dates.Nanosecond, Base.Dates.Month, Base.Dates.Year, DateTime, DateTime, DateTime, Date, Date, Date, Base.Dates.Time, Union{SparseMatrixCSC{Float64,Int64}, Symmetric{Float64,SparseMatrixCSC{Float64,Int64}}}, Base.Distributed.WorkerState, VecElement, Any, Any, Tuple, Union{Tuple{Any,Vararg{Any,N} where N}, Tuple{}}, Tuple{Any,Vararg{Any,N} where N}, Tuple, Pair{A,B} where B where A, Pair{_,_} where _ where _, UnitRange{T} where T<:Real, UnitRange{_} where _, Base.OneTo{_} where _, Base.OneTo{T} where T<:Real, UnitRange{_} where _, UnitRange{_} where _, StepRange{T1,T2} where T2 where T1, StepRange{_,_} where _ where _, StepRange{_,_} where _ where _, StepRangeLen{T,R,S} where S<:Base.TwicePrecision where R<:Base.TwicePrecision where T<:AbstractFloat, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{T,R,S} where S where R where T, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{_,_,_} where _ where _ where _, StepRangeLen{_,_,_} where _ where _ where _, LinSpace{T} where T, Any, LinSpace{_} where _, Any, Any, Union{Array{_,1} where _, Array{_,2} where _}, Base.TwicePrecision{T} where T, Base.TwicePrecision{_} where _, Any, Base.TwicePrecision{_} where _, Int8, UInt8, Int16, UInt16, Int32, UInt32, Int64, UInt64, Int128, UInt128, Int64, UInt64, Integer, Int64, Integer, BigInt, Any, Union{Int64, UInt64}, Any, Ptr{_} where _, Ptr{_} where _, Ptr{T} where T, Ptr{_} where _, Ref{T} where T, Base.RefArray{_,_,Void} where _ where _, Union{Array{Float64,N} where N, Array{_,0} where _, Array{_,1} where _}, Array{_,1} where _, Any, Union{Array{Float64,N} where N, Array{_,2} where _}, Any, Array{_,2} where _, Array{_,2} where _, Array{_,2} where _, Array{_,2} where _, Any, Any, Any, AbstractArray{T,2} where T, AbstractArray{T,2} where T, Union{Array{Float64,N} where N, Array{_,2} where _}, Union{Array{Float64,N} where N, Array{_,2} where _}, Union{Array{Float64,N} where N, Array{_,2} where _}, Any, Any, Array{T,n} where n where T, Array{T,n} where n where T, Any, Union{Array{Float64,N} where N, Array{_,2} where _}, Any, Array{_,2} where _, Array{_,2} where _, Array{_,2} where _, Array{_,2} where _, Union{Array{Float64,N} where N, Array{_,2} where _}, Any, Array{_,1} where _, Any, Any, Any, Any, SymTridiagonal{_} where _, Tridiagonal{_} where _, LowerTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, LowerTriangular{_,_} where _ where _, Base.LinAlg.UnitLowerTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.UnitLowerTriangular{_,_} where _ where _, UpperTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, UpperTriangular{_,_} where _ where _, Base.LinAlg.UnitUpperTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.UnitUpperTriangular{_,_} where _ where _, Base.LinAlg.QRPackedQ{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.QRPackedQ{_,_} where _ where _, Base.LinAlg.QRCompactWYQ{S,M} where M<:(AbstractArray{T,2} where T) where S, Base.LinAlg.QRCompactWYQ{_,_} where _ where _, Base.LinAlg.LQPackedQ{_,_} where _ where _, Symmetric{_,_} where _ where _, Hermitian{_,_} where _ where _, Diagonal{_} where _, Bidiagonal{_} where _, SparseMatrixCSC{Tv,Ti} where Ti<:Integer where Tv, SparseMatrixCSC{_,_} where _ where _, AbstractArray{T,N} where N where T, Any, Any, Union{Array{Float64,N} where N, Array{_,2} where _}, Any, Any, Any, Any, Any, AbstractArray{T,2} where T, Union{Array{Float64,N} where N, Array{_,2} where _}, Union{Array{Float64,N} where N, Array{_,2} where _}, Union{Array{Float64,N} where N, Array{_,2} where _}, Union{Array{Float64,N} where N, Array{_,0} where _, Array{_,1} where _}, Array{T,N} where N where T, Any, Any, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Float64, Any, Complex{_} where _, Complex{_} where _, Any, Complex, Complex{_} where _, Rational{_} where _, Rational{_} where _, Rational, Rational{_} where _, Any, Any, Any, Rational{_} where _, Rational{Int64}, Rational{Int64}, Any, Any, Any, BitArray{N} where N, Any, Dict{K,V} where V where K, Dict{_,_} where _ where _, Set{T} where T, Set{_} where _, Ptr{_} where _, Union{Cstring, Cwstring}, SubString{_} where _, Array{UInt8,1}, Any, IOContext, IOContext{_} where _, Any, Any, Any, Any, Nullable{_} where _, Nullable{T} where T, Nullable{_} where _, Nullable{_} where _, Nullable{_} where _, Nullable{_} where _, Nullable{Union{}}, Nullable{_} where _, WeakKeyDict{K,V} where V where K, WeakKeyDict{_,_} where _ where _, Any, Any, Any, Rational{BigInt}, BigFloat, Any, Integer, Any, RowVector{_,_} where _ where _, SymTridiagonal{_} where _, Tridiagonal{_} where _, Tridiagonal{_} where _, SymTridiagonal{_} where _, LowerTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, LowerTriangular{_,_} where _ where _, Base.LinAlg.UnitLowerTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.UnitLowerTriangular{_,_} where _ where _, UpperTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, UpperTriangular{_,_} where _ where _, Base.LinAlg.UnitUpperTriangular{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.UnitUpperTriangular{_,_} where _ where _, Base.LinAlg.QR{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.QR{_,_} where _ where _, Base.LinAlg.QRCompactWY{T,M} where M<:(AbstractArray{T,2} where T) where T, Base.LinAlg.QRCompactWY{_,_} where _ where _, Base.LinAlg.QRPivoted{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.QRPivoted{_,_} where _ where _, Base.LinAlg.LQ{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.LQ{_,_} where _ where _, Base.LinAlg.Cholesky{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.Cholesky{_,_} where _ where _, Base.LinAlg.CholeskyPivoted{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.CholeskyPivoted{_,_} where _ where _, Base.LinAlg.LU{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.LU{_,_} where _ where _, Base.LinAlg.BunchKaufman{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.BunchKaufman{_,_} where _ where _, Base.LinAlg.LDLt{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.LDLt{S,U} where U where S, Factorization{T} where T, Base.LinAlg.QR{_,_} where _ where _, Base.LinAlg.QRCompactWY{_,_} where _ where _, Any, Any, Any, Any, Base.LinAlg.QRPivoted{_,_} where _ where _, Any, Any, Any, Any, Base.LinAlg.QRPackedQ{_,_} where _ where _, Base.LinAlg.QRCompactWYQ{_,_} where _ where _, Any, Any, Any, Any, Base.LinAlg.LQ{_,_} where _ where _, Any, Any, Any, Any, Base.LinAlg.LQPackedQ{_,_} where _ where _, Any, Any, Any, Any, Any, Any, Any, Any, Symmetric{T,S} where S<:(AbstractArray{T,2} where T) where T, Symmetric{_,_} where _ where _, Hermitian{T,S} where S<:(AbstractArray{T,2} where T) where T, Hermitian{_,_} where _ where _, Base.LinAlg.Cholesky{_,_} where _ where _, Base.LinAlg.CholeskyPivoted{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.CholeskyPivoted{_,_} where _ where _, Any, Any, Any, Any, Any, Any, Any, Any, Base.LinAlg.LU{_,_} where _ where _, Base.LinAlg.LU{_,_} where _ where _, Tridiagonal{_} where _, Any, Tridiagonal{_} where _, Any, Any, Any, Any, Any, Tridiagonal{_} where _, Base.LinAlg.BunchKaufman{T,S} where S<:(AbstractArray{T,2} where T) where T, Base.LinAlg.BunchKaufman{_,_} where _ where _, Diagonal{T} where T, Diagonal{_} where _, Tridiagonal{_} where _, Bidiagonal{T} where T, Bidiagonal{_} where _, Base.LinAlg.Givens{T} where T, Base.LinAlg.Givens{_} where _, Base.LinAlg.Rotation{T} where T, Base.LinAlg.Rotation{_} where _, Base.LinAlg.Givens{_} where _, Base.LinAlg.Rotation{_} where _, Bidiagonal{_} where _, SymTridiagonal{_} where _, Tridiagonal{_} where _, Diagonal{_} where _, SymTridiagonal{_} where _, Tridiagonal{_} where _, Bidiagonal{_} where _, Diagonal{_} where _, Bidiagonal{_} where _, SymTridiagonal{_} where _, Tridiagonal{_} where _, Diagonal{_} where _, Bidiagonal{_} where _, SymTridiagonal{_} where _, Tridiagonal{_} where _, Base.LinAlg.LDLt{_,_} where _ where _, Base.LinAlg.LDLt{_,_} where _ where _, SymTridiagonal{_} where _, SymTridiagonal{_} where _, SymTridiagonal{_} where _, Union{Array{Float64,N} where N, Array{_,2} where _}, Union{Array{Float64,N} where N, Array{_,2} where _}, Any, Any, Any, Any, Float64, Rational{_} where _, SparseMatrixCSC{Tv,Ti} where Ti<:Integer where Tv, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{Tv,Ti} where Ti where Tv, SparseMatrixCSC{_,Int64} where _, SparseMatrixCSC{_,Int64} where _, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{_,_} where _ where _, SparseMatrixCSC{_,_} where _ where _, SparseVector{_,_} where _ where _, SparseVector{_,_} where _ where _, SparseVector{_,_} where _ where _, SparseVector{Tv,Ti} where Ti<:Integer where Tv, SparseVector{_,_} where _ where _, SparseVector{_,_} where _ where _, SparseVector{_,_} where _ where _, SparseVector{_,_} where _ where _, SparseVector{Tv,Ti} where Ti where Tv, SparseVector{_,_} where _ where _, Union{Base.SparseArrays.CHOLMOD.Dense{Complex{Float64}}, Base.SparseArrays.CHOLMOD.Dense{Float64}}, Base.SparseArrays.CHOLMOD.Dense{_} where _, Base.SparseArrays.CHOLMOD.Dense{_} where _, Union{Base.SparseArrays.CHOLMOD.Sparse{Complex{Float64}}, Base.SparseArrays.CHOLMOD.Sparse{Float64}}, Union{Base.SparseArrays.CHOLMOD.Sparse{Complex{Float64}}, Base.SparseArrays.CHOLMOD.Sparse{Float64}}, Base.SparseArrays.CHOLMOD.Sparse{Complex{Float64}}, Base.SparseArrays.CHOLMOD.Sparse{Float64}, Union{Base.SparseArrays.CHOLMOD.Sparse{Complex{Float64}}, Base.SparseArrays.CHOLMOD.Sparse{Float64}}, Union{}, Any, Base.SparseArrays.CHOLMOD.Sparse{_} where _, Base.SparseArrays.CHOLMOD.Sparse{_} where _, Base.SparseArrays.CHOLMOD.Sparse{_} where _, Union{Hermitian{_,_} where _ where _, SparseMatrixCSC{Tv,Ti} where Ti where Tv}, SharedArray{_,_} where _ where _, SharedArray{_,_} where _ where _, SharedArray{_,_} where _ where _, UpperTriangular{_,_} where _ where _, LowerTriangular{_,_} where _ where _, Base.LinAlg.UnitUpperTriangular{_,_} where _ where _, Base.LinAlg.UnitLowerTriangular{_,_} where _ where _, LowerTriangular{_,_} where _ where _, UpperTriangular{_,_} where _ where _, Any, Any, Union{Real, Tuple{Any,Vararg{Any,N} where N}}, Union{Real, Tuple{Any,Vararg{Any,N} where N}}, Base.Use_StepRangeLen_Instead{T} where T<:AbstractFloat, Base.Use_StepRangeLen_Instead{_} where _, Base.Use_StepRangeLen_Instead{_} where _, Base.Use_StepRangeLen_Instead{_} where _, Any, Base.RefValue{_} where _, Any]

function go()
  @time typejoin(t1...)
end

I'm a little surprised that typejoin can be so slow when it's clear that the answer is Any.

TotalVerb commented 6 years ago

Maybe another heuristic could to be output Any when length(unique(Base.return_types(...))) exceeds a threshold, as if there are 10 or more distinct possible inferred return types, my bet is that typejoin would return Any anyway.

ikirill commented 6 years ago

Another example of a very expensive call in statictype.jl:

julia> println(@time Base.return_types(Base.At_mul_B!, (Any, Any, Any)))
  4.820505 seconds (8.64 M allocations: 416.880 MiB, 7.96% gc time)
Any[Any, Any, AbstractArray{T,1} where T, Union{Base.ReshapedArray{T,1,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray, DenseArray{T,1}, SubArray{T,1,A,I,L} where L} where I<:Tuple{Vararg{Union{Base.AbstractCartesianIndex, Int64, Range{Int64}},N} where N} where A<:Union{Base.ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray where N where T, DenseArray} where T, Union{Base.ReshapedArray{T,1,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray, DenseArray{T,1}, SubArray{T,1,A,I,L} where L} where I<:Tuple{Vararg{Union{Base.AbstractCartesianIndex, Int64, Range{Int64}},N} where N} where A<:Union{Base.ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray where N where T, DenseArray} where T, Union{Union{Base.ReshapedArray{T,1,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray, DenseArray{T,1}, SubArray{T,1,A,I,L} where L} where I<:Tuple{Vararg{Union{Base.AbstractCartesianIndex, Int64, Range{Int64}},N} where N} where A<:Union{Base.ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray where N where T, DenseArray}, Union{Base.ReshapedArray{T,2,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray, DenseArray{T,2}, SubArray{T,2,A,I,L} where L} where I<:Tuple{Vararg{Union{Base.AbstractCartesianIndex, Int64, Range{Int64}},N} where N} where A<:Union{Base.ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{Base.MultiplicativeInverses.SignedMultiplicativeInverse{Int64},N} where N} where A<:DenseArray where N where T, DenseArray}} where T, AbstractArray{T,1} where T, AbstractArray{T,2} where T, Any]

It's cached the second time:

julia> println(@time Base.return_types(Base.At_mul_B!, (Any, Any, Any)))
  0.000249 seconds (57 allocations: 2.516 KiB)

I don't know why it runs on At_mul_B!, it doesn't occur directly in expr.jl. Does this mean that Lint will potentially try to infer return types of an arbitrarily large number of base functions, applied to argument types like (Any,Any,Any)? I can't imagine Lint will gain any useful information from that. Replacing the return_types -> typejoin sequence with return Any gets the time down to 40s.

TotalVerb commented 6 years ago

It's been a while since I looked over that part of the code, but if I recall correctly, if there are undefined symbols Lint will in fact read all the files in the package (in this case, base/) to find it, even though it only reports problems in expr.jl. So it does indeed infer return types of an arbitrarily large number of base functions, and that would be nice to change in the future.

ikirill commented 6 years ago

I suspect one problem might be that any time lint can't figure out a type of something, it ends up passing Any as the corresponding type of an argument to return_types, so it ends up with a lot of rather pointless calls like this, where return_types has little chance of giving a helpful return type:

julia> @time Base.return_types(Base.getindex, (Any, Any))
  3.710983 seconds (3.30 M allocations: 161.212 MiB, 8.36% gc time)
118-element Array{Any,1}:
... omitted ...

where return_types has to look at all known methods of getindex because its first argument could be anything.

TotalVerb commented 6 years ago

I'm worried that blanketly refusing to infer things when some arguments are Any might lead to some missed inferences. For example, repr can be inferred to String and string can be inferred to AbstractString when their argument types are Any. Maybe a compromise would be to have a cap on the number of methods a function can have before we attempt to infer it with a broad signature?

ikirill commented 6 years ago

There is another consequence to this that I didn't notice at first, which is that if you use Lint.jl as a background checker (I use flycheck in emacs), it can eat up a lot of battery life unnoticed.