I have a BitSet<usize> in my simulation program which I need to select a uniform random value from:

fn random_element(set: &BitSet<usize>) -> Option<usize> {
    set.iter().choose(rng)
}

However, BitSet::iter() does not provide an O(1) implementation of nth(), so this is somewhat slow. I have evidence from profiling that this operation is a bottleneck for my program. My bitset almost always fits into a single usize (around 98% of the time, to be specific). I'm using the fastrand - Rust crate as a random number generator and it looks like number generation is not the bottleneck here.

I'm wondering if there's a crate or approach out there I could use for a faster implementation of this. I'm targeting x86_64 and aarch64 here, and I'm particularly interested in crates that utilize tools like the BMI2 instructions on newer Intel chips to implement this kind of operation very efficiently, or e.g. using something like the __popcnt intrinsic to narrow down which byte to search.

6 posts - 3 participants

Read full topic