An experiment with SIMD in Rust using fearless_simd

SIMD is having a moment right now.

I've always been vaguely aware of the existence of SIMD instructions, but it was Mitchell Hashimoto's Everyone Should Know SIMD that finally inspired me to try writing some code that uses SIMD myself.

I decided to take a straightforward problem and try making it faster using SIMD instructions: count the number of occurrences of a byte inside a text file. Since I've been using Rust for writing pretty much everything these days, that's the language I picked for this task.

I used enwik9 as my test dataset. This is a file containing a gigabyte of text from the English language Wikipedia. All benchmark numbers are from my MacBook Pro with an M4 Pro and 48GB RAM. My Rust version is 1.100.0.

Here's what the non-SIMD version of the code looks like:

fn count_bytes(haystack: &[u8], needle: u8) -> usize {
    let mut count = 0;
    for byte in haystack {
        if *byte == needle {
            count += 1;
        }
    }
    count
}

When I compiled this code with Rust's auto-vectorization turned off, it took 138.05ms to count the number of occurrences of the letter x in the test dataset. With auto-vectorization enabled—which is the default behavior—it was marginally faster at 114.55ms.

Here's the same code, this time using fearless_simd:

#[simd]
fn count_bytes_simd<S: Simd>(simd: S, haystack: &[u8], needle: u8) -> usize {
    // Broadcast the byte we're searching for into a SIMD vector
    // with the same length as the number of SIMD lanes on our
    // CPU.
    let needle_vector = S::u8s::splat(simd, needle);

	// Divide the input text into chunks. Each chunk contains the
	// the same number of elements as the number of SIMD lanes on
	// our CPU.
    let haystack_chunks = haystack.chunks_exact(S::u8s::LEN);
    
    // If the input text doesn't divide cleanly into the number of
    // SIMD lanes, hold on to the remainder so we can use it later.
    let remainder = haystack_chunks.remainder();
    
    // Let's count!
    let mut count: usize = 0;
    for chunk in haystack_chunks {
	    // Convert each chunk into a SIMD vector.
        let haystack_vector = S::u8s::from_slice(simd, chunk);
        
        // Use SIMD instructions to compare each input chunk with
        // the vector containing the byte we're looking for. This
        // comparison produces a bitmask. A `1` indicates we found
        // our byte. A `0` indicates we didn't.
        let comparison = needle_vector.simd_eq(haystack_vector);
        
        // Now all we have to do is count the number of `1`s in
        // the result of our comparison and add them to the running
        // total.
        count += comparison.to_bitmask().count_ones() as usize;
    }

	// Count the leftover bytes in the usual way.
	for byte in remainder {
        if *byte == needle {
            count += 1;
        }
    }

    count
}

This code took 30.35ms to to run on my computer. That's ~4.5 times faster than the scalar version with auto-vectorization disabled, and ~3.8 times faster than the scalar version with auto-vectorization enabled.

Pretty damn good for a few extra lines of code!

Notes on testing

To make sure my numbers were accurate, I had to make sure Rust and LLVM weren't optimizing away the very code I was trying to benchmark.

  • I made liberal use of black_box to block certain common optimizations.
  • I used [inline(never)] to prevent inlining the scalar code (black_box might have been enough to ensure this, but I was in an overly cautious mood).
  • I compiled the scalar version with no-vectorize-loops and no-vectorize-slp to disable auto-vectorization.

Bonus benchmark

I recently inherited an old ASUS TUF Dash F15 from my brother. This computer comes with an 11th generation Intel Core i5 (11300H) and 24GB RAM. It's currently running Fedora 45.

The benchmarks on this machine were a bit surprising:

  • Scalar version with auto-vectorization disabled: 240.48ms
  • Scalar version with auto-vectorization enabled: 319.96ms
  • SIMD version: 56.80ms

I don't understand why enabling auto-vectorization made the scalar version slower. I don't know enough about Rust, SIMD, Linux, benchmarking, or x86 assembly to explain this behavior. If anyone reading this understands why this happens, I would appreciate it if you could get in touch.

Code

If you want to try replicating these experiments, you can grab the code from my simd-experiment GitHub repo. You'll also have to download the test data from Matt Mahoney's website.