It is finally time.

After 3 months and quite a bit of hard work, I have finally finished the Google Summer of Code program. In it, I have created an enhanced and improved implementation of P0237 and N2050 from scratch. In my original proposal to get the Summer of Code work-study, I stated that I would implement a range-based bit_view, a container adaptor version of dynamic_bitset, all of the bit_iterator/bit_reference/bit_value types, and more.

Let’s go through the checklist of each phase and what we managed to implement and work on:

Phase 1 - bit_iterator, bit_reference, bit_value and bit_view

✔️ 🏆 🎉 - Absolutely covered, with all stretch goals and even MORE met!

This was spoken about much, much earlier. We had both dynamic_bitset<C> and bit_view<R> covered, which pulled in an implementation of bit_iterator, bit_reference, and bit_value. Unfortunately, during this time we also had bit_span, which was a bad name for a type. The original idea was having a mutable versus immutable split for each container in separate types. That was a mistake and it was far better to just let the const-ness of the range or container flow naturally into the class’s interface and compile-time prevent things. There’s still a bit_span in the final product, but it’s just an alias for template <typename T> using bit_span = bit_view<span<T>>;.

The only other change here is that our bit_reference type is a bit more involved, taking a ReferenceType and a MaskType rather than just the default bit_reference<T> of the original proposal. This allows for a greater degree of control over how the reference shakes out, including potential uses for std::reference<> types being used in bit_reference successfully. (Currently, this scenario is not tested, but we do allow for a top-level bit_view<std::reference<std::vector>> behavior!)

Phase 2 - Iterator Improvements and Algorithms

✔️ 🏆 - Everything, plus most of the stretch goals.

This was covered by 2 previous articles, here and here. I won’t recap absolutely everything, but it was a bit of a struggle getting most of the iterator constraints perfectly okay.

We also added some serious utilities here that cover some of the use cases first brought up after completion of the first phase. Jonathan Müller mentioned that he had some use cases for directly working with a potentially disjoint set of bits. The tiny/bit_view class in his library does that. I added support for creating a view of a set of bits that could target precisely bits [x, y) by using the Bounds class portion of the new bit_view<Range, Bounds>:

// 0xFBFF = (MSB) 0b‭1111101111111111‬ (LSB)
std::vector<std::uint32_t> storage{ 0x0000FBFF, 0xFFFFFFFF };
using Rng = std::span<std::uint32_t>;
bitsy::bit_view<Rng, bitsy::bit_bounds<10, 22>> truncated_view_bits(, storage.size()
assert(truncated_view_bits.size() == 12);
// 0th bit of biew is 10th bit,
// 10th bit of 0xFBFF is false
assert(truncated_view_bits[0] == bitsy::bit0);

Most people would wonder why I didn’t take the stance of using a number directly like when they made std::span<T, N>. I believe taking a class template parameter is far more flexible than span’s single numeric bound value. It also allows for taking a bitsy::dynamic_bit_bounds type as well, whose size can be calculated entirely at runtime. The default is a bitsy::word_bit_bounds, which simply spans from 0 to the size of the container (which is, e.g., the bounds encompassing the words of the range). This was a severe improvement to the API that resulted in covering a much broader selection of use cases while still retaining the same abstraction powers.

It is also important to pass in 2 numbers: span does not need 2 numbers to describe its bounds/extents, because you can just increment the contiguous iterator being put into the span. You cannot increment “just 10 bits” from the iterator that goes into a bit_view: either the bit_iterator itself needs to be incremented, or an external abstraction applied to bit_view (like, e.g. std::ranges::view::drop(10)).

Writing the algorithms was simple, really. It turns out most of the algorithms in C++ aren’t too hard when you sit down with them and read the requirements and listen to conference talks and read text books about them.

But the next part? Getting things fast is where things got…. interesting.

Phase 3 - Optimizations

✔️ 🏆 - Everything, plus most of the stretch goals.

Optimizing everything was the hardest part of this Summer of Code, but also the most satisfying. I plan to write an article later with much more detailed information, but the success here is clear as day. There were severe improvements made over top of the bit intrinsics GCC ships in libstdc++ (the ones detailed by Jens Maurer’s p0553), since they only work with unsigned numeric types. This excluded enumerations (including std::byte) and most character types as well. We also identified several places where GCC trips over itself as far as code generation, something that actually made me publish this article today rather than a full week ago (feel free to poke the bear here and see all the zany codegen and constexpr mishaps between MSVC, GCC, and Clang: Godbolt). I would like to actually congratulate Clang, which gets the code generation and work done 100% right when you affix the platform. It even recognizes that the use of the built-ins, one with the addition, are actually equivalent code, and it dumps out the optimal assembly. It is pretty great!

In all seriousness, I could spend all day writing about this kind of stuff. But, why should I prattle on about algorithmic improvements, intrinsic usage, codegen and the like, when I can simply show some numbers. I re-implemented Howard Hinnant’s performance benchmarks for almost all of the algorithms he talked about (sans std::rotate). The results are in:

Benchmark                            Time             CPU   Iterations
noop                             0.000 ns        0.000 ns   1000000000
is_sorted_by_hand                 2842 ns         2888 ns       248889
is_sorted_base                   56290 ns        57199 ns        11200
is_sorted_vector_bool           273079 ns       278308 ns         2358
is_sorted_bitset                192486 ns       194972 ns         3446
is_sorted_itsy_bitsy               817 ns          820 ns       896000
is_sorted_until_by_hand           2812 ns         2825 ns       248889
is_sorted_until_base             48404 ns        48652 ns        14452
is_sorted_until_vector_bool     251334 ns       251116 ns         2800
is_sorted_until_bitset          187284 ns       185904 ns         3446
is_sorted_until_itsy_bitsy         679 ns          680 ns       896000
find_by_hand                      2443 ns         2455 ns       280000
find_base                        22696 ns        22949 ns        32000
find_vector_bool                 84364 ns        85449 ns         8960
find_bitset                      90512 ns        89979 ns         7467
find_itsy_bitsy                   2422 ns         2400 ns       280000
fill_by_hand                       256 ns          255 ns      2635294
fill_base                         2533 ns         2511 ns       280000
fill_vector_bool                   254 ns          257 ns      2800000
fill_bitset                     126316 ns       125552 ns         4978
fill_bitset_smart                  255 ns          257 ns      2800000
fill_itsy_bitsy                    259 ns          262 ns      2800000
fill_itsy_bitsy_smart              254 ns          255 ns      2635294
sized_fill_by_hand                 252 ns          251 ns      2800000
sized_fill_base                   2567 ns         2567 ns       280000
sized_fill_vector_bool          113136 ns       112305 ns         6400
sized_fill_bitset               124528 ns       125558 ns         5600
sized_fill_bitset_smart            254 ns          251 ns      2800000
sized_fill_itsy_bitsy              257 ns          257 ns      2800000
sized_fill_itsy_bitsy_smart        256 ns          257 ns      2800000
equal_by_hand                     1020 ns         1025 ns       640000
equal_memcmp                     0.321 ns        0.312 ns   1000000000
equal_base                       0.323 ns        0.328 ns   1000000000
equal_vector_bool               242796 ns       239955 ns         2800
equal_vector_bool_operator      256364 ns       254981 ns         2635
equal_bitset                     0.000 ns        0.000 ns   1000000000
equal_bitset_operator            0.000 ns        0.000 ns   1000000000
equal_itsy_bitsy                   518 ns          516 ns      1000000
equal_itsy_bitsy_operator          513 ns          516 ns      1120000
count_by_hand                     5606 ns         5625 ns       100000
count_base                       46712 ns        46490 ns        14452
count_vector_bool                98263 ns        97656 ns         6400
count_bitset                    111041 ns       109863 ns         6400
count_bitset_smart               11085 ns        10986 ns        64000
count_itsy_bitsy                  5509 ns         5580 ns       112000
count_itsy_bitsy_smart            5500 ns         5625 ns       100000
copy_by_hand                       259 ns          255 ns      2635294
copy_base                         3202 ns         3209 ns       224000
copy_vector_bool                192254 ns       192540 ns         3733
copy_bitset                     146175 ns       146484 ns         4480
copy_bitset_operator               262 ns          261 ns      2635294
copy_itsy_bitsy                    258 ns          262 ns      2800000
copy_itsy_bitsy_operator           259 ns          255 ns      2635294
sized_copy_by_hand                 259 ns          255 ns      2635294
sized_copy_base                   3258 ns         3278 ns       224000
sized_copy_vector_bool          220069 ns       219727 ns         3200
sized_copy_bitset               151193 ns       149972 ns         4480
sized_copy_itsy_bitsy              269 ns          267 ns      2635294

There is still performance left on the table here in some cases, but the results are clear: our bitsy::bit_iterators and data structures severely outperform std::vector<bool> from current-generation libstdc++ (GCC 9) and either meet or exceed the current algorithmic benchmarks in all categories.

Here are the results for VC++ from Visual Studio 16.2.3:

Benchmark                            Time             CPU   Iterations
sized_copy_by_hand                 554 ns          558 ns      1120000
sized_copy_base                   2670 ns         2668 ns       263529
sized_copy_vector_bool          201823 ns       204041 ns         3446
sized_copy_bitset               189604 ns       188354 ns         3733
sized_copy_itsy_bitsy              190 ns          188 ns      3733333
copy_by_hand                       606 ns          614 ns      1120000
copy_base                         2431 ns         2431 ns       263529
copy_vector_bool                244844 ns       245857 ns         2987
copy_bitset                     171791 ns       172631 ns         4073
copy_bitset_operator               147 ns          146 ns      4480000
copy_itsy_bitsy                    170 ns          167 ns      3733333
copy_itsy_bitsy_operator           145 ns          148 ns      4977778
count_by_hand                     2728 ns         2727 ns       263529
count_base                       67899 ns        65569 ns        11200
count_vector_bool               132797 ns       131830 ns         4978
count_bitset                     98924 ns        97656 ns         6400
count_bitset_smart                5299 ns         5301 ns       112000
count_itsy_bitsy                  2563 ns         2550 ns       263529
count_itsy_bitsy_smart            2601 ns         2609 ns       263529
equal_by_hand                     1023 ns         1001 ns       640000
equal_memcmp                       518 ns          516 ns      1120000
equal_base                       65633 ns        65569 ns        11200
equal_vector_bool               230969 ns       230164 ns         2987
equal_vector_bool_operator         525 ns          531 ns      1000000
equal_bitset                    146907 ns       146484 ns         4480
equal_bitset_operator              528 ns          531 ns      1000000
equal_itsy_bitsy                   532 ns          531 ns      1000000
equal_itsy_bitsy_operator          527 ns          516 ns      1120000
sized_fill_by_hand                 515 ns          516 ns      1120000
sized_fill_base                   1805 ns         1800 ns       373333
sized_fill_vector_bool          113288 ns       111607 ns         5600
sized_fill_bitset               145251 ns       144385 ns         4978
sized_fill_bitset_smart            138 ns          138 ns      4977778
sized_fill_itsy_bitsy              162 ns          164 ns      4480000
sized_fill_itsy_bitsy_smart        167 ns          167 ns      3733333
fill_by_hand                       504 ns          502 ns      1120000
fill_base                         1824 ns         1842 ns       407273
fill_vector_bool                149444 ns       149613 ns         4073
fill_bitset                     145098 ns       147524 ns         4978
fill_bitset_smart                  147 ns          148 ns      4977778
fill_itsy_bitsy                    566 ns          572 ns      1120000
fill_itsy_bitsy_smart              163 ns          161 ns      4072727
find_by_hand                     64005 ns        64174 ns        11200
find_base                        45115 ns        45516 ns        15448
find_vector_bool                114227 ns       114397 ns         5600
find_bitset                      78854 ns        77424 ns         7467
find_itsy_bitsy                  64992 ns        64523 ns         8960
is_sorted_until_by_hand          49151 ns        48828 ns        11200
is_sorted_until_base             65651 ns        65569 ns        11200
is_sorted_until_vector_bool     231133 ns       234375 ns         3200
is_sorted_until_bitset          161046 ns       163923 ns         4480
is_sorted_until_itsy_bitsy        1459 ns         1475 ns       497778
is_sorted_by_hand                52399 ns        51618 ns        11200
is_sorted_base                   68395 ns        68011 ns         8960
is_sorted_vector_bool           236765 ns       235395 ns         2987
is_sorted_bitset                162437 ns       163923 ns         4480
is_sorted_itsy_bitsy              1420 ns         1444 ns       497778
noop                             0.325 ns        0.328 ns   1000000000

Note that the performance here might not be as great. In order to preserve constexpr, we could not use intrinsics in VC++ because none of their intrinsics are constexpr. Their compiler does not have std::is_constant_evaluated() in any form, which makes it impossible to use low-level, fast functions in MSVC for the algorithms and other places without giving constexpr the guillotine. Hopefully, the situation on that front will improve and we will get better constexpr-related goodies in the releases to come.

I’m almost certain Alisdair Meredith and Vincent Reverdy would be proud to know that the papers they thought up of and 13 and 3 years ago, respectively, can enable such great performance. And the best part about this is…

You Can Have It Too

While I implemented this for libstdc++ and for itsy.bitsy, the performance is not limited to the standard, or to itsy bitsy. The point is that the iterators are not an implementation-defined, private mess. Nor is it like std::bitset, where it has no iterators or begin()/end() at all. These are well-defined, public interfaces that are going to go into the standard. That means if you write a data structure that works with bits and opt to use bitsy::bit_iterator or __gnu_cxx::bit_iterator, you get the performance benefits when using std::equal and std::find and std::copy too. So rather than sinking the tiny handful of standard library maintainer time into optimizing a single container, they optimize the algorithm and everyone gets to benefit.

Note that there are even more optimizations to perform here: there are plenty of optimization opportunities when someone copies a bit_iterator<std::byte*> to, say a bit_iterator<std::uint64_t*>. The current overloads don’t handle such a case (because it is a difficult case to handle generically and with all due speed). Being able to tackle that in a far more generic fashion will be important to the continued longevity of making the basic abstractions we use faster and better than before.

This also has further downstream consequences: as pretty as Conor Hoekstra’s code is, nobody who cares in performance critical areas is going to use that beautiful solution if it exhibits the std::vector<bool> levels of performance. Performance is correctness, and if I can write a disgusting hand-optimized loop and get better performance, you had better believe I’m going to write that disgusting code that would probably make Conor very sad.


The liberating point about this exploration here is that we can have our beautiful algorithmic cake and develop a powerful algorithmic intuition, and – as long as we commit to improving the algorithm – we can have our speedy cake too and share it with everyone. That means that you, the application developer, can focus on algorithm intuition and reaching Sean Parent levels of “that’s a rotate”. And the library developers and interested parties can write the optimization in their algorithms and other places. Once. For everyone. For all time. And finally move on to doing more interesting things that twiddling bits, something that should’ve been a solved problem for 20 years! Algorithms no longer need to be for the Computer Science Gods and the Geniuses: we, the proletariat, can seize the means of performance from the bourgeoisie and the regular plebeian developer can write std::copy and std::equal and have it be exactly as fast as intended…!

But I digress. There is a lot more to do, but this is it for now. The GCC patch can be reviewed but albeit it’s likely going to be rejected because there’s some work I need to do before hand to make sure the tests can work in an isolated GCC. Most notably, I need to implement a std::span for libstdc++ and I need a std::ranges::subrange type. Then all the tests will work directly.

Remember to optimize your algorithms, not your data structures, and hug your local library developer (with permission).

Catch you later. 💚

P.S.: double underscores are ugly and I hate them with every fiber of my being.