Speed loss (factor 10): left division for matrices (A \ B) with LU factorization

[moritzdrechselgrau]

Matrix division A \ B has become extremely slow in julia 1.7 compared to e.g. julia 1.3.
In particular, LU factorization is much slower in julia 1.7.
There seems to be no speed problem with QR factorization.
All of this also holds for julia 1.6 vs 1.3.

Here is a minimal example.

using LinearAlgebra, BenchmarkTools, Random

Random.seed!(3)
A = rand(70,70)
x = rand(70)

# test functions
myleftdiv1(A::AbstractMatrix, B::AbstractVecOrMat) = LinearAlgebra.:\(A, B)
myleftdiv2(A::AbstractMatrix, B::AbstractVecOrMat) = LinearAlgebra.lu(A, Val(true)) \ B
myleftdiv2b(A::AbstractMatrix, B::AbstractVecOrMat) = LinearAlgebra.lu(A, RowMaximum()) \ B
myleftdiv3(A::AbstractMatrix, B::AbstractVecOrMat) = LinearAlgebra.qr(A, Val(true)) \ B

Note that for a square but not upper or lower diagonal matrix such as A above, \(A, B) eventually executes lu(A, Val(true)). I use lu(A, Val(true)) as this is supported in all versions of julia while lu(A, RowMaximum()), the default in julia 1.7, is only supported in julia 1.7. However, this difference does not matter (see myleftdiv2 vs. myleftdiv2b below).

Source code for julia 1.3: https://github.com/JuliaLang/julia/blob/2d5741174ce3e6a394010d2e470e4269ca54607f/stdlib/LinearAlgebra/src/generic.jl#L1007-L1053
Source code for julia 1.7: https://github.com/JuliaLang/julia/blob/bf534986350a991e4a1b29126de0342ffd76205e/stdlib/LinearAlgebra/src/generic.jl#L1097-L1145

Performance using julia 1.3

julia> myleftdiv1(A,x) ≈ myleftdiv2(A,x) ≈ myleftdiv3(A,x)
true

julia> @benchmark myleftdiv1(A, x)
BenchmarkTools.Trial: 2948 samples with 1 evaluation.
 Range (min … max):  870.500 μs …  17.656 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):       1.588 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):     1.689 ms ± 624.549 μs  ┊ GC (mean ± σ):  0.12% ± 1.68%

julia> @benchmark myleftdiv2(A, x)
BenchmarkTools.Trial: 3102 samples with 1 evaluation.
 Range (min … max):  961.200 μs … 57.139 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):       1.413 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):     1.605 ms ±  1.701 ms  ┊ GC (mean ± σ):  0.11% ± 1.72%

julia> @benchmark myleftdiv3(A, x)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  102.900 μs …   9.207 ms  ┊ GC (min … max): 0.00% … 95.36%
 Time  (median):     350.050 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   364.839 μs ± 434.881 μs  ┊ GC (mean ± σ):  8.21% ±  7.04%

julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, cannonlake)

Performance using julia 1.7

julia> myleftdiv1(A,x) ≈ myleftdiv2(A,x) ≈ myleftdiv3(A,x)
true

julia> @benchmark myleftdiv1(A, x)
BenchmarkTools.Trial: 378 samples with 1 evaluation.
 Range (min … max):  808.500 μs … 119.170 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):      10.232 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):    13.230 ms ±  11.133 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

julia> @benchmark myleftdiv2(A, x)
BenchmarkTools.Trial: 316 samples with 1 evaluation.
 Range (min … max):   1.088 ms … 105.779 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     12.137 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   15.806 ms ±  13.511 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

julia> @benchmark myleftdiv2b(A, x)
BenchmarkTools.Trial: 478 samples with 1 evaluation.
 Range (min … max):  528.700 μs … 48.797 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):       8.662 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):    10.455 ms ±  9.234 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

julia> @benchmark myleftdiv3(A, x)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  275.500 μs …  17.191 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     345.900 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   405.128 μs ± 332.029 μs  ┊ GC (mean ± σ):  4.02% ± 6.35%

julia> versioninfo()
Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, tigerlake)

[Seelengrab]

Seems fixed on somewhat recent master:

julia> @benchmark myleftdiv1(A, x)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  35.376 μs …  1.273 ms  ┊ GC (min … max): 0.00% … 93.86%
 Time  (median):     36.072 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   42.662 μs ± 22.724 μs  ┊ GC (mean ± σ):  1.10% ±  2.32%

julia> @benchmark myleftdiv2(A, x)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  35.337 μs …  1.474 ms  ┊ GC (min … max): 0.00% … 92.97%
 Time  (median):     36.016 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   40.488 μs ± 23.034 μs  ┊ GC (mean ± σ):  1.26% ±  2.34%

julia> @benchmark myleftdiv3(A, x)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  197.896 μs …  1.514 ms  ┊ GC (min … max): 0.00% … 81.33%
 Time  (median):     203.524 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   214.261 μs ± 87.056 μs  ┊ GC (mean ± σ):  2.76% ±  5.83%

julia> versioninfo()
Julia Version 1.9.0-DEV.428
Commit 3cff21e725 (2022-04-22 01:46 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 4 × Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, skylake)
  Threads: 1 on 4 virtual cores

[andreasnoack]

It would be great if you could identify the minor release that introduced the slowdown. It's probably an issue related to OpenBLAS and it might be specific to OS and CPU.

[moritzdrechselgrau]

It still works on 1.5 but does not on 1.6. So, the minor release that introduced the slowdown is julia 1.6.

julia> @benchmark myleftdiv1(A, x)
BenchmarkTools.Trial: 3087 samples with 1 evaluation.
 Range (min … max):  803.100 μs …   7.028 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):       1.511 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):     1.611 ms ± 580.877 μs  ┊ GC (mean ± σ):  0.15% ± 1.93%

julia> versioninfo()
Julia Version 1.5.4
Commit 69fcb5745b (2021-03-11 19:13 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, tigerlake)

[dkarrasch]

Seems fixed on somewhat recent master:

I'm getting very comparable timings on

julia> versioninfo()
Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin19.5.0)
  CPU: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)

and

julia> versioninfo()
Julia Version 1.6.6
Commit b8708f954a (2022-03-28 07:17 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.7.0)
  CPU: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)

[AbhilashReddyM]

edit: I tested v1.8 rc1 and it worked as expected out of the box.

I too came across this problem. I replaced the libopenblas64_.dll that came bundled with the installer with one that I built myself from source. That addressed the immediate issue. I don't know what side-effects there might be however.

julia> versioninfo()
Julia Version 1.7.3
Commit 742b9abb4d (2022-05-06 12:58 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, tigerlake)

[giordano]

For those with a Tiger Lake CPU and Julia v1.7 (which uses OpenBLAS 0.3.13), setting the environment variable

export OPENBLAS_CORETYPE=SKYLAKEX

before starting julia should let OpenBLAS 0.3.13 use the right kernels for your CPU, even if autodetection doesn't work, because CPUID autodetection of Tiger Lake was added only to OpenBLAS 0.3.14.

[ViralBShah]

We have a newer OpenBLAS now, but in general it always takes time to get support for newer CPU releases.