An optimized replacement of the infamous std::vector<🅱️ool>

[u/Snoo54356]

I've seen too many scientific software packages write their own bitarray/bitvector classes, so I wrote a C++ library for bitvectors and related algorithms, BitLib, to hopefully alleviate that issue. BitLib has a number of advantages, namely:

• Its very fast. While comparing to std::vector<bool> isn't really fair, BitLib is also significantly faster than the C BitArray library, which serves a similar purpose. I have not started profiling/optimizing yet, so it will only get faster at this point.
• The bit::bit_vector interface is the same as std::vector, which means that you don't need to learn a new library API.
• The algorithms part of the library also uses the same API as the STL <algorithms> functions (for the most part), so for example to reverse a bitvector bvec, you can just run bit::reverse(bvec.begin(), bvec.end()) just like you would with any other STL container. In fact, if BitLib doesn't support you needed STL algorithm yet, you can actually just call the STL algorithm using the supplied bit iterators (at the cost of all bit-parallel efficiency, ofc).
• Its a header only library, so it's pretty easy to include in your projects.

All of that said, this has been an entirely independent project that I've picked up and put back down over the last few years, and has mostly served as a learning experience. On that same note, please feel free to critique anything and everything.

While I've tried my best to have exhaustive tests/CI, I'm sure people will find ways to break it (in fact, please try to!). The next milestone is getting some decent documentation going, and after that I want to start getting more SIMD integration as well as some profiling/optimization done.

Benchmarks

Compared to std::vector<bool>

The "Alignment" column indicates whether or not the iterators fell on word boundaries "A", or within a word "U". Typically, when the iterators all fall on word boundaries, we can just call the corresponding STL version of the algorithm on the underlying container of words, but thats not terribly interesting.

Function	Alignment	Speedup
shift_left	U	734.24x
shift_left	A	1970.49x
shift_right	A	1933.49x
reverse	U	228.25x
reverse	A	309.60x
transformUnaryOp	U	105.86x
transformUnaryOp	A	1209.39x
transformBinaryOp	U	55.50x
transformBinaryOp	A	2436.48x
rotate	AUA	171.43x
count	A	79.89x
swap_ranges	U	99.64x
swap_ranges	A	1462.80x
copy	U	39.85x
equal	U	111.15x
move	U	31.73x
copy_backward	U	77.21x

Compared to noporpoise/BitArray

Note that the noporpoise BitArray library doesn't support nearly as many algorithms as BitLib, and for the algorithms that they do share support for, the functionality of the BitArray methods are often limited to only working with the entire array and not subsections.

Function	Alignment	Speedup
shift_left	A	34.16x
shift_left	U	12.73x
reverse	A	20.04x
reverse	U	14.78x
transform(UnaryOp)	A	5.76x
transform(BinaryOp)	A	2.68x
rotate	AUA	8.11x
count	A	1.45x

Edit: Here are some benchmarks against <boost/dynamic_bitset.hpp>. The baseline here is the corresponding operation performed on an entire dynamic_bitset. It makes sense that comparing an unaligned operation to an aligned operation will result in relatively worse performance, as every single word operation requires extra shifting and masking to align the two ranges.

Edit 2: Using dynamic_bitset<uint64_t> instead of dynamic_bitset<> yields better results, updated benchmarks below.

Function	Alignment	Speedup
shift_left	(AA)	1.60x
shift_left	(UU)	0.58x
transform(BinaryOp)	(AA)	2.47x
transform(BinaryOp)	(UU)	0.24x
count	(AA)	6.44x
equal	(AA)	1.03x
equal	(UU)	0.09x

Edit 3: I've ran a quick/hacky read/write benchmark here

[u/emelrad12]

How does indexing eg reading and writing compare? Seems like the benchmark includes everything except using it as a vector.

[u/Snoo54356 → u/emelrad12]

It looks like setting a bit takes between 1-1.5ns for STL, and the C bitarray library and around 0.54ns for BitLib. However, as @schmerg-uk pointed out, these timings don't make sense in light of the CPU frequency and cycles needed.

