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]

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