Am I using Rust's bitvec_simd in the most efficient way?

Question

I'm using bitvec_simd = "0.20" for bitvector operations in rust.

I have two instances of a struct, call them clique_into and clique_from. The relevant fields of the struct are two bitvectors members_bv and neighbors_bv, as well as a vector of integers which is called members. The members_bv and members vector represent the same data.

After profiling my code, I find that this is my bottleneck (in here 41% of the time): checking whether the members (typically 1) of clique_from are all neighbors of clique_into.

My current approach is to loop through the members of clique_from (typically 1) and check each one in turn to see if it's a neighbor of clique_into.

Here's my code:

use bitvec_simd::BitVec;
use smallvec::{smallvec, SmallVec};

struct Clique {
  members_bv: BitVec,
  members: SmallVec<[usize; 256]>,
  neighbors_bv: BitVec,
}

fn are_cliques_mergable(clique_into: &Clique, clique_from: &Clique) -> bool {
  for i in 0..clique_from.members.len() {
    if !clique_into.neighbors_bv.get_unchecked(clique_from.members[i]) {
      return false;
    }
  }
  return true;
}

That code works fine and it's fast, but is there a way to make it faster? We can assume that clique_from almost always has a single member so the inner for loop is almost always executed once.

It likely comes down to this:

if !clique_into.neighbors_bv.get_unchecked(clique_from.members[i])

Is get_unchecked() the fastest way to do this? While I have written this so it will never panic, the compiler doesn't know that. Does this force Rust to waste time checking if it should panic?

Answer 1

You are attempting to test if two sets are disjoint or not. The fastest way to do this is to and together two bit vectors to form the intersection and test is_empty on the generated set.

To accomplish this, you will need to store data in sets of equal size.