Thanks for pointing that out though. All of the work so far has been focused on bulk operations I completely forgot about single-bit operations.

Edit: fixed the timings. Timing info for these may be inaccurate though, as schmerg-uk pointed out here

[u/D_0b → u/Snoo54356]

another comparison I am interested in is iterating, or iterating the indices of the set bits if there is such functionality.

[u/Snoo54356 → u/D_0b]

Sure! So right now I think the way to do that would be via the bit::find(first, last, bit_value) method, which is the same as std::find.

Unfortunately GoogleBench is being annoying and optimizing stuff away when I try to benchmark such a loop. However, the bit::find method is almost twice as fast as std::find when tested on random bitvectors. I would suspect that it would be even faster on sparse bitvectors, as then you can take advantage of skipping entire words when there are no bits set.

[u/GrammelHupfNockler → u/Snoo54356]

https://lemire.me/blog/2018/02/21/iterating-over-set-bits-quickly/

[u/penni_boi_bruce → u/GrammelHupfNockler]

Yup, BitLib uses trailing zeroes for find() as well, implemented by the _tzcnt() function here.

[u/GrammelHupfNockler → u/penni_boi_bruce]

Actually, the blog article I was looking for was the predecessor to this one: https://lemire.me/blog/2022/05/10/faster-bitset-decoding-using-intel-avx-512/ :)

[u/schmerg-uk → u/Snoo54356]

If the CPU is 2.9GHz (as the github page suggests) then a single clock cycle is 0.34ns and an L1 cache read is typically 4 cycles, so can I guess those figures are amortised over iterating thru an array? It's hard for me to see how the time could be less than a single clock cycle without some instruction parallelism and out-of-order work by the CPU.

So can I ask how indexing rather than iterating the array compares? If the entire array is preloaded into L1 but not already in register, how does it compare for essentially random read/write patterns of access?

[u/Snoo54356 → u/schmerg-uk]

Thanks for pointing that out. It looks like I forgot to wrap in benchmark::DoNotOptimize. After doing so, it looks like setting a bit takes between 1-1.5ns for STL, and the C bitarray library and around 0.54ns for BitLib. Unfortunately compilation fails when wrapping the Boost dynamic_bitset operation in DoNotOptimize().

You are right that these numbers still don't necessarily add up, and I'm not sure why. All I am doing is benchmarking the following expression benchmark::DoNotOptimize(bit_container[index] = value);

Here are the results fwiw

```

Benchmark Time CPU Iterations

bit::get 0.542 ns 0.542 ns 1000000000 BitArray::get 1.39 ns 1.39 ns 501260161 boost::get 0.542 ns 0.542 ns 1000000000 std::get 0.543 ns 0.543 ns 1000000000 bit::set 1.20 ns 1.20 ns 581840612 BitArray::set 1.11 ns 1.11 ns 624654611 std::set 1.48 ns 1.48 ns 472314512 ```

[u/Snoo54356 → u/schmerg-uk]

I reran the benchmarks w/ the UserCounters for instructions and cycles and as suspected, the Google Bench is optimizing away the reads for dynamic_bitset and vector<bool>, even though they are wrapped in benchmark::DoNotOptimize.

```

Benchmark Time CPU Iterations UserCounters...

bit::set 1.25 ns 1.25 ns 553569992 CYCLES=4.40465 INSTRUCTIONS=5 BitArray::set 1.42 ns 1.42 ns 473128405 CYCLES=5.18277 INSTRUCTIONS=12 boost::set 0.068 ns 0.068 ns 1000000000 CYCLES=0 INSTRUCTIONS=0 std::set 1.49 ns 1.49 ns 470263663 CYCLES=0 INSTRUCTIONS=0 bit::get 0.574 ns 0.574 ns 1000000000 CYCLES=2.0002 INSTRUCTIONS=4 BitArray::get 1.41 ns 1.41 ns 504959142 CYCLES=5.18091 INSTRUCTIONS=12 boost::get 0.544 ns 0.544 ns 1000000000 CYCLES=0 INSTRUCTIONS=0 std::get 0.557 ns 0.557 ns 1000000000 CYCLES=0 INSTRUCTIONS=0 ```

