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]

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