bool

bool

[Andrew Borthwick]

Hi,

    I'm looking for some advice on boolean variables in g++.  I wrote a little
test program and found that with the 1997/11/05 snapshot, a bool has a size of 4
bytes.  While I recognize that this is not a valid comparison because of the use
of pointers, I found that "sizeof(vector<bool>)" gives a size of 28 bytes as did
"sizeof(bit_vector)".  My questions, then are,

--Am I better off using vector<bool> or bit_vector if I want a vector of
booleans?

--Am I correct that if space is a concern, I am better off using a "char" than a
"bool" because the former takes one byte and the latter takes four?

Thanks,
Andrew Borthwick

Re: bool

[Per Bothner]

Andrew Borthwick <borthwic@johnson.cs.nyu.edu>:
> I wrote a little test program and found that with the 1997/11/05 snapshot,
> a bool has a size of 4 bytes.

I had thought this was fixed.
If not, it really should be.  sizeof(bool) must be one.
Any other choice will be "unexpected" by reasonable progragrammers.

Whether it takes more time to load a one-byte bool than a 4-byte
or 8-byte bool is irrelevant - otherwise, we should make short
be 4 bytes as well.

While saying that, I do think you may be confused.  You say:

> "sizeof(vector<bool>)" gives a size of 28 bytes as did "sizeof(bit_vector)".

Er - what has sizeof to do with how bits are packed?  Obviously, sizeof
will only tell you the fixed (overhead) size.  If you look at
bit_vector, you will find that it does use 1 bit per bool.

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner

Re: bool

[Jason Merrill]

>>>>> Per Bothner <bothner@cygnus.com> writes:

> Andrew Borthwick <borthwic@johnson.cs.nyu.edu>:
>> I wrote a little test program and found that with the 1997/11/05 snapshot,
>> a bool has a size of 4 bytes.

> I had thought this was fixed.
> If not, it really should be.  sizeof(bool) must be one.
> Any other choice will be "unexpected" by reasonable progragrammers.

> Whether it takes more time to load a one-byte bool than a 4-byte
> or 8-byte bool is irrelevant - otherwise, we should make short
> be 4 bytes as well.

Nonsense.  Most uses of bool are to store boolean values.  Most of these
values would have been type 'int' if 'bool' were not available.  If you
want packed data, you can use a bitvector or 'unsigned char'.

Jason

Re: bool

[Per Bothner]

Jason Merrill <jason@cygnus.com> writes:
> Nonsense.  Most uses of bool are to store boolean values.  Most of these
> values would have been type 'int' if 'bool' were not available.  If you
> want packed data, you can use a bitvector or 'unsigned char'.

Most uses of short are to store integer values.  Most of these
values would have been type 'int' if 'short' were not available.
What's your point?

My point is about user expectations and standardization.
Most users will be surprised if bool takes 4 bytes.
The natural expectation is that bool is one byte.

