Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
ikirill opened this issue Sep 2, 2017 · 9 comments
Open

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

ikirill opened this issue Sep 2, 2017 · 9 comments

Comments

@ikirill
Copy link
Contributor

ikirill commented Sep 2, 2017 •
edited
Loading

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
Copy link
Contributor Author

ikirill commented Sep 2, 2017 •
edited
Loading

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
Copy link
Collaborator

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

ikirill added a commit to ikirill/Lint.jl that referenced this issue Sep 5, 2017
@ikirill
A hack to not run typejoin so much, relates to tonyhffong#242.
04da125
@ikirill
Copy link
Contributor Author

ikirill commented Sep 5, 2017 •
edited
Loading

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
Copy link
Collaborator

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
Copy link
Contributor Author

ikirill commented Sep 5, 2017 •
edited
Loading

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
Copy link
Collaborator

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
Copy link
Contributor Author

ikirill commented Sep 6, 2017

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
Copy link
Collaborator

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
Copy link
Contributor Author

ikirill commented Sep 16, 2017

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@ikirill @TotalVerb