How to use bit vector efficiently

Recently I came across yet another "micro benchmark" and I wanted to participate by submitting my rust solution. The goal is to produce the most amount of primes in the same time.

C++ solution

My Rust solution (requires bitvec 0.22.1)

In my machine my Rust code runs twice as slow, just wondering where I am losing in the optimization game. I'm having issues with my machine in setting up perf currently so I can't provide the flamegraph yet.


Test environment:
C++: g++ -O3, v: 10.2.0
Rust: cargo build --release, v 1.51


Source: E00: Software Drag Racing: C++ vs C# vs Python - Which Will Win? - YouTube (Check description for the git repo)


Flamegraph: Imgur

For benchmarks, check out criterion. It's more accurate than using Instant.

At a glance, I'd say you likely have one of two problems: bounds checking or compilation mode. Frost, make sure you're running `cargo run --release, then see if the performance improves when you use slice.get_unchecked() instead of slice.get(). If that fixes it, you will need to provide more information to the compiler, so it knows in advance that all array access are valid. Sometimes you can do this with an assert, and sometimes you need to convert your code to iterate directly over the elements of the slice instead of iterating over indexes.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.