Is there a chance to access vector<bool> content byte- or word-wise?

[MikeStgt]

Question: see title.

Why?
I'd like to count all true values by the sum of 'on' bits of a single char or unsigned int -- in the hope to be a bit faster.

[salem c]

http://www.cplusplus.com/reference/vector/vector-bool/
Except there seems to be no guarantee of the underlying implementation, or a means of finding out.
Specifically, there is no vector<bool>::data

> in the hope to be a bit faster.
A bit faster than what?

Or put another way, a bit faster at the expense of
- you spending a lot of time for minimal gains
- the code becomes less portable
- the code becomes less readable.

Unless you know you have a performance problem (ie, you've profiled the code with real data), you're probably better off adding features and fixing bugs.

If you have a idea that it might be a performance problem later, then perhaps start with

#include <iostream>
#include <vector>
using namespace std;

class myVB : public vector<bool> {
public:
    int countSet() {
        int count = 0;
        for ( size_t i = 0 ; i < size() ; i++ ) {
            if ( at(i) ) count++;
        }
        return count;
    }
};

int main(int argc, char *argv[])
{
    myVB foo;
    foo.push_back(true);
    foo.push_back(false);
    foo.push_back(true);
    foo.push_back(false);
    foo.push_back(true);
    foo.push_back(true);
    foo.push_back(false);
    cout << foo[0] << endl;
    cout << foo.countSet() << endl;
}

If vector<bool> really does become an issue, then you only have the inside of a class wrapper to re-implement.

[MikeStgt]

A bit faster than what?

    for (n=1; n <= i; n++)
		if (p[n]) c++;

I just ask as I stumbled over http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

[salem c]

Do you have megabytes of booleans you need to analyse at say video frame rates?

Sure, why not, just implement your own specialisation of vector bool which allows you to do bit-twiddling hacks.

How much are you going to save by doing this?
Will you be able to measure it?
Will your users even notice?

[MikeStgt]

Will your users even notice?

I am the user and I will do notice it. The size of the vector is 10e8 at minimum, so the order of magnitude of the runtime is about 0.1 seconds and more.
Some more questions?

I had hoped someone would come up with the information that modern processors offer this function for crypto-gizmo and with C++ it may be accessed by... -- well, I hoped.

[salem c]

OK, how many 0.1 seconds do you have to save, to recoup the effort so far expended on discussing "optimisation".

Further, if you do make the program faster, are you going to change your behaviour?
You're just going to "sit and wait" whether you speed this up or not.

A real performance improvement would be taking a run-time of 1 hour down to 1 minute. At which point, your user changes their behaviour from "go to lunch" to "sit and wait".

Oh, just so you don't think I'm being overly obtuse.
https://en.wikichip.org/wiki/population_count
But you're not going to be able to use this directly with a boolean vector.

Perhaps this would be a better data structure for you.
http://www.cplusplus.com/reference/bitset/bitset/
At least it has a count() method, which might make use of very efficient machine level 'popcount' instructions, or at least optimised bit-twiddling hacks.

[Ganado]

I'm not too experience with bit-twiddling, but I think a good thing to know is why you need to count the number of 1s in an array of bits of magnitude 10e8? And how often is this done (60 FPS)? Perhaps the solution here might be to not do it at all and find another way.

Is this for some sort of video processing? Perhaps there's a better way to use a GPU to your advantage (doing the calculation at a per-fragment level in the shader).

[mzimmers]

Hi -

This isn't a direct answer to your question, but if you're manipulating that volume of data, and performance is important, you're probably better off not doing this with vectors. While the overhead of object-based programming is very small with modern compilers, it's non-zero.

Efficiently manipulating amount of data, no matter what you're doing with it, is something of an emerging discipline. If this is something important to you, you may want to revisit the entire architecture of your solution (from the storage technology up).

[MikeStgt]

Thank you to all who answered, thank you for your time.

OK, how many 0.1 seconds do you have to save, to recoup the effort so far expended on discussing "optimisation".

It's not about getting it 10% faster, my goal as a beginnter is to learn something about C++, what tools do I have, what could be done with this kit. Learning by toying.

Perhaps this would be a better data structure for you.
http://www.cplusplus.com/reference/bitset/bitset/

Thank you for this hint. Works.

but I think a good thing to know is why you need to count the number of 1s in an array of bits of magnitude 10e8? And how often is this done (60 FPS)?

Not very often, just once in a while. And I do need to count the 'on' bits to compare the result with existing programgs from others.

If this is something important to you, you may want to revisit the entire architecture of your solution

No, it is not important for me, I just test, how I get along with C++, if I could imagine to do something useful with it. The question I ask in the subject of this thread is a kind of "revisit of the entire architecture".

What I do with this 1e8 bits and more in that bool vector? Counting primes, not even new ones, since long time well known primes. So for sure the result is colourless, it is only about the way to get it. And to get it fast. Of course I coud run this ready to use program from https://primesieve.org/ but as said before, this is not my goal, it is a role model.

Edit: marked what answered my question.