This is probably faster than the current implementation: https://lemire.me/blog/2018/02/21/iterating-over-set-bits-quickly/

Hello, i would like to implement a function which would yield me the offset of the first unset bit. Something like find_first_unset_bit(&self) -> Option<usize>. I thought about making it more generic (giving it a binary value for which to search, but then i think it will end up as two different functions under the hood, because you want to test entire blocks with an if statement at the beginning -- something like

// we are searching for the first unset bit
for block in &self.data {
    if block != BLOCK::max_value() {
        // find exact id here
    }
}

in order to search for first set bit you'd need to change the value you are comparing block against to 0. I also thought that maybe this function could take a Range and try to find the first bit that is set/unset within the given range.

Simple example for the version without range/custom bit value:

let mut fb = FixedBitSet::with_capacity(30);
for i in 0..20 {
    fb.insert(i);
}
let next = fb.find_first_unset_bit();
assert_eq!(next, Some(20));

As the title says. It would be nice to have bit shift operations, so <<, >>, and >>>.

Having an iterator over the bits that are set to 1 (or 0) would be a nice addition. For example, it would speed up this loop of my Kuhn-Munkres implementation. I could implement it myself by using the as_slice() method, but this would make assumptions about the order in which bits are stored in the u32. This can be efficiently implemented using bsf (bit-scan-forward x86) or equivalent operations.

I have implemented function: fn count_ones_to_offset(&self, offset: usize) -> usize. I would like to add it to this crate, but when I asked @bluss about it, he suggested that maybe this function should take Range as argument. Example usage below:

    let mut fb = FixedBitSet::with_capacity(15);
    fb.set(11, true);
    fb.set(7, true);
    assert_eq!(fb.count_ones_to_offset(6), 0);
    assert_eq!(fb.count_ones_to_offset(7), 1);
    assert_eq!(fb.count_ones_to_offset(11), 2);

There's currently multiple open PRs ranging from 2016 to midway through this year that have remained unmerged, and multiple issues in the same timescale without any response.

Is it possible to expand the maintainer group of this library? There are many operations that could be optimized for, benchmarks to expand coverage, etc.

This crate currently has 33 million all time downloads on crates.io, nearly 2x the next competitor in this niche, and is being actively used in multiple high profile projects like petgraph and bevy_ecs. It'd be a shame to need to fork this library to provide the Rust ecosystem with these improvements.

To get a quick overview of the contents of a set, it would be nice to be able to get a binary display of the set.
The Binary trait seems perfect for this.

Allows syntax like received[id] = true;

Maybe I'm misunderstanding something, but it looks like it's currently not possible to write code like this:

let mut left: FixedBitSet = ...
let right: &FixedBitSet = ...
left &= right;

Instead you need to use the equivalent but more verbose

left.intersect_with(right)

To me it looks like the BitAndAssign and related implementations take the RHS by value for no reason.

I think this can be fixed in a backwards compatible manner by adding new implementations like this:

impl <'a> BitAndAssign<Rhs = &Self> for FixedBitSet { ... }

Would a pull request for this be accepted?

FixedBitSet's BitOr implementation requires copying the underlying data, since it returns a new FixedBitSet (see https://play.rust-lang.org/?gist=0b8e747fc39a65088ac2403e387dde2e&version=stable&mode=release&edition=2015 for demonstration of copy -- FixedBitSet::bitor doesn't get inlined, so the copy certainly isn't getting optimized away) Seems like it would be nice to have a union_with(&mut self, rhs: &FixedBitSet) function that could do this operation without copying.

From Future Work of #1525.

Are there features fixedbitset would benefit from but cannot use without bumping the minimum rust version?

Hi,

I'm building a tiny abstraction over this lib for my use case (a set of usizes with an API very similar to BTreeSet) and I'm stuck on the implementation of my IntoIterator because there is no owning equivalent of ones(). I mean, One<'a> iterates over a borrow of the FixedBitSet and I cannot easily keep the FixedBitSet and the One<'_> around on the same struct:

struct IntoIter<'a> {
    bit_set: FixedBitSet,
    ones: Ones<'a>,
}

I'm currently using rental as a workaround, but that is quite complex.

Does it make sense to implement a method like pub fn into_ones(&self) -> IntoOnes? I can work on a PR if you are interested.

Best regards,

Hello,

Thanks a lot for the awesome lib 👍

