tomtung
commented
2 years ago I tried confirming the speed regression with a quick & scrappy benchmark.
I first cloned sprs locally, and patch it to add back the previous csr_mulacc_dense_colmaj implementation with a suffix _old:
--- a/src/sparse/prod.rs
+++ b/src/sparse/prod.rs
@@ -295,6 +295,46 @@ pub fn csc_mulacc_dense_colmaj<'a, N, A, B, I, Iptr>(
}
}
+/// CSR-dense colmaj multiplication
+///
+/// Performs better if rhs has few columns.
+pub fn csr_mulacc_dense_colmaj_old<'a, N1, N2, NOut, I, Iptr>(
+ lhs: CsMatViewI<N1, I, Iptr>,
+ rhs: ArrayView<N2, Ix2>,
+ mut out: ArrayViewMut<'a, NOut, Ix2>,
+) where
+ N1: 'a + Num + Copy,
+ N2: 'a + Num + Copy,
+ NOut: 'a + Num + Copy,
+ N1: std::ops::Mul<N2, Output = NOut>,
+ I: 'a + SpIndex,
+ Iptr: 'a + SpIndex,
+{
+ if lhs.cols() != rhs.shape()[0] {
+ panic!("Dimension mismatch");
+ }
+ if lhs.rows() != out.shape()[0] {
+ panic!("Dimension mismatch");
+ }
+ if rhs.shape()[1] != out.shape()[1] {
+ panic!("Dimension mismatch");
+ }
+ if !lhs.is_csr() {
+ panic!("Storage mismatch");
+ }
+ let axis1 = Axis(1);
+ for (mut ocol, rcol) in out.axis_iter_mut(axis1).zip(rhs.axis_iter(axis1)) {
+ for (orow, lrow) in lhs.outer_iterator().enumerate() {
+ let mut prev = ocol[[orow]];
+ for (rrow, &lval) in lrow.iter() {
+ let rval = rcol[[rrow]];
+ prev = prev + lval * rval;
+ }
+ ocol[[orow]] = prev;
+ }
+ }
+}
+
/// CSR-dense colmaj multiplication
///
/// Performs better if rhs has few columns.then I modified Cargo.toml a bit
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -29,6 +29,7 @@ smallvec = "1.4.0"
rayon = { version = "1.3.0", optional = true }
num_cpus = { version = "1.13.0", optional = true }
approx = { version = "0.5", optional = true }
+rand = { version = "0.8", default-features = false, features = ["small_rng"] }
[dev-dependencies]
num-derive = "0.3"
@@ -37,7 +38,6 @@ tempfile = "3.1.0"
bincode = "1.2.0"
tobj = "3.0"
image = { version = "0.23.0", default-features = false, features = ["png"] }
-rand = { version = "0.8", default-features = false, features = ["small_rng"] }
[[bench]]
name = "suite"
@@ -51,6 +51,11 @@ harness = false
name = "sorting"
harness = false
+[[bin]]
+name = "scrappy_bench"
+path = "src/scrappy_bench.rs"
+
+
[workspace]
members = [
"sprs-ldl",Finally, I wrote the following simple benchmark program to src/scrappy_bench.rs:
extern crate rand;
extern crate sprs;
extern crate ndarray;
use rand::Rng;
use sprs::prod::{csr_mulacc_dense_colmaj, csr_mulacc_dense_colmaj_old};
fn generate_random_csr(shape: sprs::Shape) -> sprs::CsMat<f32> {
let mut rng = rand::thread_rng();
let (rows, cols) = shape;
let nnz = rng.gen_range(1..rows * cols / 2);
let mut mat = sprs::TriMat::<f32>::new(shape);
for _ in 0..nnz {
let r = rng.gen_range(0..rows);
let c = rng.gen_range(0..cols);
let v = rng.gen::<f32>();
mat.add_triplet(r, c, v);
}
mat.to_csr()
}
fn generate_random_array(shape: sprs::Shape) -> ndarray::Array2<f32> {
let mut rng = rand::thread_rng();
let data = (0..shape.0 * shape.1).map(|_| rng.gen()).collect::<Vec<f32>>();
ndarray::Array2::from_shape_vec(shape, data).unwrap()
}
fn main() {
const N_RUNS_PER_LOOP: usize = 1000;
const N_LOOP: usize = 10;
const MAX_LEFT_DIM: usize = 200;
const MAX_RIGHT_DIM: usize = 200;
const MAX_INNER_DIM: usize = 5000;
let mut rng = rand::thread_rng();
for _ in 0..N_LOOP {
let left_shape: sprs::Shape = (
rng.gen_range(10..=MAX_LEFT_DIM),
rng.gen_range(10..=MAX_INNER_DIM),
);
let right_shape: sprs::Shape = (
left_shape.1,
rng.gen_range(1..=MAX_RIGHT_DIM),
);
let rand_csr = generate_random_csr(left_shape);
let rand_vec = generate_random_array(right_shape);
let mut out = ndarray::Array2::<f32>::zeros((left_shape.0, right_shape.1));
let start_t = std::time::Instant::now();
for _ in 0..N_RUNS_PER_LOOP {
csr_mulacc_dense_colmaj(rand_csr.view(), rand_vec.view(), out.view_mut());
}
println!("New\t{}ms", start_t.elapsed().as_millis());
let start_t = std::time::Instant::now();
for _ in 0..N_RUNS_PER_LOOP {
csr_mulacc_dense_colmaj_old(rand_csr.view(), rand_vec.view(), out.view_mut());
}
println!("Old\t{}ms", start_t.elapsed().as_millis());
println!("");
}
}The benchmark can then be run by cargo run --release scrappy_bench. Here's the result of one such run:
New 4846ms
Old 1874ms
New 450ms
Old 166ms
New 12071ms
Old 4460ms
New 1651ms
Old 581ms
New 60298ms
Old 38835ms
New 61863ms
Old 21512ms
New 7074ms
Old 2528ms
New 32ms
Old 10ms
New 5847ms
Old 2168ms
New 12322ms
Old 4290msAs you can see, the new implementation with MulAcc is indeed significantly slower than the old one.
mulimoen
aujxn
I just found out that my implementation of an ML model has been training up to several times slower than before. After some debugging, turns out that the cause was vbarrielle/sprs#276, where the
MulAcctrait was introduced in d56bd72e4f883c9f12f7e38c47c2141784127f21, and specifically where theCopybound was removed in d2f0da76df51be6e81839b04ed64c5121a2ec640. For details please see https://github.com/tomtung/omikuji/pull/32.My intuitive guess is that the trait
MulAccgot rid of theCopybound at the cost of forcing the values to be passed as references (pointers). This might have made it hard for the compiler to do inlining and/or other optimizations. since the+=operation is typically in the innermost part of the loop, any slow-down in such hot spots would result in significant speed regression.I don't have context on the introduction of
MulAcc, so I'm not sure what's the right way to fix this. Let me know if there's something I could help with.