Performance issues: Two examples of Rust programs significantly slower than their C++ versions

[hjyamauchi]

I thought it might be useful to report here as I encountered two examples where the Rust versions were much slower than the C++ counterparts compiled with Clang. I ported them for my learning.

ary3

ary3.rs is about 4 times slower than ary3.cpp.

Based on the generated code, it seems that the difference is caused by a missed loop vectorization in the Rust version (details).

matrix

matrix.rs is about 2 times slower than matrix.cpp

I think that the difference is caused by the following (details):

• the mmult function isn't inlined into the main function (so the constant size of the vectors aren't constant propagated to mmult).
• the bounds checks are not elided.
• loop unrolling has not been applied.

In both cases, the differences are in the frontend (rustc and clang) output, as opposed to the LLVM backend.

This is with Rustc 1.86.0 (05f9846f8 2025-03-31) compiling with -O on my x86_64 pc. The Clang version I used was Clang 20.1.5 compiling with -O2.

[ds84182]

For the first example (ary3) the loop is vectorized when using iterators instead of indexing: https://rust.godbolt.org/z/bva1Tx6qz

For the second example (matrix) it's not equivalent to the C++ version. Since the size is a compile-time constant it would be better to use an array instead of nested Vecs. e.g. [[i32; SIZE]; SIZE]. And if the heap allocations are desired, use Box::new.

[hjyamauchi]

@ds84182 Thanks for the comments.

ary3: I can confirm that when iterators are used, loop vectorization indeed happens

vector.body159:                                   ; preds = %bb13, %vector.body159
  %index160 = phi i64 [ %index.next169, %vector.body159 ], [ 0, %bb13 ]
  %106 = xor i64 %index160, -1
  %107 = add i64 %_0.sroa.0.0.sroa.speculated.i.i.i, %106
  %108 = getelementptr inbounds i32, ptr %_73117, i64 %107
  %109 = getelementptr inbounds i32, ptr %x.val24118, i64 %107
  %110 = getelementptr inbounds i8, ptr %109, i64 -12
  %111 = getelementptr inbounds i8, ptr %109, i64 -28
  %wide.load = load <4 x i32>, ptr %110, align 4, !alias.scope !82, !noalias !85
  %wide.load161 = load <4 x i32>, ptr %111, align 4, !alias.scope !82, !noalias !85
  %112 = getelementptr inbounds i8, ptr %108, i64 -12
  %113 = getelementptr inbounds i8, ptr %108, i64 -28
  %wide.load163 = load <4 x i32>, ptr %112, align 4, !alias.scope !88, !noalias !94
  %wide.load165 = load <4 x i32>, ptr %113, align 4, !alias.scope !88, !noalias !94
  %114 = add <4 x i32> %wide.load163, %wide.load
  %115 = add <4 x i32> %wide.load165, %wide.load161
  store <4 x i32> %114, ptr %112, align 4, !alias.scope !88, !noalias !94
  store <4 x i32> %115, ptr %113, align 4, !alias.scope !88, !noalias !94
  %index.next169 = add nuw i64 %index160, 8
  %116 = icmp eq i64 %index.next169, %n.vec157
  br i1 %116, label %middle.block152, label %vector.body159, !llvm.loop !95

and the performance is on par with C++. Nice!

matrix:
I'd use arrays and https://rust.godbolt.org/z/Gsf8PxjrP seems to work and is on par with the C++ version in performance. But it may be considered different in that the function mmult would work on arrays of any sizes while the (fixed-size) array version in Rust would be tied to the specific SIZE.

[austinorr]

Your mmult function is tough to convert into iterators which would help the compiler elide the bounds checks, but the loop is so tight these really add up.
I'm able to get a lot of performance back just by disabling them with a couple unsafe blocks. This is still as safe as the c++ code obviously, but now you have to remember to only call it with square matrices of the same size or undefined things will happen (same rules as the c++ code):

fn mmult_vec(
    m1: &Vec<Vec<i32>>,
    m2: &Vec<Vec<i32>>, 
    m3: &mut Vec<Vec<i32>>,
) {
    let len = m1.len();
    for i in 0..len {
        for j in 0..len {
            let mut val = 0;
            for k in 0..len {
                unsafe {
                    val += m1.get_unchecked(i).get_unchecked(k) * m2.get_unchecked(k).get_unchecked(j);
                }
            }
            unsafe {
                let elem = m3.get_unchecked_mut(i).get_unchecked_mut(j);
                *elem = val;
            }
        }
    }
}

This should allow you to keep the flexibility of having variable matrix sizes while keeping the performance. It'd be nice if the compiler could elide the bounds checks, but it's hard to prove to the compiler that both axes of these matrices will always be in bounds with this algorithm. Iterators usually help with that, but it's tricky and maybe even less readable for this case.

On godbolt my timings for the unsafe implementation above match the boxed & compile-time-sized timing.

[hjyamauchi]

@austinorr That's very interesting!

I tried something like the following version after some manual loop invariant code hoisting and loop versioning. The main difficulty is in hoisting/eliminating the bound check on the index j on m2[k]. This results in timings within a single digit % of the C++ version and it's bounds-safe, I think. I'm not sure the compiler would be able to do such transformations in practice, but one can hope :)

fn mmult(rows: usize, cols: usize, m1: &Vec::<Vec::<i32>>,
         m2: &Vec::<Vec::<i32>>, m3: &mut Vec::<Vec::<i32>>) {
    let mut do_fast_path = true;
    let mut min_m2_k_len = usize::MAX;
    if cols <= m2.len() {
        for k in 0..cols {
            unsafe {
                min_m2_k_len = std::cmp::min(min_m2_k_len, m2.get_unchecked(k).len());
            }
        }
    } else {
        do_fast_path = false;
    }
    if do_fast_path && cols <= min_m2_k_len {
        for i in 0..rows {
            let m1_i = &m1[i];
            let m3_i = &mut m3[i];
            for j in 0..cols {
                let m3_i_j = &mut m3_i[j];
                let mut val = 0;
                if cols <= m1_i.len() && cols <= m2.len() {
                    // The fast path                                                                                                                                        
                    for k in 0..cols {
                        unsafe {
                            val += m1_i.get_unchecked(k) * m2.get_unchecked(k).get_unchecked(j);
                        }
                    }
                } else {
                    // The slow path                                                                                                                                        
                    for k in 0..cols {
                        val += m1_i[k] * m2[k][j];
                    }
                }
                *m3_i_j = val;
            }
        }
    } else {
        // The slow path, the original loop                                                                                                                                 
        for i in 0..rows {
            for j in 0..cols {
                let mut val = 0;
                for k in 0..cols {
                    val += m1[i][k] * m2[k][j];
                }
                m3[i][j] = val;
            }
        }
    }
}

[austinorr]

Nice, though this seems way safer than the c++ code now which has no explicit bounds checks (iirc -O3 removes bounds checks, right?) and would crash if a user tried to multiply two non-square non-equal-sized matrices. Looks like rust is actually winning by a lot if you say they’re within 1%.

I’d suggest moving all the size checks to a different ‘checker’ function though since the function is now so complex. Just write the fast one cleanly, and the if needed add a checker function. If this is internal code, you probably already know that your matrices are compatible.