JuliaLang/julia — pull request #8316 by gchisholm (2014-09-11 20:47:55+00:00)
Title: Sort SparseCSC elements function and speed up sparse matrix multiplication

A suggested addition.

Replacing the dual transpose used in the sparse matrix multiplication with an in place sort of the rowval and nzval elements. This seems to outperform in particular with larger matrices.

julia> x = sprand(n, m, 0.0002);

julia> s = sprand(m, k, 0.001);

julia> @time y = x * s;
elapsed time: 56.447965143 seconds (11903648416 bytes allocated, 0.23% gc time)

julia> @time y = spmm(x, s);
elapsed time: 35.558409459 seconds (13790626144 bytes allocated, 5.49% gc time)

Avoiding the gc time by improving the allocation of the two Array's would further improve performance, I did test with a if statement to avoid allocations, but that seemed to decrease perf particularly with smaller pairs of matrix.

Either way, I assume a Sparse sort function would have some longer term benefit.