std::vector<bool> perormance penalty

I have created a test for various vector<T> types (T in int, bool, char, int_fast8_t, uint_fast8_t).

Summary

I have found that a vector of int is 4 times faster than bool, but char (and *_fast8_t types) can be even faster: 20 times when writing and 50 times when reading

Vector size is 400 million (8 long pattern used 50 million times). First we populate a vector (write), then ve copy the vector to another (read+write). We approximate the read by subtracting the two (read = read+write - write).

type	write [ms]	read+write [ms]	read [ms]
int	92	129	37
bool	419	892	473
char	23	32	9
int_fast8_t	23	32	9
uint_fast8_t	23	31	8

• CPU: AMD EPYC 7B12
• OS: Linux version 6.6.15 amd64
• Compiler: gcc version 13.2.0
• Compliation: g++ -std=c++17 -O3 -W -Wall -Wextra -pedantic -flto vector_bool.cpp -o vector_bool
• Source: pastebin.com

Background

In the standard library of C++ vector<bool> is specialized for space. This is a very old legacy from a time where generally speaking RAMs were very small. In this container the bool type ‐ which uses 1 or even more bytes to store a true/false ‐ is not used for storage: rather a larger integer type is used as underlying array element to store multiple bits. In this case writing a bit requires reading the corresponding integer, altering it with bitwise operations, then writing it back to the container.

Search the Internet if you would like to find other disadvantages of this specialization. This post is only about the magnitude of the performance penalty this decision have caused.

Recommended workarounds

Some alternatives

• Use *_fast8_t as T.
• Use boost::container::vector<bool> instead.
• Create a class Bool that stores a bool and use it as T. This seems to be much more like a school/learning project rather than a production solution. But who knows: there might be circumstances where this is the way.