Efficient way to store a limited number of booleans

[mathieu]

Hi,

I was trying to make an entry in a std::map be stored more
efficiently. The struct contained 3 booleans discribing it's property,
so I am trying to make it as compact as possible.
Using a std::vector<bool> in this case does not work, or at least is
not as efficient for my particular case (size was 20 bytes). Same goes
for tr1::array<bool,3>.

Is there anything else that I could have reused ?

Here is the current code:

// Compact struct to store up to 8 booleans:
struct B3
{
template <unsigned int TPos>
void SetB(bool v) {
if( v ) b.b |= (0x80 >> TPos%8);
else b.b &= (~(0x80 >> TPos%8));
}
template <unsigned int TPos>
bool GetB() const {
return b.b & (0x80 >> (TPos%8));
}
private:
union { unsigned char b; } b;
};

Thanks
-Mathieu

 

[Pete Becker]

Is there anything else that I could have reused ?

Let the compiler do the work:

struct eight_bools
{
unsigned bool0 : 1;
unsigned bool1 : 1;
unsigned bool2 : 1;
unsigned bool3 : 1;
unsigned bool4 : 1;
unsigned bool5 : 1;
unsigned bool6 : 1;
unsigned bool7 : 1;
};

eight_bools data = { 0 };
data.bool6 = true;
data.bool6 = false;

 

[mathieu]

Let the compiler do the work:

struct eight_bools
{
unsigned bool0 : 1;
unsigned bool1 : 1;
unsigned bool2 : 1;
unsigned bool3 : 1;
unsigned bool4 : 1;
unsigned bool5 : 1;
unsigned bool6 : 1;
unsigned bool7 : 1;

};

eight_bools data = { 0 };
data.bool6 = true;
data.bool6 = false;

s/unsigned/unsigned char/g

Much nicer/cleaner indeed !

Thanks
-Mathieu

 

[Victor Bazarov]

Let the compiler do the work:

struct eight_bools
{
unsigned bool0 : 1;
unsigned bool1 : 1;
unsigned bool2 : 1;
unsigned bool3 : 1;
unsigned bool4 : 1;
unsigned bool5 : 1;
unsigned bool6 : 1;
unsigned bool7 : 1;
};

eight_bools data = { 0 };
data.bool6 = true;
data.bool6 = false;

I am not sure about this, but I believe I've seen the compilers
that were making the object of any class type to have enough
padding to bring its size to divisible by some power of 2, and
it wasn't 1; it was more like 4. Not to say you can't control
it, of course...

What I'd probably do is to code a custom map which would do all
the 'map' thing but instead of storing an array of bool or even
a struct with bit fields, I'd make it store a char and when it
comes to manipulating that char, I'd have a proxy object that
can set and interrogate the respective bits in the stored char.

Whether it would constitute savings I am not sure, depends on
the implementation of 'map', I think.

V

 

[Victor Bazarov]

s/unsigned/unsigned char/g

Does it make a real difference? I mean, did you check the
'sizeof' for the resulting struct?

Much nicer/cleaner indeed !

V

 

[mathieu]

Does it make a real difference? I mean, did you check the
'sizeof' for the resulting struct?

At least on gcc 4.1.2 (debian) it does. With unsigned int I get 4
(obviously) and with unsigned char I get 1 as expected (same size as
my solution but cleaner).


-Mathieu

 

[Pete Becker]

I am not sure about this, but I believe I've seen the compilers
that were making the object of any class type to have enough
padding to bring its size to divisible by some power of 2, and
it wasn't 1; it was more like 4. Not to say you can't control
it, of course...

What I'd probably do is to code a custom map which would do all
the 'map' thing but instead of storing an array of bool or even
a struct with bit fields, I'd make it store a char and when it
comes to manipulating that char, I'd have a proxy object that
can set and interrogate the respective bits in the stored char.

Whether it would constitute savings I am not sure, depends on
the implementation of 'map', I think.

It also depends on the definition of "savings." It took less time to
write this code than it took to write the description of your version.

 

[mathieu]

Does it make a real difference? I mean, did you check the
'sizeof' for the resulting struct?

Actually you are raising a good point. Shouldn't I be doing:


struct eight_bools
{
bool bool0 : 1;
bool bool1 : 1;
bool bool2 : 1;
bool bool3 : 1;
bool bool4 : 1;
bool bool5 : 1;
bool bool6 : 1;
bool bool7 : 1;
};

Thanks
-Mathieu

 

[Victor Bazarov]

It also depends on the definition of "savings." It took less time to
write this code than it took to write the description of your version.

Absolutely. It's sometimes faster to compare and swap all elements
in an array than to call 'std::sort' for it. And if we had some
specific definition of savings, we'd still be wearing animal skins
and living in caves...

V

 

[Abhishek Padmanabh]

Hi,

I was trying to make an entry in a std::map be stored more
efficiently. The struct contained 3 booleans discribing it's property,
so I am trying to make it as compact as possible.
Using a std::vector<bool> in this case does not work, or at least is
not as efficient for my particular case (size was 20 bytes). Same goes
for tr1::array<bool,3>.

Is there anything else that I could have reused ?

Here is the current code:

// Compact struct to store up to 8 booleans:
struct B3
{
template <unsigned int TPos>
void SetB(bool v) {
if( v ) b.b |= (0x80 >> TPos%8);
else b.b &= (~(0x80 >> TPos%8));
}
template <unsigned int TPos>
bool GetB() const {
return b.b & (0x80 >> (TPos%8));
}
private:
union { unsigned char b; } b;
};

How about using std::bitset<3>?

 

[James Kanze]

Let the compiler do the work:

struct eight_bools
{
unsigned bool0 : 1;
unsigned bool1 : 1;
unsigned bool2 : 1;
unsigned bool3 : 1;
unsigned bool4 : 1;
unsigned bool5 : 1;
unsigned bool6 : 1;
unsigned bool7 : 1;
};

eight_bools data = { 0 };
data.bool6 = true;
data.bool6 = false;

If he's putting this into a map, it probably won't take anymore
data space than a tr1::array< bool >, or a bool[3]. (I think he
said he only had three bools.) Whatever structure he uses will
be placed in a map node, which will also contain the key and a
couple of pointers. And be aligned and padded for pointers, at
least---on a typical machine, that means that anything less than
four bytes will in fact occupy four (or eight) bytes.

In fact, using the tr1::array<bool> will actually result in a
small space saving, because the size of the code needed to read
and write the values will be smaller.

If there's more data than just the 3 bool's, of course, bit
fields may be just the solution. Throw in a couple of ints with
very limited ranges, and the size gain can be very significant.

But of course, if he's worried about memory use, std::map may
not be the data structure he needs.

 

[Victor Bazarov]

How about using std::bitset<3>?

What is 'sizeof(std::bitset<3>)' on your machine? Just curious...

V