CppCon 2016

Efficient bit abstractions for the standard library, or how to beat vector<bool> performances by three orders of magnitude.

Can you imagine a perfect world? A world of unicorns. A world of double rainbows. A world of candy mountains. A world in which vector<bool> would not even have existed. As the first three aspects are easy to imagine, I will mostly focus on the last one. For about 20 years now, vector<bool> has been regarded as a bad design decision. There is no problem with the functionality provided by a dynamic vector of bits, but specializing vector for boolean data types was not the best idea ever. In this talk, I will present a radically new approach, generalizing existing implementation practices and experimentations, to achieve both genericity and performances for bit manipulation. I will describe how we designed a minimalist set of abstractions to access and manipulate bits and to serve as a common basis for bit oriented data structures, algorithms and arbitrary precision arithmetic. This presentation echoes a standardization work that will hopefully make bit utilities available in a future revision of the C++ standard library.

Bit manipulation is used as a fundamental building block of a wide range of applications including arithmetic of big integers, cryptography, hash tables, compression, fast Fourier transforms and bioinformatics. We started this work while investigating... the expansion of the Universe. Cosmological simulations on supercomputers require fast data structures, and in our case bit manipulation was a bottleneck. A common problem with bit abstractions is that they need a double standard: an easy to use interface for users, and a full access to low level instructions and compiler intrinsics to make the most of modern architectures. I will review our approach and give examples on how to use our library. I will also explain how to use bit values, bit references, bit pointers and bit iterators to design algorithms that outperform bit vectors by factors varying between 100 an 3500. I will conclude this talk by discussing how the bit abstraction proposal may affect the future of the standard library and particularly how it will be interfaced with standard algorithms, standard containers, ranges and arbitrary precision arithmetic.