I people want to pack more than one bool per byte, they can use bitvector.
If they want the fastest type, they can use int.  But the default should
be one byte, at least in structures and arrays (which implies that
sizeof(bool)==1.

I have no problem with the compiler behind the scenes using 4 bytes for
a stand-alone bool auto or static variable.  But not in structs or arrays.

Another (minor) argument concerns Java compatibility:  The Java
Native Interface defines jbool (the C/C++ typedef that matches
thye Java boolean type) as a one-byte unsigned.  This is not
a major issue, since we can always:
	typedef unsigned char jbool;
but it would be nicer to:
	typedef bool jbool;

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner

Re: bool

[Alexandre Oliva]

Per Bothner writes:

> My point is about user expectations and standardization.
> Most users will be surprised if bool takes 4 bytes.
> The natural expectation is that bool is one byte.

The natural expectation is that bool takes one bit.  bool could have
been defined as:

typedef enum {false=0, true=1} mybool;

Enums are represented as integral types large enough to hold their
whole set of values.  AFAIK, gcc won't use a single byte to represent
mybool, so why should it for a bool?

Using int as the underlying type is much faster than anything else
and, if one really wants it to be packed, s/he can use bitfields.

-- 
Alexandre Oliva
mailto:oliva@dcc.unicamp.br mailto:aoliva@acm.org
http://www.dcc.unicamp.br/~oliva
Universidade Estadual de Campinas, SP, Brasil

Re: bool

[Jason Merrill]

>>>>> Per Bothner <bothner@cygnus.com> writes:

> Jason Merrill <jason@cygnus.com> writes:
>> Nonsense.  Most uses of bool are to store boolean values.  Most of these
>> values would have been type 'int' if 'bool' were not available.  If you
>> want packed data, you can use a bitvector or 'unsigned char'.

> Most uses of short are to store integer values.  Most of these
> values would have been type 'int' if 'short' were not available.
> What's your point?

My point is that C programmers use int to store flags.  They could use
short or unsigned char, but they use int.  Removing a 'typedef int bool'
and building with g++ should not make their code slower.

Naive users will use bool for a flag, not considering that it might
dramatically slow down an inner loop in their code.  If a knowledgeable
user wants to save space, they can use unsigned char, or a bitvector, or a
bitfield for that matter.

Basically, this is a space/time tradeoff, and there is no right answer.  My
opinion is that time is more important.  And in any case bool has been 4
bytes on RISC targets for the past couple of years, and I don't think it's
worth changing it now.

Jason

Re: bool

[John Carr]

> Basically, this is a space/time tradeoff, and there is no right answer.  My
> opinion is that time is more important.  And in any case bool has been 4
> bytes on RISC targets for the past couple of years, and I don't think it's
> worth changing it now.

Whatever is decided, no changes should be made until the next time we
break binary compatibility.  It is too late in the release cycle to
change bool now.

bool should be a type which can be loaded with a single instruction.
That means at least 32 bits on Alpha.  On other machines (except
possibly DSPs) I don't think size matters.  I don't expect it to be
any particular size.  If it becomes a char, make it unsigned because
gcc is bad at optimizing out sign/zero extension and signed char is on
average slightly slower than unsigned.

Re: bool

[Torbjorn Granlund]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 421 bytes --]

Having bool a 8-bit quantity does not need to be slower than having it be
the `fastest type', if the tm macro PROMOTE_MODE is set up properly.
PROMOTE_MODE has the effect of widening a type when a quantity of that type
is in a register,

Machines without byte loads/stores would still be hurt, but such machines
are rare.  Even Alpha now has byte loads, although the 21064 and early 21164
did not have them.

Torbjörn

Re:bool

[Andrew Borthwick]

Per Bothner:
> sizeof(bool) must be one.
> Any other choice will be "unexpected" by reasonable progragrammers.

   I totally agree.  This behavior was certainly unexpected by me.

> Er - what has sizeof to do with how bits are packed?  Obviously, sizeof
> will only tell you the fixed (overhead) size.  If you look at
> bit_vector, you will find that it does use 1 bit per bool.

My apologies for a somewhat poor choice of words on the subject of vector<bool>
vs. bit_vector.

     I'm still not entirely clear.  Am I correct that bit_vector gives me
1 bit per bool but vector<bool> does not?  If this is so, couldn't vector be
easily specialized for vector<bool> to give this functionality in a more
standard fashion?

Thanks,
Andrew Borthwick

Re: bool

[Branko Cibej]

Andrew Borthwick wrote:

>     I'm still not entirely clear.  Am I correct that bit_vector gives me
> 1 bit per bool but vector<bool> does not?  If this is so, couldn't vector be
> easily specialized for vector<bool> to give this functionality in a more
> standard fashion?

    There was a long and heated debate about that some time ago in comp.std.c++. I
don't know what the status is now, but at that time the draft standard required
vector<bool> to be specialised so that it used one bit per bool, like bit_vector
does. The central problem was the very same space-vs.-time trade-off we have here.

Personally I think that having two different containers is the correct solution:
vector<bool> for fast access and bit_vector for compact storage -- and you can
always compromise with a vector<unsigned char>.

--
Branko Cibej   <branko.cibej@hermes.si>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
phone: (++386 61) 186 53 49  fax: (++386 61) 186 52 70