As noted in #188, benchamrks were needed to be able to monitor the performance of sparse matrix products.
In this PR, I implemented benchmarks of the old and new (SMMP) implementation of product in sprs, scipy's matrix product, and also the product for the C++ library eigen.
There are benchmarks inspecting the influence of the matrices shape on the performance, with the number of non zeros growing as the number of rows:
The quadratic performance of the old product implementation can clearly be seen. It's also possible to observe that eigen has a lower performance than scipy and sprs, and I suspect this is because their sparse matrix format is an extension of CSR that reserves some space to be able to more efficiently insert new elements in the matrix. Maintaining this possibility must have a runtime cost.
Scipy looks a bit faster than sprs most of the time, but it does not guarantee that the indices are sorted in the resulting matrix, so most of the overhead in sprs comes from sorting. There are also some huge variations for scipy when dealing with big matrices, and I can't find a good explanation for this. Maybe sometimes the python runtime kicks in and impacts my benchmarks?
Here are benchmarks with the density increasing. This is probably less representative of real workloads, but it helps monitoring the different performance caracteristics.
Shape (1500, 2500):
Shape (15000, 25000):
Shape (150000, 25000):
Shape (150000, 250000):
The same trends appear, but we can see the old sprs implementation was actually good for small shapes and high densities. However this is probably not a very realistic workload. With these quite dense matrices, there are more elements per row in the result, so the sorting overhead for sprs augments, meaning scipy gets a larger edge.
As noted in #188, benchamrks were needed to be able to monitor the performance of sparse matrix products.
In this PR, I implemented benchmarks of the old and new (SMMP) implementation of product in sprs, scipy's matrix product, and also the product for the C++ library eigen.
There are benchmarks inspecting the influence of the matrices shape on the performance, with the number of non zeros growing as the number of rows:
The quadratic performance of the old product implementation can clearly be seen. It's also possible to observe that eigen has a lower performance than scipy and sprs, and I suspect this is because their sparse matrix format is an extension of CSR that reserves some space to be able to more efficiently insert new elements in the matrix. Maintaining this possibility must have a runtime cost.
Scipy looks a bit faster than sprs most of the time, but it does not guarantee that the indices are sorted in the resulting matrix, so most of the overhead in sprs comes from sorting. There are also some huge variations for scipy when dealing with big matrices, and I can't find a good explanation for this. Maybe sometimes the python runtime kicks in and impacts my benchmarks?
Here are benchmarks with the density increasing. This is probably less representative of real workloads, but it helps monitoring the different performance caracteristics.
Shape (1500, 2500):![sparse_mult_perf_1500_2500](https://user-images.githubusercontent.com/1874105/81745595-66986700-94a5-11ea-9199-6addd38078b8.png)
Shape (15000, 25000):![sparse_mult_perf_15000_25000](https://user-images.githubusercontent.com/1874105/81745639-70ba6580-94a5-11ea-8c8e-baec15d3921b.png)
Shape (150000, 25000):![sparse_mult_perf_150000_25000](https://user-images.githubusercontent.com/1874105/81745668-7e6feb00-94a5-11ea-8999-f8345c9719ec.png)
Shape (150000, 250000):![sparse_mult_perf_150000_250000](https://user-images.githubusercontent.com/1874105/81745694-892a8000-94a5-11ea-9fd8-e185c1e2d254.png)
The same trends appear, but we can see the old sprs implementation was actually good for small shapes and high densities. However this is probably not a very realistic workload. With these quite dense matrices, there are more elements per row in the result, so the sorting overhead for sprs augments, meaning scipy gets a larger edge.