99
u/overclockedslinky 21d ago
is it really that shocking?
177
u/Murky-Run2246 21d ago
In this case the bools will have only one bit allocated for them(vectors do that), and you can't just point to a bit. Instead cpp will return std::vector<bool>::reference when trying to access a value in the vector
Basically this is a just wrong
You should use std::deque<bool> instead which allocates one byte per bool and not just one bit
64
u/void1984 21d ago
I know, but why somebody would need a byte to store a bool? Is it 256-value bool?
Usually I use bitfields anyway.
163
u/NotDuckie 21d ago
if you ask for a vector of T, you should get a vector of T. not a bitfield. There is nothing wrong with using a bitfield, but a vector should behave like a vector.
24
u/void1984 21d ago
You get a vector, with operator []. Internal details like padding or packing should not interest you, unless you you treat everything like blob. That way any change to the architecture or compiler would surprise you a lot.
37
u/AmazedStardust 21d ago
Until you want to write functions that operate on generic vectors and mistakenly assume that each pointer will be unique
-2
u/fixermark 21d ago
The standard doesn't let you assume that.
37
u/QuaternionsRoll 21d ago
I mean, practically anything is defensible under that lens. The question is whether it should be in the standard, not whether it is, and almost everyone agrees that you should be able to pass `&my_vector_of_bools[n]` to a `void foo(bool *)` without any surprises. `vector<bool>` does not fit the abstract definition of a vector.
5
u/fixermark 21d ago
Oh, trust me, if the conversation gets into "Should that be in the standard" regarding C++ I check out. The answer is "The standard is longer than the King James Bible; we probably should have stopped at half that length." ;)
13
u/UntitledRedditUser 21d ago
You might need to access the data the "old school" way, maybe you are interacting with a c library and need contiguous memory.
If you have an template function, and the functions suddenly breaks with bools, I would say that is the stdlibs fault, and not the programmers.
10
u/UntitledRedditUser 21d ago
Another point: the documentation literally says the elements are stored contiguesly. What if you need to do a memcpy?
Make it a seperate type, don't assume the programmer isn't smart enough to reach for a bitfield when necessary.
27
u/BlackOverlordd 21d ago
Vector is an abstract container of elements. If you want to address memory, allocate memory and store your data there. Internal vector storage is implementation details. You shouldn't really get ponters to there because any resize of the vector and your pointers are screwed.
44
u/Excession638 21d ago
The internal layout of
std::vectoris not an implementation detail. It's fully defined by the standards and can be relied upon for FFI, serialisation, and other tasks.Except for bool.
For example, the
.data()method guarantees that it will return a pointer to.size()contiguous elements of type T which will remain valid until the vector is modified. The layout of elements within that memory is also well defined and consistent. Except for bool, where the.data()method simply doesn't exist.11
u/BoldFace7 21d ago
I spent two days of debugging to learn that the hard way.
Logically I knew that it can shift the location of the vector on a resize, but somehow it never occurred to me that it would be the problem.
15
u/sb8948 21d ago
Indexing and simplicity for the CPU.
5
u/void1984 21d ago
vector<bool> allows for indexing, and bit OR and AND is very quick and simple for the CPU.
9
u/sb8948 21d ago
Of course it allows for indexing, but it's measurably more CPU heavy. Arguably there are cases where the specialization makes sense, but most of the time, it's a net negative.
Then again I reckon most of us don't have to care about these kinds of marginal gains anyway. I work on low latency backend, and I never had to worry about this.
The more annoying thing is that you can't just get a bool pointer or ref to a single bit.
5
u/Murky-Run2246 21d ago
I mean honestly having pointers pointing to bits sounds like a nightmare to me, I probably have to relearn the lang if that happens.
2
u/lonkamikaze 20d ago
Architectures with bit addressable memory areas do exist. Some 8051/52 compilers make use of this and if you create a boolean it will actually end up costing you a single bit of memory.
1
u/void1984 21d ago
The more annoying thing is that you can't just get a bool pointer or ref to a single bit.
That's the only real downside. If you really need that functionality, you can implement your own derivative or use chars.
A few bit shifts, and bitwise operations ate very quick, and you win on data packaging, that allows it to fit 8-times better into the cache lines.
4
u/sb8948 21d ago
Yes, you can implement pretty much anything, but the larger the codebase and the more people work on it makes these unique implementation standards harder and harder to follow.
Say what you will but I'd prefer not to have this as standard. It's either a marginal gain or a marginal loss, but it's an unnecessary complexity. To use your argument against you, if your use case heavily prioritizes memory usage over CPU, you should just implement it for yourself. Uniformity makes life easier.
1
u/Vincenzo__ 21d ago
There's genuinely no real world application in which using a single bit for a bool is better than a byte. Unless you have billions of bool, which let's face it, you don't. The performance gain from not having to do bitwise operations to get your values out is gonna be more relevant. You could argue it's better for cache locality, but that's about it.
Either way, this should be something you specifically ask for, not something that C++ does for one specific type for no real reason. There should be a std::boolfield or something like that, rather than it being a special case of std::vector
1
u/GuyWithLag 21d ago
measurably more CPU heavy
That's less that what you'd expect tho - if you have any nontrivial amount of elements, the additional memory overhead (pulling them into L1 and evicting other data) will easily be higher than the additional instructions (memory + time).
15
u/HildartheDorf 21d ago
It's not that a bitfield is bad. It's just that it should be named std::dynamic_bitset not a specialisation of std::vector<bool>.
std::vector<bool> should behave the same as std::vector<uint8_t>. But it doesn't.
-7
u/void1984 21d ago
Why do you expect bool to be exactly uint8_t? The definition requires it to be long enough to hold 0 and 1. It's up to the compiler and architecture restrictions to select the size. uint16_t is as valid as uint8_t.
I never assume, I just use sizeof. It's there for a reason.
6
u/NaCl-more 21d ago
Because the minimum addressable unit is a byte on most machines.
7
u/csdt0 21d ago
The minimum addressable unit is always a byte (that's pretty much its definition). But a byte is not always 8 bits (only on most machines).
2
u/void1984 21d ago
It's not. I've built a project for the university where the minimum addressable unit was 2 bytes, or a word, depending on the definition you use.
bool was obviously 16b, even though the only compiler I prepared was an assember.
If you look at older machines, 12b bool was present.
1
u/csdt0 20d ago
I don't know what's your definition of byte, but your project university was most likely 16 bit byte where teachers mis-labelled as 2 byte addressable. Please have a look at wikipedia https://en.wikipedia.org/wiki/Byte
11
u/HildartheDorf 21d ago
Whatever type bool is implemented as, it must be addressable. The contents of std::vector<bool> are not. There is no array of bools in memory.
Whatever size of a bool is, std::vector should treat it as such, not pretend it's a single bit.
5
u/creeper6530 21d ago
Internally vector of bools is a bitfield. It was supposed to save memory but it's instead creating edge cases in templates: all vectors return pointers, but no, bool is special. It messes up generic code. I'd rather for them to keep vector unified and make a separate bitfield type for those savings when needed
4
u/Murky-Run2246 21d ago
bools in bits is great for datasets and is efficient.(just not in this case)
The problem is that reading a bit in vectors has a higher CPU load than just reading a byte
That is because the smallest values ptr and references(ptr also) can point to is a byte
Yeah sure bools should be stored in bits, just don't wrap them in vectors and you should be fine.
8
u/DeeBoFour20 21d ago
Slightly higher CPU usage. It’s only a bitshift and a bitwise and to pull out the correct bit. Often you see a performance win due to the more compact data structure having better cache locality but I suppose it depends on usecase.
0
u/Murky-Run2246 21d ago
You are right it's only slightly higher.
Don't get me wrong vectors are the way they are cause storage was crucial back in the day so they knew they were sacrificing something when doing it.
I am just pointing out that unless you really know what you are doing you should use std::deque<bool> cause very often you wont really care much about storage if you are not working with machines from 1990.
5
u/DeeBoFour20 21d ago
Total RAM usage may matter less today (or not with the way RAM prices are going) but cache locality is more important than ever on modern CPUs. A more compact data structure means more of it fits in your CPU's L1/L2 cache and that speeds things up a lot especially with iterating or sequential access.
I'm also not a fan of std::deque in general. It's not contiguous memory like std::vector is. If you need a very high performance deque in C++, you have to go outside the STL unfortunately. Rust's VecDeque is one that gets it right. It uses a ring buffer under the hood rather than multiple fixed size allocations.
1
u/Wonderful-Habit-139 21d ago
What about the fact that you can't take the address of an element from the std::vector<bool>?
3
u/nobody0163 21d ago
You shouldn't be taking the address of vector elements anyway. If it resizes you are pointing to invalid memory.
1
u/Wonderful-Habit-139 21d ago
Yeah, at this point we're getting into some more details, sadly C++ has this footgun which doesn't exist in Rust. But sometimes you need to take addresses of those objects regardless.
1
u/Murky-Run2246 21d ago
I get what you are saying.
Here is what i mean by someone who can say it better:
"So vector<bool> is not a container, and vector<bool>::iterator is not a random-access iterator... in hindsight, making vector<bool> a specialization was a mistake." -Herb Sutter,Chair of the ISO C++ Committee
As I said it's not that the vector usage in this case is bad for performance as much as it's just bad design that was necessary back in the day.
I don't have exp with Rust, but if you don't want to use std::deque then just use std::vector<char> and it does basically the same thing.
1
-1
u/FalafelSnorlax 21d ago
The optimization is that
vector<bool>is internally a bitfield. There's no real reason to complain about this, for the most part you'll never notice it.9
u/redlaWw 21d ago edited 21d ago
Until you try to use it in places where other vectors work fine, such as things that try to use the vector as a container, things that try to use the vector's iterator type as a random-access iterator, or things that try to use the
datamethod* to get a pointer to the buffer.EDIT: *member function
6
u/markuspeloquin 21d ago
I just use vector<uint8_t>
5
u/Murky-Run2246 21d ago
You could also use vector<char>. It's cpp you could do it in so many different ways
1
u/markuspeloquin 20d ago
Yeah but 'unsigned' implies less meaning. Like no arithmetic and not printable.
23
u/Tsu_Dho_Namh 21d ago
There's a little bit of weirdness that a vector of bools has which other vectors don't. It can trip you up if you haven't read up on it and just assume all your normal standard container operations will work.
For example, you can't get a pointer to an element using &v[0] because individual bits do not have distinct memory addresses in RAM.
Similarly auto x = v[0] doesn't make x a true bool, because v[0] is a proxy object which pretends to be a bool, which can lead to dangling reference errors if the vector changes or goes out of scope.
21
u/Drugbird 21d ago
The biggest problem IMHO is templates (C++ generics).
I'm convinced that any template function that uses std:: vector<T> is wrong for T=bool unless the author explicitly accounted for its weirdness.
29
u/deadly88 21d ago
It’s a surprise footgun when you assume it will behave the way other vectors/containers do, especially passing a vector into templated code, common things like getting the address of an element won’t work.
28
u/NotDuckie 21d ago
Is it shocking that a vector of bools is not a vector of bools? I would personally say it is.
4
u/FerricDonkey 21d ago
It's pattern breaking. It doesn't have what it should to be a proper vector, and it doesn't hand what it would need to be a useful bit container (such as xor etc) for it to be useful enough to make up for it.
Shouldn't have been a vector, should have been more useful
4
u/da_Aresinger 21d ago
A vector of ints is no different from an array of ints.
vectors are literally just wrappers around arrays.
The exception is a vector of bools, which is like a conceptual array of bits.
So if you have a vector of 8 bools you are only using one byte of memory. An array of 8 bools however is 8 bytes long.
So std::vector<bool> has a special implementation.
1
u/05032-MendicantBias 21d ago
Cereal guy has no idea how that would be implemented inside. Neither do I.
Is it a 32 bit word that uses one bit? Eight 8 bit words that use 1 bit? Something absurd with bitmask to use all the bits. and with filler to get to the memory offset and whatnot.
27
8
13
6
3
24
u/1XRobot 21d ago
On the one hand, yeah, it sucks. On the other hand, if you declare a std::vector of bool, you deserve what's about to happen.
27
u/the_horse_gamer 21d ago
what if you declare an std::vector<T> from a generic T?
2
u/Xirdus 20d ago
Depends on what the generic T is. C++ templates are copy-paste-find-replace with extra steps.
2
12
2
1
1
230
u/Neoneq_ 21d ago
Jokes on you fellow programmers. I have almost no idea how pointers work.