A case where FixedSizedArrays seems way slower than Vectors

[MarcoRiggirello]

Hi,
Thanks a lot for your work. In my project I need to perform sparse matrix-vector multiplication, with matrices that are nonzero only along few subdiagonals.
I found that this structure

struct HollowSymmetricCDS{Tv, Ti<:Integer} <: AbstractMatrix{Tv}
    n::Int
    offsets::Vector{Ti}
    nzval::Vector{Tv}
    diag_ptrs::Vector{Ti}
end

and a specialized version of

function LinearAlgebra.mul!(y::AbstractVector, A::HollowSymmetricCDS, x::AbstractVector)
    n = A.n
    if length(y) != n || length(x) != n
        throw(DimensionMismatch("Vectors must have length $n."))
    end
    fill!(y, 0)
    @inbounds for diag_idx in 1:length(A.offsets)
        offset = A.offsets[diag_idx]
        start_ptr = A.diag_ptrs[diag_idx]
        # The length of this diagonal is n - offset
        len = A.diag_ptrs[diag_idx + 1] - start_ptr
        for i in 1:len
            j = i + offset
            val = A.nzval[start_ptr + i - 1]
            y[i] += val * x[j]
            y[j] += val * x[i]
        end
    end
    return y
end

Can reduce the computation time by a factor of two (In this case is a 100000x100000 matrix with only 2 nonzero superdiagonals)

# Standard sparse csc matrix
julia> @benchmark A*x
BenchmarkTools.Trial: 7436 samples with 1 evaluation per sample.
 Range (min … max):  561.197 μs …   2.088 ms  ┊ GC (min … max): 0.00% … 54.11%
 Time  (median):     624.196 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   656.399 μs ± 103.487 μs  ┊ GC (mean ± σ):  2.97% ±  6.99%

     ▂▅▇█▇▆▄▁ ▂                                                  
  ▃▆▇███████████▆▇▆▅▄▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▂▂▂▂▂▂▃▃▃▃▃▃▂▂▃▃▃▃▃▃▃▃▂ ▄
  561 μs           Histogram: frequency by time          994 μs <

 Memory estimate: 781.32 KiB, allocs estimate: 3.

# My implementation
julia> @benchmark A*x
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
 Range (min … max):  222.149 μs …   2.052 ms  ┊ GC (min … max): 0.00% … 71.69%
 Time  (median):     239.331 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   271.138 μs ± 104.724 μs  ┊ GC (mean ± σ):  6.63% ± 11.40%

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

 Memory estimate: 781.32 KiB, allocs estimate: 3.

However, something strange happens when I use your library to store the nonzero elements

struct HollowSymmetricCDS{Tv, Ti<:Integer} <: AbstractMatrix{Tv}
    n::Int
    offsets::FixedSizeVector{Ti}
    nzval::FixedSizeVector{Tv}
    diag_ptrs::FixedSizeVector{Ti}
end

julia> @benchmark A*x
BenchmarkTools.Trial: 66 samples with 1 evaluation per sample.
 Range (min … max):  68.901 ms … 151.049 ms  ┊ GC (min … max): 1.49% … 54.42%
 Time  (median):     71.429 ms               ┊ GC (median):    4.23%
 Time  (mean ± σ):   76.440 ms ±  19.055 ms  ┊ GC (mean ± σ):  9.70% ± 12.28%

   █                                                            
  ▆██▃▂▁▂▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃ ▁
  68.9 ms         Histogram: frequency by time          150 ms <

 Memory estimate: 49.29 MiB, allocs estimate: 2981422.

I did not touch the mul! function. Do you have a clue of what is going on?

[giordano]

I can't look at this right now, but what version of Julia are you using? If it isn't nightly, can you try that? If that solves the performance issue that's likely a duplicate of #152 and #70. (edit: but you already have an explicit inbounds annotation, so that's probably not the same issue)

[MarcoRiggirello]

Nightly does not solve the issue...

[giordano]

Oh, note that FixedSizeVector{T} isn't concrete, you need to use FixedSizeVectorDefault{T}

[MarcoRiggirello]

I'll try right now

[MarcoRiggirello]

Changing to concrete type makes performance in line with standard Vectors!

julia> @benchmark A*x
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
 Range (min … max):  222.049 μs …  2.496 ms  ┊ GC (min … max): 0.00% … 77.32%
 Time  (median):     243.695 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   274.121 μs ± 98.256 μs  ┊ GC (mean ± σ):  6.85% ± 12.01%

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

 Memory estimate: 781.32 KiB, allocs estimate: 3.