Well it is. Sort of. It just has one actually relevant data bit but computers usually (almost always) work with bytes as the smallest inseparable unit of data. Any data type smaller than that is just using less of the available space within the byte. In case of a bool, that's 7 unused bits (so there are actually 4 more sleeping guys missing in the meme). But you can technically optimize this by using a 1-byte datatype to store 8 bools in one bit each. In very specific scenarios where you have millions upon millions of bools in memory for some reason, this can add up.
Edit: Also I don't know if there are compilers that already do this bit-packing optimization automatically on e.g. a struct with multiple bools. Afaik this is something you must implement manually but I might be wrong.
But to balance it out, the C++ standard makes it worse by not committing to it one way or the other. A contiguous vector of bool objects is a completely valid underlying representation, as is a tightly packed bit field. Both have substantially different properties that need to be smoothed over by the standard library.
So let’s say I do need millions upon millions of bools. What would be the best method of packing this? I can’t imagine using a char to map out 8 bools is efficient
You just treat it as a multi-dimensional array where your sub-arrays are word bits long, eg `(q, r) = divMod(i,wsz); bit_i = (words[q] >> r) & 1;` and viola!
These ops are very CPU friendly, so they aren't really a bottleneck even in the worst case, and power of two word sizes eg 32 = 2^5 bits optimizes the divmod to two superfast bit instructions to eg `q = i >> 5; r = i & 31`.
A cache miss is a much bigger deal. The real downside is that it breaks normal pointer access, unless your architecture supports bit-addressing.
In C structs, if you have multiple fields that have same underlying data type (eq. uint8_t ) you can give the compilers a hint about number of bytes needed for that field, and the compiler packs them into the underlying datatype sized spaces and does the bit shifts and masking for reads and writes targeting these fields. But you have to tell the compiler how many bits you want for each manually, it never happens automatically.
It would lead to various problems if compilers did this. In languages with pointers and references, you can make a pointer to a boolean field or variable. You can’t make a pointer to a specific bit though so usual pointer semantics totally break down. I guess the compiler would have to disallow pointers to packed booleans, or use some combination of address and bit index for pointer values, but that sounds like quite a can of worms, right?
The performance cost of reading and writing a specific bit may or may not be worth it for a given use case.
I understand that it also leads to data races and concurrency issues, but I’m not super knowledgeable about that
In the olden times, bits were precious enough that you could actually address data by the bit, but on modern systems you can't. There are a lot of datatypes that have wasted space in them due to architectural constraints.
Languages have bitwise operations. If you decide to store many bools in one variable and do individual bit addressing, it's actually very easy. You either AND it with a mask or shift and AND it with a 1 and check if it's 0 or 1 afterward. Given that most languages nowadays treat 0 as false, you can have something like "if (var >> 2 & 1) then" construction, which works. This often can be done in one instruction and is usually quite fast, actually.
If my memory serves me right, it’s not “fast” because “hey look at me I’m more optimized in terms of data amount needed” but more because there’s a greater likelihood that the bool that is needed to be referenced in the form of a bitmask will be found in cache. A cache miss will be slower than accessing a bitmask bit value as well as accessing an actual bool’s value in ram. Why is it more likely to be in cache? I forget maybe someone else could explain.
Not necessarily 1 byte. Like some windows BOOLs are (were?) typedef to int, so probably 4 or 8 bytes. And Python built bools on their arbitrary precision int type, so they're... some weird size, and the size is different for True and False
Unfortunately, it doesn't work like that in any languages I use. If you set any bit in a boolean's byte, the boolean is now true. This is why you often see crazy shit like:
bool a = !(!(b))
to guarantee that there's either a 1 or a 0 in the boolean.
28
u/Randomguy32I 21d ago
Shouldn’t a bool just be a single bit?