Skip to content

Missing specialization of adjoint sparse matrix times Diagonal #619

@JoshuaLampert

Description

@JoshuaLampert

I noticed some dramatic performance issues when multiplying an adjoint sparse matrix with a Diagonal matrix. This is because there is no specialization defined in SparseArrays.jl, which means this matrix matrix product uses some inefficient fallback.

julia> using SparseArrays, LinearAlgebra, BenchmarkTools

julia> N = 1000
1000

julia> A = sparse(I, N, N); B = Diagonal(ones(N));

julia> @benchmark A * B
BenchmarkTools.Trial: 10000 samples with 10 evaluations per sample.
 Range (min  max):  2.226 μs  267.405 μs  ┊ GC (min  max):  0.00%  95.71%
 Time  (median):     2.550 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   3.079 μs ±   5.644 μs  ┊ GC (mean ± σ):  12.02% ±  7.47%

  ▁▆██▇▆▅▄▃▂▁                                             ▁▁  ▂
  ███████████▇▆▅▄▆▅▃▄▅▄▁▄▃▁▁▁▁▁▃▃▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▃▅▇████ █
  2.23 μs      Histogram: log(frequency) by time      7.72 μs <

 Memory estimate: 23.76 KiB, allocs estimate: 10.

julia> @benchmark A' * B
BenchmarkTools.Trial: 850 samples with 1 evaluation per sample.
 Range (min  max):  5.838 ms   10.277 ms  ┊ GC (min  max): 0.00%  0.00%
 Time  (median):     5.869 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   5.882 ms ± 159.429 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

        ▁▅▆▅▇█▇▆▅▃▂                                            
  ▃▃▃▅█▇██████████████▆▆▆▅▅▄▄▄▃▄▃▃▃▂▂▃▂▂▂▃▂▂▂▂▂▃▁▃▂▂▂▁▃▁▁▂▂▂▂ ▄
  5.84 ms         Histogram: frequency by time        5.98 ms <

 Memory estimate: 57.51 KiB, allocs estimate: 15.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions