100x compile time slowdown in BandedMatrices.jl

[dlfivefifty]

BandedMatrices.jl has had an almost 100x slowdown (see "bug-slowmul" branch) in 0.7-alpha:

julia> A = brand(5,5,1,1); b = randn(5); @time A*b # v0.6.2
  0.375991 seconds (335.46 k allocations: 16.421 MiB)

VS

julia> A = brand(5,5,1,1); b = randn(5); @time A*b  # v0.7, branch "bug-slowmul"
 24.676427 seconds (57.04 M allocations: 5.038 GiB, 3.76% gc time)

I sped this up to "only" 15x slowdown on "master" by making the code type stable:

julia> A = brand(5,5,1,1); b = randn(5); @time A*b # v0.7, branch "master"
  5.644144 seconds (16.42 M allocations: 1.252 GiB, 4.54% gc time)

[ufechner7]

On my PC the slow down is much smaller:

julia> A = brand(5,5,1,1); b = randn(5); @time A*b # v0.6.2
WARNING: importing deprecated binding Base.uninitialized into BandedMatrices.
WARNING: Base.uninitialized is deprecated, use undef instead.
 in module BandedMatrices
WARNING: Base.uninitialized is deprecated, use undef instead.
 in module BandedMatrices
WARNING: Base.uninitialized is deprecated, use undef instead.
 in module BandedMatrices
┌ Warning: using `A[I...] = x` to implicitly broadcast `x` across many locations is deprecated. Use `A[I...] .= x` instead.
│   caller = _banded_generic_matvecmul!(::Array{Float64,1}, ::Char, ::BandedMatrix{Float64}, ::Array{Float64,1}) at interface.jl:184
└ @ BandedMatrices interface.jl:184
  2.024492 seconds (7.35 M allocations: 432.613 MiB, 5.60% gc time)

With julia 0.63 I also need about 0.38 seconds.
I am using:

julia> versioninfo()
Julia Version 0.7.0-alpha.58
Commit c9b2274 (2018-06-09 05:25 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.0 (ORCJIT, skylake)
Environment:
  JULIA_PKG3_PRECOMPILE = enable

julia> 

And part of the slow down might be due to the deprecations.

[dlfivefifty]

You’re not on the right branch, since master doesn’t have any warnings.

…

Sent from my iPhone

On 9 Jun 2018, at 22:43, Uwe Fechner ***@***.***> wrote: On my PC the slow down is much smaller: julia> A = brand(5,5,1,1); b = randn(5); @time A*b # v0.6.2 WARNING: importing deprecated binding Base.uninitialized into BandedMatrices. WARNING: Base.uninitialized is deprecated, use undef instead. in module BandedMatrices WARNING: Base.uninitialized is deprecated, use undef instead. in module BandedMatrices WARNING: Base.uninitialized is deprecated, use undef instead. in module BandedMatrices ┌ Warning: using `A[I...] = x` to implicitly broadcast `x` across many locations is deprecated. Use `A[I...] .= x` instead. │ caller = _banded_generic_matvecmul!(::Array{Float64,1}, ::Char, ::BandedMatrix{Float64}, ::Array{Float64,1}) at interface.jl:184 └ @ BandedMatrices interface.jl:184 2.024492 seconds (7.35 M allocations: 432.613 MiB, 5.60% gc time) With julia 0.63 I also need about 0.38 seconds. I am using: julia> versioninfo() Julia Version 0.7.0-alpha.58 Commit c9b2274 (2018-06-09 05:25 UTC) Platform Info: OS: Linux (x86_64-linux-gnu) CPU: Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-6.0.0 (ORCJIT, skylake) Environment: JULIA_PKG3_PRECOMPILE = enable julia> — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[ufechner7]

How can I checkout master with Pkg3?

[KristofferC]

You can pkg> add BandedMatrices#master.

[ufechner7]

Now I get:

julia> A = brand(5,5,1,1); b = randn(5); @time A*b # v0.6.2
  4.385049 seconds (16.40 M allocations: 1.245 GiB, 4.53% gc time)

So this is a slow-down by a factor of 11.5 .
But perhaps the problem is the new implementation of BandedMatrices in master and not Julia?

[dlfivefifty]

The 100x slowdown is in a different branch “bug-slowmul”. The comparison between 0.6.2 and 0.7 was done on the same branch.

In any case, 30s compilation time is a problem with the compiler, not a package.

[juliohm]

Naive question, is the slow down present if you start julia --depwarn=no?

[dlfivefifty]

There's no deprecation warnings, so julia --depwarn=no doesn't improve anything. (And it would be strange if it did.)

[dlfivefifty]

Here's another ridiculously slow example on master:

using Compat, BandedMatrices

BandedMatrixWithZero = Union{BandedMatrix{Float64}, UniformScaling}
# need to define the concept of zero
Base.zero(::Type{BandedMatrixWithZero}) = 0*I
A = BandedMatrix{BandedMatrixWithZero}(undef, 1, 2, 0, 1);
A[1,1] = BandedMatrix(Eye(1),(0,1))
A[1,2] = BandedMatrix(Zeros(1,2),(0,1))
A[1,2][1,1] = -1/3
A[1,2][1,2] = 1/3
B = BandedMatrix{BandedMatrixWithZero}(undef, 2, 1, 1, 1);
B[1,1] = 0.2BandedMatrix(Eye(1),(0,1))
B[2,1] = BandedMatrix(Zeros(2,1), (1,0))
B[2,1][1,1] = -2/30
B[2,1][2,1] = 1/3
@time A*B # 6s (v0.6.2) VS 620s (1.56 G allocations: 170.395 GiB, 5.82% gc time) (v0.7-alpha)

[ViralBShah]

I can't just paste it in the repl and reproduce. Can you provide a complete script?

[ViralBShah]

Just needed using BandedMatrices.

[ViralBShah]

Took 1714 seconds on my computer 0.7-alpha. The code doesn't run on 0.6.3 with undef not defined. What is the 0.6 version like?

[dlfivefifty]

Add using Compat

[ViralBShah]

Even with Compat:

julia> B = BandedMatrix{BandedMatrixWithZero}(undef, 2, 1, 1, 1)
2×1 BandedMatrices.BandedMatrix{Union{BandedMatrices.BandedMatrix{Float64}, UniformScaling}}:
Error showing value of type BandedMatrices.BandedMatrix{Union{BandedMatrices.BandedMatrix{Float64}, UniformScaling}}:
ERROR: UndefRefError: access to undefined reference

[dlfivefifty]

That’s just an error in show. If you ignore it the rest of the code should run.

[ViralBShah]

Ok. I am just doing it mechanically, but these comments should help others reproducing. It did run in 15s for me on 0.6.3.

[dlfivefifty]

I updated it so it should now be copy-and-pastable.

[StefanKarpinski]

Important but #triage is not appropriate.

[ViralBShah]

The reason I had tagged triage was if this needs to go on the 1.0 milestone.

[dlfivefifty]

I'm not one to over emphasise the "publicity" angle of 1.0, but I think it's a bad idea to release 1.0 with known serious bugs. Indeterministic compile time is a serious bug to me. (I don't know if it'll impact BandedMatrices.jl itself, as I'm planning to rewrite the whole matrix multiplication code.)

[JeffBezanson]

I tried the example in #27512 (comment) and it took about 5 seconds. Is this considered fixed?

[dlfivefifty]

Is this considered fixed?

Yep, it only takes me 3s 🎉 And the original example(on master) is only about 1s:

julia> A = brand(5,5,1,1); b = randn(5); @time A*b;

  1.106104 seconds (5.57 M allocations: 300.408 MiB, 9.57% gc time)