how much memory does vector<bool> take?

[zl2k]

hi, there
I am using a big, sparse binary array (size of 256^3). The size may be
changed in run time. I first thought about using the bitset but found
its size is unchangeable. If I use the vector<bool>, does each element
takes 4 bytes instead of 1 bit? I am using gcc3.4.4. There is a
bit_vector which is kind of old so I wont use that. Any other choices?
Thanks ahead.
zl2k

[Victor Bazarov]

Re: how much memory does vector&lt;bool& gt; take?

zl2k wrote:[color=blue]
> hi, there
> I am using a big, sparse binary array (size of 256^3). The size may be
> changed in run time. I first thought about using the bitset but found
> its size is unchangeable. If I use the vector<bool>, does each element
> takes 4 bytes instead of 1 bit?[/color]

No, supposedly std::vector<boo l> is a proper specialisation of std::vector
and each element only takes one bit.
[color=blue]
> I am using gcc3.4.4. There is a
> bit_vector which is kind of old so I wont use that. Any other choices?[/color]

You can always roll your own...

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Marcus Kwok]

Re: how much memory does vector&lt;bool& gt; take?

zl2k <kdsfinger@gmai l.com> wrote:[color=blue]
> I am using a big, sparse binary array (size of 256^3). The size may be
> changed in run time. I first thought about using the bitset but found
> its size is unchangeable. If I use the vector<bool>, does each element
> takes 4 bytes instead of 1 bit? I am using gcc3.4.4. There is a
> bit_vector which is kind of old so I wont use that. Any other choices?[/color]

Since vector<bool> is required to be a specialization, you should read
the following articles by Herb Sutter before deciding on using it:

vector<bool> Is Nonconforming, and Forces Optimization Choice

http://www.gotw.ca/publications/N1185.pdf

vector<bool>: More Problems, Better Solutions

http://www.gotw.ca/publications/N1211.pdf

Technically, even though vector<bool> is mentioned in the Standard,
its use is unspecified. Quoting from the second article:

Curiously, vector<bool> is not actually specified, so no current use
of it invokes well specified behavior. Its declaration appears in
the standard, but not a single function is specified. Note that the
argument "it's just the same as vector" fails because a vector<bool>
is demonstrably not a vector: it has a different interface (i.e.,
flip()), a different structure (e.g., reference is a class, not a
typedef for T&), does not meet the same requirements (e.g., container
and iterator requirements), etc.

Since you are dealing with a sparse array, maybe you could use a
std::map<int, bool> or something.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[Greg]

Re: how much memory does vector&lt;bool& gt; take?


Marcus Kwok wrote:[color=blue]
> zl2k <kdsfinger@gmai l.com> wrote:[color=green]
> > I am using a big, sparse binary array (size of 256^3). The size may be
> > changed in run time. I first thought about using the bitset but found
> > its size is unchangeable. If I use the vector<bool>, does each element
> > takes 4 bytes instead of 1 bit? I am using gcc3.4.4. There is a
> > bit_vector which is kind of old so I wont use that. Any other choices?[/color]
>
> Since vector<bool> is required to be a specialization, you should read
> the following articles by Herb Sutter before deciding on using it:
>
> vector<bool> Is Nonconforming, and Forces Optimization Choice
> http://www.gotw.ca/publications/N1185.pdf
>
> vector<bool>: More Problems, Better Solutions
> http://www.gotw.ca/publications/N1211.pdf[/color]

Neither of the quoted articles presents an argument against using
vector<bool>. They are merely criticisms of vector<bool>'s
classification as a vector - an issue of interest only to those
designing the C++ standard library.
[color=blue]
> Technically, even though vector<bool> is mentioned in the Standard,
> its use is unspecified. Quoting from the second article:
>
> Curiously, vector<bool> is not actually specified, so no current use
> of it invokes well specified behavior. Its declaration appears in
> the standard, but not a single function is specified. Note that the
> argument "it's just the same as vector" fails because a vector<bool>
> is demonstrably not a vector: it has a different interface (i.e.,
> flip()), a different structure (e.g., reference is a class, not a
> typedef for T&), does not meet the same requirements (e.g., container
> and iterator requirements), etc.
>
> Since you are dealing with a sparse array, maybe you could use a
> std::map<int, bool> or something.[/color]