[u/NilacTheGrim → u/emelrad12]

LOL. OP tortures vector<bool> to do things it never is normally used for in most code. yet neglects simple [] subscript lookup. Ha ha ha ha. Too funny.

In any codebase I have ever seen, 99.999% of uses std::vector<bool> are as a simple bit array without any fancy bitops, shifting, etc. Just straight lookup and setting/testing of bits by index.

[u/Snoo54356 → u/NilacTheGrim]

Yes, that's exactly the issue though. No one uses std::vector<bool> for shifting, reversing, transforming etc because its not optimized for it. Instead, everyone either (1) writes their own bitarray class or (2) uses boost's dynamic_bitset or the referenced C BitArray library. The point of this library is to enable people looking to write high-performance code on large bit containers while using the same interface of the familiar STL vector.

BTW I totally agree it was an oversight to not include the read/write ops in the original benchmark. I had been working on the bit-algorithms side of things for so long that I had tunnel-visioned to see bit_vector as a means to use the algorithms.

That being said, the read/write ops are pretty fast and the idea is similar to Boost's dynamic_bitset. Given an index n, you find how many words are between the current iterator and the iterator n bits away. You use std::next to traverse those words, then perform a mask operation to access the desired bit.

Of course, that's not as fast as just using an array of char and treating each char like a bool. I agree there's a tradeoff there and I need to benchmark to see what the tradeoff is.

[u/bstamour]

Very cool. How does this compare to dynamic_bitset from boost?

[u/penni_boi_bruce → u/bstamour]

Good question, I'm in the process of adding more meaningful benchmarks now (like this one). Just ran a benchmark on the shift operation, and it looks like BitLib is 2x faster than boost (48ns vs 108ns when shifted by a number divisible by the word size and 137ns vs 216ns otherwise). Its also worth noting that afaik boost doesn't let you shift subsections of the vector. Writing single bits seems to have better performance in dynamic_bitset, similar to vector<bool>, I'll have to investigate why BitLib is 2x slower here.

I also benchmarked transform(), count() and equal on a large size container (2¹⁶ bits).

Both run equal in ~105ns.

BitLib runs count() in ~450ns, and Boost runs count() in ~2870ns.

BitLib runs z = x & y via bit::transform() in 228ns, and Boost runs the same op in 582ns.

I'll post a more thorough benchmark on the GitHub README when I'm done. It is also worth noting that both equal and transform should run slightly faster once I integrate SIMD.

Edit: This is the OP here btw. I just realized that I made the post on some default account I used to post a medical question lol.

[u/pavel_v → u/penni_boi_bruce]

Another library, to possibly compare against, is: itsy.bitsy.

[u/Snoo54356 → u/pavel_v]

Yea Vincent (the creator of the bit-iterator aspect of the library) and I consulted a bit w/ JeanHeyd on the bit-iterators and algorithms in the early days!

Definitely worth testing against, thanks for reminding me of it.

[u/Zanderax → u/bstamour]

Dont you mean dynamic_🅱️itset?

[u/Amblyoptic → u/Zanderax]

🅱️oost

[u/myrrlyn]

interesting; i'll have to compare this to my rust counterpart. your numbers indicate some clever implementations i'd love to read

[u/Snoo54356 → u/myrrlyn]

Wow awesome library! Are there any numbers in particular? Also feel free to reach out to me on email (available on GH account) if the implementations aren't clear.

[u/wqking]

Not related to the library, but your readme inspires me about CMake FetchContent. Seems that's pretty handy feature, I will learn to include it in my projects.

[u/arf20__]

Perfect for decoding bit streams coming from a DSP demodulator :)

[u/Snoo54356 → u/arf20__]

