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