Why? Whether vector<bool> should be called a "vector" or not - makes no
difference to the issue of how well it can solve a particular problem.
The only question that the programmer needs to decide is whether a
std:vector<bool > can do what the program needs it to do. And if that
task is to store a dynamically-resizable container of one-bit boolean
values - then the answer is clearly "yes." And there would no reason
for a program not to use a std::vector<boo l> in that case.

Greg

[Marcus Kwok]

Re: how much memory does vector&lt;bool& gt; take?

Greg <greghe@pacbell .net> wrote:[color=blue]
> Marcus Kwok wrote:[color=green]
>> zl2k <kdsfinger@gmai l.com> wrote:[color=darkred]
>> > I am using a big, sparse binary array (size of 256^3). The size may be
>> > changed in run time. I first thought about using the bitset but found
>> > its size is unchangeable. If I use the vector<bool>, does each element
>> > takes 4 bytes instead of 1 bit? I am using gcc3.4.4. There is a
>> > bit_vector which is kind of old so I wont use that. Any other choices?[/color]
>>
>> Since vector<bool> is required to be a specialization, you should read
>> the following articles by Herb Sutter before deciding on using it:
>>
>> vector<bool> Is Nonconforming, and Forces Optimization Choice
>> http://www.gotw.ca/publications/N1185.pdf
>>
>> vector<bool>: More Problems, Better Solutions
>> http://www.gotw.ca/publications/N1211.pdf[/color]
>
> Neither of the quoted articles presents an argument against using
> vector<bool>. They are merely criticisms of vector<bool>'s
> classification as a vector - an issue of interest only to those
> designing the C++ standard library.[/color]

From the first article:

2. vector<bool>::i terator does not meet the requirements of a
forward, bidirectional, or random-access iterator, although the
last is strongly implied by the specialization' s naming and
position. This means that it may not work with a conforming
implementation of a standard library algorithm.

The possibility of not being able to use a vector<bool> with standard
library algorithms is an argument against using it in my book.

5. vector<bool>'s name is misleading because the things inside aren't
bools.

// Example 1: Works for every T except bool
//
template<class T>
void g( vector<T>& v ) {
T& r = v.front();
T* p = &*v.begin();
// ... do something with r and *p ...
}

If something is explicitly stated as being a vector, is it unreasonable
to assume that it should behave as a vector?

6. vector<bool> forces a specific optimization choice on all users by
enshrining it in the standard. That's probably not a good idea,
even if the actual performance overhead turns out to be negligible
for a given compiler for most applications; different users have
different requirements.

In this case, vector<bool> forces the "favour less space at the
expense of potentially slower speed" optimization choice on all
programs. The implicit assumption is that virtually all users of
a vector of bools will prefer "less space" at the expense of
"potentiall y slower speed," that they will be more
space-constrained than performance-constrained. This is clearly
untrue.
[color=blue][color=green]
>> Technically, even though vector<bool> is mentioned in the Standard,
>> its use is unspecified. Quoting from the second article:
>>
>> Curiously, vector<bool> is not actually specified, so no current use
>> of it invokes well specified behavior. Its declaration appears in
>> the standard, but not a single function is specified. Note that the
>> argument "it's just the same as vector" fails because a vector<bool>
>> is demonstrably not a vector: it has a different interface (i.e.,
>> flip()), a different structure (e.g., reference is a class, not a
>> typedef for T&), does not meet the same requirements (e.g., container
>> and iterator requirements), etc.
>>
>> Since you are dealing with a sparse array, maybe you could use a
>> std::map<int, bool> or something.[/color]
>
> Why?[/color]