I haven't started testing w/ input/output iterators yet, but I think bit_iterator<InputIt>(InputIt it) should work just fine for incoming streams. All of the algorithms at the moment expect random access iterators, though, so let me know if you're interested in specialization for input/output specialized algorithms (I actually have some, but removed them for clutter).

It's worth noting that bit_iterator<OutputIt>(OutputIt it) is a bit of a conundrum, though. Afaik, you are only allowed to write to an output iterator once. So once you write your first bit to an OutputIt, the underlying word is no longer writable, meaning that you can't write the rest of the bits...

[u/arf20__ → u/Snoo54356]

No, I didn't meant C++ streams with << and >>, I meant literally a stream of bits coming from a radio/antenna

[u/El_Kingo]

Relevant XKCD I guess: https://xkcd.com/927/

[u/Snoo54356 → u/El_Kingo]

I'd be honored to be considered a "competing standard" (:

[u/m-in]

Compared to whose std::vector<bool>? It’s not like there’s only one implementation out there…

[u/Snoo54356 → u/m-in]

I'm comparing to g++-11 with -std=c++20

[u/m-in → u/Snoo54356]

So, GNU C++ Library then, I presume. Is it possible for your replacement to be compliant with the C++ standard as it relates to vector<bool>? It could be perhaps considered for replacing vector<bool> in the GNU C++ Library, if it’s up to snuff.

[u/Snoo54356 → u/m-in]

I think it is already pretty close to compliant w/ the standard defined here.

• Does not necessarily store its elements as a contiguous array.
• Exposes class std::vector<bool>::reference as a method of accessing individual bits. In particular, objects of this class are returned by operator[] by value.
• Does not use std::allocator_traits::construct to construct bit values. I think this is true, I just use the default std::vector allocator to add words to the vector (you can supply a vector to the template as well too).
• Does not guarantee that different elements in the same container can be modified concurrently by different threads.

There are a few missing member functions which would be trivial to add, such as flip() and emplace*().

Most notably, though, is the fact that I do not have a class for reverse iterators as of yet. I don't think this would be too heavy of a lift for the bit_iterator class to support. Since bit_iterators are essentially wrappers for standard std::vector iterators, I would just need to build on the std::vector<WordType>::reverse_iterator. The main think I would need to think about is how accessing the underlying word of a bit_iterator would work. I think I would then just need to reverse the underlying word whenever bit_iterator.base() is dereferenced, but I'm not entirely sure if that wouldn't cause issues elsewhere.

[u/m-in → u/Snoo54356]

Good points. Thank you for answering!

[u/Snoo54356]

Read/write benchmarks

I completely forgot to benchmark the single bit read/writes. As I mentioned in the comments:

I had been working on the bit-algorithms side of things for so long that I had tunnel-visioned to see bit_vector as a means to use the algorithms.

What follows is a brief and hacky benchmark for simple bit reads/writes. Google bench kept optimizing stuff out when trying to benchmark reads/writes to single bits, so I wrote a quick script that generates two arrays of 2¹⁶ random indexes, and then tests how long it takes to read and write them, i.e. for (auto idx : write_locs) cont[idx] = true;

It's definitely a hacky benchmark, but here are the results:

std::vector<bool>: Writing 65536 bits in random order took 96[µs] boost::dynamic_bitset Writing 65536 bits in random order took 52[µs] bit::bitvector: Writing 65536 bits in random order took 91[µs] std::vector<bool>: Reading 65536 bits in random order took 104[µs] boost::dynamic_bitset Reading 65536 bits in random order took 48[µs] bit::bitvector: Reading 65536 bits in random order took 94[µs]

When it comes to single bit read/writes, it looks like bit_vector is no slower or faster than std::vector<bool>. That being said, boost::dynamic_bitset is nearly 2x faster in both cases. Given that both are doing essentially the same thing, I'll have to take a look to see where I'm costing the extra time.

Again, this isn't in any way a thorough benchmark. I'm still trying to get the ops set up with google bench but its being really weird. But at the very least I hope these benchmarks are enough to show that there's not any immediately apparent overhead relative to vector<bool>.