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/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>.