Performance Regression in 1.5

[FHell]

I have the following performance regression:

$ julia-14 bench.jl
 Activating environment at `~/Bench/Project.toml`
  1.618 μs (1 allocation: 3.88 KiB)
  6.179 μs (9 allocations: 9.61 KiB)
$ julia-15 bench.jl
 Activating environment at `~/Bench/Project.toml`
  2.732 μs (1 allocation: 3.88 KiB)
  9.054 μs (9 allocations: 9.63 KiB)

with the following code:

using Pkg
Pkg.activate(@__DIR__)

using LightGraphs
using BenchmarkTools
using Random

Random.seed!(3)

### Defining the graph
N = 100 # nodes
g = barabasi_albert(N, 5)
B = incidence_matrix(g, oriented=true)
B_t = transpose(B)
x0 = rand(N)

@btime B_t * x0
@btime x0 .+ B * sin.(B_t * x0)

[PallHaraldsson]

[EDIT: I can reproduce the better MWE in next comment.] I tried your code (starting at using LightGraphs, you're not timing most of it anyway), and I can't reproduce. Or I should say I more or less get your 1.5 timings, but also similar in my older 1.4 and 1.6 nightly.

$ time ~/julia-1.5.0/bin/julia bench.jl 
  1.980 μs (1 allocation: 3.88 KiB)   # if anything this was faster on 1.5
  8.667 μs (9 allocations: 9.63 KiB) # this was similar

real	0m15,729s   # these numbers where probably slightly lower on Julia 1.5, but include some slightly higher one-time costs you were not measuring
user	0m14,150s
sys	0m2,456s

I would do for your version 1.4:

pkg> st LightGraphs

and then in your 1.5:

pkg> add LightGraphs@v1.3.3  # or whatever your other installation gave you, I guess lower version

My theory is that you do not have the same versions, and the regression is in LightGraphs. I'm not saying it isn't there, just try for sure the same versions in both. Then report there or where it is, and until fixed you could user older version in 1.5 too.

[FHell]

It's the same version of LightGraphs on Julia 1.4 and 1.5. Either way, B_t is of type Transpose(SparseMatrix), so LightGraphs is only used to initialize the matrix and doesn't show up in the performance critical code. I investigated some more and could simplify it further:

using BenchmarkTools

N = 100
x0 = ones(N)

A_t = transpose(ones(Int64, N, 5*N))

@btime $A_t * $x0

Has the following timings on my machine:
Julia 1.4 : 50.774 μs (1 allocation: 4.06 KiB)
Julia 1.5 : 63.061 μs (1 allocation: 4.06 KiB)

If everything is float, or without the transpose there is no performance difference, so the origin here seems to be the interaction of transpose, Int and Float. So I also had a look at pure Integer performance, and there is a major regression here:

using BenchmarkTools

N = 100
x0 = ones(Int64, N)

A_t = transpose(ones(Int64, N, 5*N))

@btime $A_t * $x0

Julia 1.4 : 15.053 μs (1 allocation: 4.06 KiB)
Julia 1.5 : 198.067 μs (1 allocation: 4.06 KiB)

My Versions are:
Version 1.4.1 (2020-04-14)
Version 1.5.0 (2020-08-01)

Running on a stock Ubuntu 18.04 and on the same Project.toml/Manifest.toml with only BenchmarkTools in it. Also on Discourse someone could reproduce the original results on MacOS.

[PallHaraldsson]

I can confirm:

julia> @btime $A_t * $x0;  # on 1.4.0, neither of us on latest 1.4.2, possibly improvements from 1.4.0->1.4.1 doubling speed, worth looking into (regression related to?)
  32.068 μs (1 allocation: 4.06 KiB)

vs. on 1.5.0:
  227.553 μs (1 allocation: 4.06 KiB)

on 1.6 (1 day old master):
  230.399 μs (1 allocation: 4.06 KiB)

I can also confirm regression for former example, there numbers closer to yours.

[chethega]

Thanks for the nice reproducer! Can you verify whether #36975 fixes the issue for you?

You can simply monkey-patch, i.e. @eval LinearAlgebra begin [...] end where you copy-paste the function body from my PR.

[orialb]

I tested #36975 on my machine with the MWE above:

• 1.4.1 : 23.501 μs (1 allocation: 4.06 KiB)
• 1.5.0: 171.612 μs (1 allocation: 4.06 KiB)
• 1.5.0 with Improve inferrability of generic matrix-vector multiplication #36975 : 23.622 μs (1 allocation: 4.06 KiB)

OS: macOS (x86_64-apple-darwin18.7.0)

[FHell]

I can confirm that the second bunch of minimal working examples is fixed by this. However, the performance regression in sparse int * float that I reported at the top remains. Here is a new MWE that doesn't use LightGraphs for initialization:

using Pkg
Pkg.activate(@__DIR__)

println("Julia $VERSION :")

using BenchmarkTools
using SparseArrays
using Random

Random.seed!(3)

N = 100
B1 = sprand(Int64, N, 5*N, 0.1)
B = transpose(B1)
x0 = ones(N)

println("Sparse Int * Float")
@btime B * x0

include("patch.jl")

println("Sparse Int * Float patched")
@btime B * x0

Julia 1.4.1 :
Sparse Int * Float
5.330 μs (1 allocation: 4.06 KiB)
Sparse Int * Float patched
5.358 μs (1 allocation: 4.06 KiB)

Julia 1.5.0 :
Sparse Int * Float
6.903 μs (1 allocation: 4.06 KiB)
Sparse Int * Float patched
6.898 μs (1 allocation: 4.06 KiB)

I don't have time right now to run more thorough experiments on the various permutations of sparse, types and transpose that show up here for the next days.

Files attached (including the patch.jl I include above that fixes the second regression reported) if someone else wants to have a look.
bench.zip

[vtjnash]

Then we'll call this fixed by #36975

[FHell]

Then we'll call this fixed by #36975

Note that only one (the far more dramatic one) of two performance issues reported above are reported as fixed by this.