Banded matrix support triples compile time

[jebej]

On my fast desktop, running @time using OrdinaryDiffEq takes 15 seconds.

A couple of versions ago, it used to start much more quickly. I manually checked the loading time in a clean environment, and the biggest jump in load time happens when moving from 5.11.1 to 5.12.0.

The time goes from ~5sec to 15sec. Hopefully this can be improved.

(ODELoadTime) pkg> add OrdinaryDiffEq@5.11                                                                            
  Updating registry at `C:\Users\Jeremy\.julia\registries\General`                                                    
  Updating git-repo `https://github.com/JuliaRegistries/General.git`                                                  
 Resolving package versions...                                                                                        
 Installed OrdinaryDiffEq ─ v5.11.1                                                                                   
  Updating `C:\Users\Jeremy\temp\ODELoadTime\Project.toml`                                                            
  [1dea7af3] ↑ OrdinaryDiffEq v5.10.0 ⇒ v5.11.1                                                                       
  Updating `C:\Users\Jeremy\temp\ODELoadTime\Manifest.toml`                                                           
  [01453d9d] ↓ DiffEqDiffTools v1.3.0 ⇒ v0.14.0                                                                       
  [1dea7af3] ↑ OrdinaryDiffEq v5.10.0 ⇒ v5.11.1                                                                       
                                                                                                                      
(ODELoadTime) pkg>                                                                                                    
                                                                                                                      
C:\Users\Jeremy\AppData\Local\Cmder                                                                                   
λ julia -q                                                                                                            
julia> using Pkg; Pkg.activate("C:\\Users\\Jeremy\\temp\\ODELoadTime\\")                                              
"C:\\Users\\Jeremy\\temp\\ODELoadTime\\Project.toml"                                                                  
                                                                                                                      