I've observed that PartialEq is derived automatically. But that means that sets with different capacities are always considered different, even when having the same "elements" (in the sense of the values obtained with ones()).

let a = FixedBitSet::with_capacity(0);
let b = FixedBitSet::with_capacity(1);

assert_ne!(a, b); // both are "empty", but considered different

Wouldn't it be better to consider sets that return the same values when iterated over with ones() as equal, regardless of their internal capacities? That would be more in line with how the standard library works, for Vec and other data structures.

This could arguably be a breaking change though, not sure the maintainers would be ok with this.

I'll be glad to work on a PR for this change if well received.

Best regards,

A good chunk of the platforms Rust works on supports SIMD instructions (see: core::arch's docs), this includes bitwise AND/OR/NOT operations for 128/256/512 bit types. It'd be great if operations across FixedBitSet's used platform specific implementations to allow for faster operations. This adds a few bytes of overhead due to blocks being bigger, however.

Alternatively, simply using usize internally over u32 might also speed up operations by using the widest supported integral type (barring SIMD types).

The documentation for struct fixedbitset::Zeroes is the same as for struct fixedbitset::Ones.
I think this should be changed to talk about "unset" bits and reference the method FixedBitSet::zeroes instead of FixedBitSet::ones

Apache-2.0 requires text license to be presented along with sources.

Mentioned by @maniwani in

bevyengine/bevy#6587 (comment)

Hi,

I'm a newcomer to Rust, who just tried to use your crate in my Conway's Game of Life learning project, as recommended in the "Rust and WebAssembly" book. And although it went mostly fine, I had a hard time understanding what some of the functions do or what kind of arguments they take.

Because of it being recommended in the aforementioned book one can expect more newcomers like me to stumble over your crate, that is why I think it would be very appropriate to update the documentation to be more accessible.

One particular example is the FixedBitSet::with_capacity_and_blocks function. As far as I understand, I give it a length and some data from which it creates a FixedBitSet. That data must implement the IntoIterator trait for u32. Vec<u32> should do that right? So I tried it like this:

let data = vec![
    0, 1, 0, 0, 1,
    1, 0, 0, 0, 0,
    1, 0, 0, 0, 1,
    1, 1, 1, 1, 0,
];

let cells = FixedBitSet::with_capacity_and_blocks(20, data);

Compiler gives no errors, but cells only contains zeros, not to mention the wasted space by representing bit-sized values as u32 if this would work. So do the Integers have to take some other representation? Unfortunately the documentation doesn't say anything about that.

A better API documentation would help here a lot, especially some examples. I would even do it myself if you want me to (And if you give me a hint on how to solve that issue I had ;-P ). There's also some other places where some examples would make it more clear what the code does.

I got this error " self.cells.as_slice().as_ptr()
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected *const u32, found *const usize" when wasm-pack build using fixedbitset="0.5.1" .But when I change to "0.1.9" the compilation is successful. why is this happening and how to use the latest version?

I'm new to FixedBitSet, but what is the most idiomatic way to disable a bit?

I'm looking for a simple method like HashSet::remove().

Do I have to use FixedBitSet::set(i, false)? (Is there any technical reason why remove() is not implemented?)

There are eight new commits since last release. Thanks in advance.

There are options like core::arch::is_x86_feature_detected which can detect which instruction sets are available. Unfortunately the checks cannot be done inside each function call due to the cost of feature detection.

One potential way around this is to do feature detection during initialization, and use a tagged pointer to store the features detected. As any SIMD-supporting platform is at least 32-bit wide, there are at least two bits at the bottom of every pointer to a backing allocation that are always zero. If the default block size is increased to 8 to 64 bytes, the number of tag bits increases. An example mapping for x86 may include:

• 00 - Default, none detected.
• 01 - SSE2 detected
• 10 - SSE4.1 detected
• 11 - AVX detected

These bits can then be zeroed out on access in a branchless way, which should have a slight impact negative performance impact to point queries (contains, insert, etc.), but allow for the most performant instructions to be used without explicitly compiling for a particular target feature set.

To use it as a drop-in replacement for HashSet, it would be nice to make FixedBitSet generic over its "index", i.e. FixedBitSet<K = usize> where K: From<usize> + Into<usize> (à la typed-index-collections).
So when you have e.g. a custom wrapper type MyId(u32) which is a HashSet<MyId>, and you know the collection is mainly dense (not too many holes), you could very easily switch to FixedBitSet<MyId> without changing anything else in the code.

I'm implementing iterator over unset bits, but i noticed that benches for ones are significantly worse after they are moved to the separate file. Take a look:

$  git checkout e92c5eca22b62b0eb36b721a9b11739b83390cfd
$ cargo bench --features=unstable
test bench::bench_iter_ones_all_ones                      ... bench:   1,095,463 ns/iter (+/- 92,484)
test bench::bench_iter_ones_all_zeros                     ... bench:      29,367 ns/iter (+/- 1,309)
test bench::bench_iter_ones_using_contains_all_ones       ... bench:     940,732 ns/iter (+/- 38,425)
test bench::bench_iter_ones_using_contains_all_zeros      ... bench:     784,732 ns/iter (+/- 50,771)
test bench::bench_iter_ones_using_slice_directly_all_ones ... bench:     696,833 ns/iter (+/- 123,018)
test bench::bench_iter_ones_using_slice_directly_all_zero ... bench:      30,110 ns/iter (+/- 10,471)

$ git checkout 51c1e7414ecfc21f6f81968ef2cd11b16d059dc8
$ cargo bench
test bench_iter_ones_all_ones                      ... bench:   3,419,658 ns/iter (+/- 665,823)
test bench_iter_ones_all_zeros                     ... bench:      63,210 ns/iter (+/- 4,960)
test bench_iter_ones_using_contains_all_ones       ... bench:     950,322 ns/iter (+/- 49,482)
test bench_iter_ones_using_contains_all_zeros      ... bench:     822,978 ns/iter (+/- 109,732)
test bench_iter_ones_using_slice_directly_all_ones ... bench:     773,788 ns/iter (+/- 207,150)
test bench_iter_ones_using_slice_directly_all_zero ... bench:      38,948 ns/iter (+/- 2,617)

It looks as if something is not getting inlined ? Notably, even if benches are in the same file on my machine bench for ones is significantly worse than using slice directly. Can you comment on that @mneumann ?

My setup is rustc 1.15.0-nightly (daf8c1dfc 2016-12-05), running on Intel Core i5-3320M CPU @ 3.3GHz. I can provide benches for a machine with Intel Xeon inside if need be.

Potential performance optimization for a pattern like this:

if !received[id] {
  received[id] = true;
  // Do other stuff
}

// Could be this instead
if !received.set(id, true) {
  // Do other stuff
}

It would need some benchmarking to make sure the bounds checking and division is actually slow enough to warrant a memory read on every set call.

How about a FixedBitSet that uses static size, array representation and provides Copy trait? Like the standard library, it could probably be limited in the sizes it would support, but up to ~256 bits or so could be pretty useful for a lot of use cases.

cc @jrraymond

Hi! While scraping tarballs from crates.io I've found the following releases to be missing tags:

• 0.5.6 commit: a3b708b
• 0.5.5 commit: c69f0ff
• 0.5.4 commit: 70b7a1f
• 0.5.3 commit: 0dbd45a
• 0.4.2 commit: da287ee
• 0.4.1 commit: 72bd94d
• 0.4.0 commit: 5ae6d8c

Could the tags for at least recent versions be recouped? The commit ids I've put in the list are from the .cargo_vcs_info.json file

FixedBitSet::into_ones transmutes between Vec with different alignment requirements, which is then UB to drop.

MIRI also reports undefined behaviour in this example:

use fixedbitset::FixedBitSet;

fn main() {
    let mut bitset = FixedBitSet::new();
    bitset.grow(32);
    let iter = bitset.into_ones();
    drop(iter);
}

error: Undefined Behavior: incorrect layout on deallocation: alloc1776 has size 64 and alignment 16, but gave size 64 and alignment 8
   --> E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\alloc.rs:119:14
    |
119 |     unsafe { __rust_dealloc(ptr, layout.size(), layout.align()) }
    |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ incorrect layout on deallocation: alloc1776 has size 64 and alignment 16, but gave size 64 and alignment 8
    |
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: BACKTRACE:
    = note: inside `std::alloc::dealloc` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\alloc.rs:119:14: 119:64
    = note: inside `<std::alloc::Global as std::alloc::Allocator>::deallocate` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\alloc.rs:256:22: 256:51
    = note: inside `<alloc::raw_vec::RawVec<usize> as std::ops::Drop>::drop` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\raw_vec.rs:555:22: 555:56
    = note: inside `std::ptr::drop_in_place::<alloc::raw_vec::RawVec<usize>> - shim(Some(alloc::raw_vec::RawVec<usize>))` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ptr\mod.rs:515:1: 515:56
    = note: inside `<<std::vec::IntoIter<T, A> as std::ops::Drop>::drop::DropGuard<'_, usize, std::alloc::Global> as std::ops::Drop>::drop` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\vec\into_iter.rs:436:94: 436:95
    = note: inside `std::ptr::drop_in_place::<<std::vec::IntoIter<T, A> as std::ops::Drop>::drop::DropGuard<'_, usize, std::alloc::Global>> - shim(Some(<std::vec::IntoIter<T, A> as std::ops::Drop>::drop::DropGuard<'_, usize, std::alloc::Global>))` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ptr\mod.rs:515:1: 515:56
    = note: inside `<std::vec::IntoIter<usize> as std::ops::Drop>::drop` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\vec\into_iter.rs:447:5: 447:6
    = note: inside `std::ptr::drop_in_place::<std::vec::IntoIter<usize>> - shim(Some(std::vec::IntoIter<usize>))` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ptr\mod.rs:515:1: 515:56
    = note: inside `std::ptr::drop_in_place::<fixedbitset::IntoOnes> - shim(Some(fixedbitset::IntoOnes))` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ptr\mod.rs:515:1: 515:56
    = note: inside `std::mem::drop::<fixedbitset::IntoOnes>` at E:\Programmi\Rust\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\mem\mod.rs:992:24: 992:25
note: inside `main`
   --> src\main.rs:7:5
    |
7   |     drop(iter);
    |     ^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to 1 previous error

I don't know what part of this implementation is "Fixed" since it seems like the bitsets can grow at will and is implemented using a Vec.

It would be cool to instead have the size be known at compile time which would allow allocation-less bitsets:

type Block = usize;
pub struct CTFixedBitSet<const BLOCKS: usize> {
    pub blocks: [Block; BLOCKS],
    pub length: usize,
}

While this would make the Api dependant on blocks instead of the number of bits which might be confusing to a new user, I feel like it could improve performance. Perhaps a macro could be used to calculate the value based on bits? Don't know if that's possible without a proc-macro though.

let mut my_bitset = bitset!(128); // Would create a CTFixedBitSet<4> on 32-bit platforms and CTFixedBitSet<2> on 64-bit if Block is usize

I think a bit iterator that returns true and false for each bit correspondingly would be a nice addition to this library. I was in need of one which is why I already personally implemented it, though I am not sure about its performance.

The use case I have for it for example, is that one could zip this iterator with an iterator over a Vec and filter out all elements where the corresponding bit is unset for example.

Compiling fixedbitset v0.0.2
...
fixedbitset-0.0.2\src\lib.rs:34:24: 34:42 error: use of unstable library feature 'collections'
fixedbitset-0.0.2\src\lib.rs:97:56: 97:56 help: add #![feature(collections)] to the crate attributes to enable

Saw this when compiling petgraph, giving you a heads up!

Detailed here: https://lemire.me/blog/2018/03/08/iterating-over-set-bits-quickly-simd-edition/

This can be significantly faster on denser bitsets, and should be easy enough to implement given that the backing blocks are now stored in SIMD-compatible blocks.

I would be nice if this library support rotate_left and rotate_right, just liked the standard library.

When trying to create a fixedbitset with invalid parameters, here is the error message and stack trace that is generated :

explanation = '''
Panic occurred in file '/home/[...]/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/macros.rs' at line 13
'''
cause = 'assertion failed: start <= end && end <= length'
method = 'Panic'
backtrace = '''

   0: 0x5638b4ce3be5 - tokio::runtime::enter::exit::hba90552f0bd4dfed
   1: 0x5638b4cfb0d9 - tokio::task::blocking::block_in_place::h0a384439c8a047e1
   2: 0x5638b4d0cc52 - <core::future::from_generator::GenFuture<T> as core::future::future::Future>::poll::h3fe07ad1656c20e0
   3: 0x5638b4ce8984 - <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h134d72015faf04e0
   4: 0x5638b4cd7b5f - tokio::runtime::task::harness::Harness<T,S>::poll::hcf7a7f0209ef9099
   5: 0x5638b5079d46 - std::thread::local::LocalKey<T>::with::hed4303faf3e1aed8
   6: 0x5638b506bb22 - tokio::runtime::thread_pool::worker::Context::run_task::hce41c119710e9437
   7: 0x5638b506b21e - tokio::runtime::thread_pool::worker::Context::run::h56ab1c1f681d7b07
   8: 0x5638b5076ad3 - tokio::macros::scoped_tls::ScopedKey<T>::set::hdf577aceeef82d4c
   9: 0x5638b506ad1b - tokio::runtime::thread_pool::worker::run::h961448ba1e9ff7ff
  10: 0x5638b4d17247 - tokio::loom::std::unsafe_cell::UnsafeCell<T>::with_mut::h57e15455d5038c88
  11: 0x5638b4ce9359 - <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::hec30f88dbe1bed0a
  12: 0x5638b4cd6806 - tokio::runtime::task::harness::Harness<T,S>::poll::h1a26a8b5f39df086
  13: 0x5638b506d5b7 - tokio::runtime::blocking::pool::Inner::run::h937eb2b632dbdb7b
  14: 0x5638b5071ce8 - tokio::runtime::context::enter::h29b8ab9636afe6c1
  15: 0x5638b506eb8f - std::sys_common::backtrace::__rust_begin_short_backtrace::h4a06a10cbf72246d
  16: 0x5638b507c192 - core::ops::function::FnOnce::call_once{{vtable.shim}}::hef5eaf9a4d249daf
  17: 0x5638b51fbe6a - <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once::hf311c88f1fadb9b8
                at /rustc/d3fb005a39e62501b8b0b356166e515ae24e2e54/src/liballoc/boxed.rs:1076
                 - <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once::h8cfb7235b81393ef
                at /rustc/d3fb005a39e62501b8b0b356166e515ae24e2e54/src/liballoc/boxed.rs:1076
                 - std::sys::unix::thread::Thread::new::thread_start::hf745c8cf29a89648
                at /rustc/d3fb005a39e62501b8b0b356166e515ae24e2e54/src/libstd/sys/unix/thread.rs:87
  18: 0x7fe9d53fc609 - start_thread
  19: 0x7fe9d553e103 - clone
  20:        0x0 - <unresolved>'''

This doesn't even mention that the error comes from fixedbitset, or give any useful information that may help with debugging the issue.

Something that would help a lot would be to always use the second argument of assert! to give useful information about the assertion.

Can fixedbitset support serialization/deserialization using Serde?

"Eq" is true only if the number of bits in the underlying representation is the same. Comparing a bitset against
FixedBitSet::new() is not necessarily true for the empty set.

1. fixedbitset could be allocation free for small block counts (store blocks in a SmallVec)
2. fixedbitset could have a const constructor

From Bevy's ECS rework notes. Figured I'd pass the thoughts on here in case there's appetite to improve this.

Minimal reproducing example (runnable version):

let v = fixedbitset::FixedBitSet::with_capacity(512usize);
println!("{}", v.count_ones(..));

Expected behavior: Print 0
Actual behavior: panic:

~/workspace/mincounter_fixedbitset$ RUST_BACKTRACE=1 cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/mincounter_fixedbitset`
thread 'main' panicked at 'index out of bounds: the len is 16 but the index is 16', /checkout/src/libcollections/vec.rs:1401
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: <collections::vec::Vec<T> as core::ops::Index<usize>>::index
             at /checkout/src/libcollections/vec.rs:1401
   1: fixedbitset::FixedBitSet::count_ones
             at .../.cargo/registry/src/github.com-1ecc6299db9ec823/fixedbitset-0.1.5/src/lib.rs:168

As far as I can see, I already use the newest version.

I need to create a bitset of known size with all bits set. Currently I do it with:

fn ones_with_capacity(bits: usize) -> FixedBitSet {
    let mut everything = FixedBitSet::with_capacity(bits);
    everything.set_range(.., true);
    everything
}

This is not hard to write, but unlike Vec::with_capacity(), FixedBitSet::with_capacity() initializes the bitset to zeros, only for my code to immediately set it to ones. With largish bitsets I'd like to avoid the unnecessary initial resetting. Looking at assembly output in release mode, it seems that the compiler doesn't inline with_capacity(), from which I infer that it cannot eliminate the initial zeroing.

The question is, what is the most efficient way to create an all-ones bitset? Is it the above code, or rather something like:

fn ones_with_capacity(bits: usize) -> FixedBitSet {
    FixedBitSet::with_capacity_and_blocks(bits, std::iter::repeat(!0))
}

And should the crate include a constructor like FixedBitSet::ones_with_capacity() (possibly with a more optimized implementation)?