Matrix multiplication performance

63 points Remarkable_Hour_615 47 comments

I recently benchmarked some matrix multiplication algorithms in Scala (blog post, repo). I've been going through and doing the same thing in Rust, with plans to try out a few additional approaches, and the Rust results have all been turning out slower than Scala (repo). I'm hoping someone with more Rust experience can help me figure out what might be going on. Is this just the JVM being impressive, or am I missing an opportunity to speed up my Rust code (or both).

Here are some sample benchmarks (details on how I calculated them below):

Algorithm Scala Rust
Naive multiplication 906 ms 1.103 s
Tiling (optimal tile size) 499 ms 749.8 ms
Parallel bands of tiles, 4 threads 174 ms 210.9 ms

More details:

  • I benchmarked everything by multiplying 1024 x 1024 matrices of 64 bit floats generated uniformly in [0, 1).
  • I ran all the benchmarks on my laptop (specs).
  • I benchmarked the Scala code with the JMBH and Rust with Divan.
  • I ran all the Rust code with cargo bench so it should optimize the build.
  • In the benchmarking code, I construct the matrices before running the benchmarks and only time the actual multiplication.
  • The code for the first the naive and tiled approaches is as close as possible.
  • For the parallel versions I used the same approach of dividing the matrix into bands of tiles, one per thread. For Scala I used futures, and for Rust I divided the product matrix into one mutable chunk per thread and used Crossbeam.

I listed the results for the various algorithms to show that the speed difference is consistent, but we can just focus on the naive version. My Scala code is:

    for i <- 0 until a.rows do
      for j <- 0 until b.cols do
        var sum = 0
        for k <- 0 until a.cols do
            sum = sum + a(i, k) * b(k,j)
        prod.set(i, j, sum)

And Rust:

    for i in 0..m1.rows {
        for j in 0..m2.cols {
            let mut acc = 0.0;
            for k in 0..m1.cols {
                acc += m1.at(i, k) * m2.at(k, j);
            }
            out.set(i, j, acc);
        }
    }

Why is the Rust slower? Thanks for any help!