# \[ANN\] Fast SpMv with CompressedSparseBlocks.jl
**URL:** https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680
**Category:** Package Announcements
**Tags:** performance, linearalgebra, sparse
**Created:** [July 23, 2022, 4:24pm UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680 "2022-07-23T16:24:20Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@pitsianis](https://discourse.julialang.org/u/pitsianis)
#### Post date: [July 23, 2022, 4:24pm UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/1 "2022-07-23T16:24:20Z")
If you have a computation with an iteration where the time is dominated by a large sparse matrix multiplication,
```julia
julia> using LinearAlgebra, SparseArrays, BenchmarkTools
julia> n = 2^22; d = 10; A = sprand(n,n,d/n); x = rand(n);
julia> y = @btime $A*$x;
909.738 ms (2 allocations: 32.00 MiB)
julia> yt = @btime $(transpose(A))*$x;
640.637 ms (2 allocations: 32.00 MiB)
```
you may want to consider the [CompressedSparseBlocks](https://github.com/fcdimitr/CompressedSparseBlocks.jl) package, a Julia wrapper to the [CSB Library](https://github.com/PASSIONLab/CSB).
```julia
julia> using CompressedSparseBlocks
```
Transforming a `SparseMatrixCSC` into a `SparseMatrixCSB` is straightforward, though it might take a few seconds for very large matrices.
```julia
julia> Ac = SparseMatrixCSB(A);
```
but the transformation cost can be eliminated with the speedup from CSB.
```julia
julia> yc = @btime $Ac*$x;
352.766 ms (2 allocations: 32.00 MiB)
julia> yc ā y
true
julia> yct = @btime $(transpose(Ac))*$x;
379.569 ms (3 allocations: 32.00 MiB)
julia> yct ā yt
true
```
Enjoy!
---
### Author:  [@ranocha](https://discourse.julialang.org/u/ranocha)
#### Post date: [July 25, 2022, 6:18am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/2 "2022-07-25T06:18:32Z")
Thanks, this looks nice! Which scalar types does this package support?
---
### Author:  [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)
#### Post date: [July 25, 2022, 6:39am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/3 "2022-07-25T06:39:48Z")
Could you compare to the case one is using Sparse MKL?
---
### Author:  [@fcdimitr](https://discourse.julialang.org/u/fcdimitr)
#### Post date: [July 25, 2022, 10:23am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/4 "2022-07-25T10:23:36Z")
The figure on the README is comparing CSB to MKLSparse
> **[GitHub - fcdimitr/CompressedSparseBlocks.jl: A Julia interface (wrapper) to...](https://github.com/fcdimitr/CompressedSparseBlocks.jl)**
>
> A Julia interface (wrapper) to the Compressed Sparse Blocks (CSB) library. - GitHub - fcdimitr/CompressedSparseBlocks.jl: A Julia interface (wrapper) to the Compressed Sparse Blocks (CSB) library.
---
### Author:  [@fcdimitr](https://discourse.julialang.org/u/fcdimitr)
#### Post date: [July 25, 2022, 10:26am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/5 "2022-07-25T10:26:17Z")
Currently, it supports Float64. It should be straightforward to add additional scalar types in the C/C++ interface, e.g., Bool, Float32.
---
### Author:  [@fredrikekre](https://discourse.julialang.org/u/fredrikekre)
#### Post date: [July 25, 2022, 10:53am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/6 "2022-07-25T10:53:16Z")
It looks like it uses threads by default (which Julia does not) so a more fair comparison would be:
```julia
julia> using LinearAlgebra, SparseArrays, BenchmarkTools,
CompressedSparseBlocks, ThreadedSparseArrays
julia> n = 2^22; d = 10; A = sprand(n,n,d/n); x = rand(n);
# Regular AT * x (no threading)
julia> @btime $(transpose(A)) * $x;
466.139 ms (2 allocations: 32.00 MiB)
# SparseMatrixCSB (8 threads)
julia> @btime $(transpose(SparseMatrixCSB(A))) * $x;
155.475 ms (2 allocations: 32.00 MiB)
# ThreadedSparseMatrixCSC (8 threads)
julia> @btime $(transpose(ThreadedSparseMatrixCSC(A))) * $x;
218.281 ms (63 allocations: 32.01 MiB)
```
(Still some speedup though, but not as drastic as in the OP.)
---
### Author:  [@fcdimitr](https://discourse.julialang.org/u/fcdimitr)
#### Post date: [July 25, 2022, 10:59am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/7 "2022-07-25T10:59:49Z")
That is correct. The figure on the README compares against MKLSparse, which is also multithreaded.
---
### Author:  [@fcdimitr](https://discourse.julialang.org/u/fcdimitr)
#### Post date: [July 25, 2022, 1:38pm UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/8 "2022-07-25T13:38:02Z")
One additional advantage of CSB is that the multiplication with A does not suffer from longer latency than that with the transposed matrix. The symmetric performance eliminates the need for an additional copy in a different layout (as with CSR or CSC) for reducing the speed gap at the cost of double memory consumption.
```julia
julia> using LinearAlgebra, SparseArrays, BenchmarkTools,
CompressedSparseBlocks, ThreadedSparseArrays
julia> n = 2^22; d = 10; A = sprand(n,n,d/n); x = rand(n);
julia> Threads.nthreads()
10
julia> CompressedSparseBlocks.getWorkers()
10
# Regular A * x (no threading)
julia> @btime $(A) * $x;
796.632 ms (2 allocations: 32.00 MiB)
# SparseMatrixCSB (8 threads)
julia> @btime $(SparseMatrixCSB(A)) * $x;
102.310 ms (2 allocations: 32.00 MiB)
# ThreadedSparseMatrixCSC (8 threads)
julia> @btime $(ThreadedSparseMatrixCSC(A)) * $x;
795.302 ms (20 allocations: 32.00 MiB)
```
---
### Author:  [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)
#### Post date: [July 26, 2022, 11:07am UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/9 "2022-07-26T11:07:37Z")
The text below the figure says MKL but the legend says differently so Iām not sure I understand the relative performance compared to MKL.
---
### Author:  [@fcdimitr](https://discourse.julialang.org/u/fcdimitr)
#### Post date: [July 26, 2022, 1:01pm UTC](https://discourse.julialang.org/t/ann-fast-spmv-with-compressedsparseblocks-jl/84680/10 "2022-07-26T13:01:51Z")
Thank you for your interest in the package!
Each plot shows the relative speedup (in wall-clock execution time) of 3 operations
- CSC transp. (via MKL) `A' * x`
- CSB (CompressedSparseBlocks.jl) `Acsb * x`
- CSB transp. (CompressedSparseBlocks.jl) `Acsb' * x`
with respect to CSC (via MKL) `A * x`.
The different plots correspond to different densities (`d`) and number of vectors (`RHS`).
The environment and the script for generating the figure are committed under `benchmarks/run_benchmarks.jl`.
We will add more comments on the `README` to clarify these points.