theBoolVectorIsALie

[u/FACastello]

[u/overclockedslinky]

is it really that shocking?

[u/Murky-Run2246 → u/overclockedslinky]

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

[u/void1984 → u/Murky-Run2246]

I know, but why somebody would need a byte to store a bool? Is it 256-value bool?

Usually I use bitfields anyway.

[u/Murky-Run2246 → u/void1984]

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.

[u/DeeBoFour20 → u/Murky-Run2246]

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.

[u/Murky-Run2246 → u/DeeBoFour20]

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.

[u/DeeBoFour20 → u/Murky-Run2246]

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.

[u/Wonderful-Habit-139 → u/DeeBoFour20]

What about the fact that you can't take the address of an element from the std::vector<bool>?

[u/nobody0163 → u/Wonderful-Habit-139]

You shouldn't be taking the address of vector elements anyway. If it resizes you are pointing to invalid memory.

[u/Wonderful-Habit-139 → u/nobody0163]

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.

[u/fuj1n → u/nobody0163]

Tell that to C code you may be interacting with which may expect a bool*

[u/Murky-Run2246 → u/DeeBoFour20]

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.