The key word that triggered my response was "sparse". If it is known
that the data is sparse, then it may not be necessary to store all 256^3
entries.
[color=blue]
> Whether vector<bool> should be called a "vector" or not - makes no
> difference to the issue of how well it can solve a particular problem.
> The only question that the programmer needs to decide is whether a
> std:vector<bool > can do what the program needs it to do. And if that
> task is to store a dynamically-resizable container of one-bit boolean
> values - then the answer is clearly "yes." And there would no reason
> for a program not to use a std::vector<boo l> in that case.[/color]

....unless speed requirements are more important than memory
requirements.

Since vector<bool> uses a proxy class instead of storing true bools,
there is some additional overhead associated with every element access.
If these values are accessed in a tight loop, performance considerations
can be substantial.

I'm not saying not to use vector<bool> at all or that vector<bool> won't
meet the OP's requirements; I'm just saying that the OP should be aware
of the issues with it before deciding that he should "clearly" use it.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[Jerry Coffin]

Re: how much memory does vector&lt;bool& gt; take?

In article <e4shrf$22u$1@n ews-int2.gatech.edu >,
ricecake@gehenn om.invalid says...

[ ... ]
[color=blue]
> In this case, vector<bool> forces the "favour less space at the
> expense of potentially slower speed" optimization choice on all
> programs. The implicit assumption is that virtually all users of
> a vector of bools will prefer "less space" at the expense of
> "potentiall y slower speed," that they will be more
> space-constrained than performance-constrained. This is clearly
> untrue.[/color]

Although the required specialization of vector<bool> has
the _potential_ to reduce speed, the reality is that on
almost any reasonably recent processor, it will generally
_increase_ speed unless the vector involved is _quite_
small.

The situation is pretty simple: on most current
processors, the reduced size also means reduced memory
access and improved cache utilization. Currently, memory
is a lot slower than the processor as a rule (and the
ratio favors processors more strongly all the time). This
means that even if you have to do quite a lot of
computation to avoid a memory access, it's usually worth
it. In this case, there's not really a lot of extra
computation at all, and you're typically reducing memory
references by a ratio of at least 8:1 (and 32:1 isn't
unheard of).

[ ... ]
[color=blue][color=green]
> > Whether vector<bool> should be called a "vector" or not - makes no
> > difference to the issue of how well it can solve a particular problem.
> > The only question that the programmer needs to decide is whether a
> > std:vector<bool > can do what the program needs it to do. And if that
> > task is to store a dynamically-resizable container of one-bit boolean
> > values - then the answer is clearly "yes." And there would no reason
> > for a program not to use a std::vector<boo l> in that case.[/color]
>
> ...unless speed requirements are more important than memory
> requirements.[/color]

Depending heavily upon your target -- if your target has
a cache, chances are good that vector<bool> actually
improves speed (unless your memory use is so low in
general that even without the reduction in memory usage
it would all fit in the cache).

My own advice would be to use a typedef:

vector<boolean> my_vect;

And then test and profile with both:

typedef char boolean;

and:

typedef bool boolean;

and possibly even:

typedef int boolean;

and see which works better for your situation. The
conversion rules for bool in C++ are loose enough that
this will normally work without any extra work on your
part as to how you use your boolean values. The one place
you're at all likely to run into a problem is if you want
to provide separate overloads (or specializations ) for
your booleans and some of the other types mentioned above
-- the typedef only creates a new name, not a new type.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Marcus Kwok]

Re: how much memory does vector&lt;bool& gt; take?

Jerry Coffin <jcoffin@taeus. com> wrote:[color=blue]
> My own advice would be to use a typedef:
>
> vector<boolean> my_vect;
>
> And then test and profile with both:
>
> typedef char boolean;
>
> and:
>
> typedef bool boolean;
>
> and possibly even:
>
> typedef int boolean;
>
> and see which works better for your situation.[/color]

Yes, I will agree that performance claims can only truly be determined
through profiling. Maybe even include tests with std::map<int, boolean>
(for the various types of "boolean" above) to see how they compare too
(assuming that the map satisfies the OP's requirements).

--
Marcus Kwok
Replace 'invalid' with 'net' to reply