(ODELoadTime) pkg> precompile                                                                                         
Precompiling project...                                                                                               
Precompiling OrdinaryDiffEq                                                                                           
[ Info: Recompiling stale cache file C:\Users\Jeremy\.julia\compiled\v1.1\OrdinaryDiffEq\DlSvy.ji for OrdinaryDiffEq [
1dea7af3-3e70-54e6-95c3-0bf5283fa5ed]                                                                                 
                                                                                                                      
julia> @time using OrdinaryDiffEq                                                                                     
  4.952551 seconds (10.26 M allocations: 612.715 MiB, 5.28% gc time)                                                  
                                                                                                                      
(ODELoadTime) pkg> add OrdinaryDiffEq@5.12                                                                            
  Updating registry at `C:\Users\Jeremy\.julia\registries\General`                                                    
  Updating git-repo `https://github.com/JuliaRegistries/General.git`                                                  
 Resolving package versions...                                                                                        
 Installed OrdinaryDiffEq ─ v5.12.0                                                                                   
  Updating `C:\Users\Jeremy\temp\ODELoadTime\Project.toml`                                                            
  [1dea7af3] ↑ OrdinaryDiffEq v5.11.1 ⇒ v5.12.0                                                                       
  Updating `C:\Users\Jeremy\temp\ODELoadTime\Manifest.toml`                                                           
  [79e6a3ab] + Adapt v1.0.0                                                                                           
  [ec485272] + ArnoldiMethod v0.0.4                                                                                   
  [aae01518] + BandedMatrices v0.13.0                                                                                 
  [8e7c35d0] + BlockArrays v0.10.1                                                                                    
  [ffab5731] + BlockBandedMatrices v0.5.2                                                                             
  [01453d9d] ↑ DiffEqDiffTools v0.14.0 ⇒ v1.3.0                                                                       
  [1a297f60] + FillArrays v0.7.4                                                                                      
  [d25df0c9] + Inflate v0.1.1                                                                                         
  [5078a376] + LazyArrays v0.12.3                                                                                     
  [093fc24a] + LightGraphs v1.3.0                                                                                     
  [a3b82374] + MatrixFactorizations v0.2.0                                                                            
  [1dea7af3] ↑ OrdinaryDiffEq v5.11.1 ⇒ v5.12.0                                                                       
  [699a6c99] + SimpleTraits v0.9.1                                                                                    
  [47a9eef4] + SparseDiffTools v0.9.2                                                                                 
  [19fa3120] + VertexSafeGraphs v0.1.0                                                                                
  [9abbd945] + Profile                                                                                                
                                                                                                                      
julia>                                                                                                                
                                                                                                                      
C:\Users\Jeremy\AppData\Local\Cmder                                                                                   
λ julia -q                                                                                                            
julia> using Pkg; Pkg.activate("C:\\Users\\Jeremy\\temp\\ODELoadTime\\")                                              
"C:\\Users\\Jeremy\\temp\\ODELoadTime\\Project.toml"                                                                  
                                                                                                                      
(ODELoadTime) pkg> precompile                                                                                         
Precompiling project...                                                                                               
Precompiling OrdinaryDiffEq                                                                                           
[ Info: Recompiling stale cache file C:\Users\Jeremy\.julia\compiled\v1.1\OrdinaryDiffEq\DlSvy.ji for OrdinaryDiffEq [
1dea7af3-3e70-54e6-95c3-0bf5283fa5ed]                                                                                 
                                                                                                                      
julia> @time using OrdinaryDiffEq                                                                                     
 15.079790 seconds (59.11 M allocations: 3.677 GiB, 5.76% gc time)                                                    

[jebej]

This seems to be caused primarily by SparseDiffTools.

[ChrisRackauckas]

Looks like the issue is BandedMatrices.jl:

@time using BandedMatrices #  14.922930 seconds (33.07 M allocations: 2.179 GiB, 5.20% gc time)
@time using BlockBandedMatrices # 6.882466 seconds (5.43 M allocations: 339.653 MiB, 3.98% gc time)
@time using DiffEqDiffTools # 1.188521 seconds (729.68 k allocations: 37.182 MiB, 8.63% gc time)
@time using ForwardDiff # 0.918514 seconds (749.80 k allocations: 46.918 MiB, 3.23% gc time)
@time using LightGraphs # 0.827393 seconds (479.37 k allocations: 25.458 MiB, 1.46% gc time)
@time using Requires # 0.001731 seconds (757 allocations: 40.563 KiB)
@time using VertexSafeGraphs # 0.035792 seconds (27.22 k allocations: 1.399 MiB)
@time using Adapt # 0.076683 seconds (24.38 k allocations: 1.382 MiB)
@time using LinearAlgebra # 0.004319 seconds (1.60 k allocations: 88.016 KiB)
@time using SparseArrays # 0.003787 seconds (1.61 k allocations: 88.203 KiB)
@time using ArrayInterface # 0.210675 seconds (96.83 k allocations: 5.000 MiB)

@dlfivefifty

[dlfivefifty]

I’m in the process of simplifying BandedMatrices which should hopefully fix this

[ChrisRackauckas]

Good to hear. I would hate to drop the automated banded matrix support due to this, since banded matrices are quite common! In fact, I was hoping to add an example using a BandedMatrix as the Jacobian type in http://docs.juliadiffeq.org/latest/tutorials/advanced_ode_example.html#Using-Structured-Matrix-Types-1 , so this will be getting more and more ingrained into what we are doing.

[dlfivefifty]

Unfortunately my "grand scheme" to improve loading time is not as successful as I thought:

julia> @time using BandedMatrices
  5.957725 seconds (31.10 M allocations: 2.030 GiB, 7.27% gc time)

This is in branch

JuliaLinearAlgebra/BandedMatrices.jl#146

That removes all LazyArray code.

I'll have to do code-bisection to see if I can track down the culprit: though it may just be StridedArray overrides needed to avoid ambiguities in *, etc., in which case I'm not sure there's anything we can do on the package level.

[ChrisRackauckas]

Honestly it should be added to Base to be in the sysimage and allow more of LinearAlgebra to produce and use BandedMatrix outputs, but that's a whole different story.

[dlfivefifty]

First step is getting

https://github.com/JuliaMatrices/ArrayLayouts.jl

into StdLib/LinearAlgebra.jl. This implements a trait-based version of mul! hence avoiding "ambiguity hell", and is a more developed version of the PR I tried to get merged in Julia v0.7-:

JuliaLang/julia#25558

This will avoid the need for StridedArray all together.

[dlfivefifty]

I think the culprit is actually MatrixFactorizations.jl, which is almost verbatim the same as StdLib/LinearAlgebra.jl code (it adds a QL factorization, and templates out a type in QR ...)

Probably I can get rid of a lot of the StridedArrays in this code now, which would fix things.

[dlfivefifty]

Hmm, Even taking out MatrixFactorizations only reduces it to 4s. Looking at Code-bisection it's completely due to StridedArray overloads needed to avoid ambiguity errors in lmul!, rmul!, etc.

The only reasonable way to improve this is to rewrite StdLib/LinearAlgebra.jl to not use StridedArray so much.

[ChrisRackauckas]

Actually,

JuliaDiff/SparseDiffTools.jl@71693f9

it's all handed by ArrayInterface.jl, so we don't need it.

[ChrisRackauckas]

JuliaDiff/SparseDiffTools.jl@eb42179

Thanks @jebej for the hunting. Everything is handled through Requires, so all Banded stuff is opt-in. I hope this gets fixed, but at least it's not an issue that's going to be apparent unless someone specifically asks for banded now!

[dlfivefifty]

I have an idea on how to work around this: just loop over concrete types that make up StridedArray in function definitions. I'll try this out sometime...

[jebej]

It appeard OrdinaryDiffEq is slow again, taking 10s to load.