Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Efficient way to store a limited number of booleans (http://www.velocityreviews.com/forums/t559735-efficient-way-to-store-a-limited-number-of-booleans.html)

mathieu 12-11-2007 05:13 PM

Efficient way to store a limited number of booleans
 
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 12-11-2007 05:16 PM

Re: Efficient way to store a limited number of booleans
 
On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malaterre@gmail.com> said:

>
> 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;

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)


mathieu 12-11-2007 05:24 PM

Re: Efficient way to store a limited number of booleans
 
On Dec 11, 6:16 pm, Pete Becker <p...@versatilecoding.com> wrote:
> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malate...@gmail.com> said:
>
>
>
> > 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;


s/unsigned/unsigned char/g

Much nicer/cleaner indeed !

Thanks
-Mathieu

Victor Bazarov 12-11-2007 05:31 PM

Re: Efficient way to store a limited number of booleans
 
Pete Becker wrote:
> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malaterre@gmail.com>
> said:
>>
>> 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;


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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask



Victor Bazarov 12-11-2007 05:32 PM

Re: Efficient way to store a limited number of booleans
 
mathieu wrote:
> On Dec 11, 6:16 pm, Pete Becker <p...@versatilecoding.com> wrote:
>> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malate...@gmail.com>
>> said:
>>
>>
>>
>>> 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;

>
> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask



mathieu 12-11-2007 05:37 PM

Re: Efficient way to store a limited number of booleans
 
On Dec 11, 6:32 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> mathieu wrote:
> > On Dec 11, 6:16 pm, Pete Becker <p...@versatilecoding.com> wrote:
> >> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malate...@gmail.com>
> >> said:

>
> >>> 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;

>
> > s/unsigned/unsigned char/g

>
> 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 12-11-2007 05:39 PM

Re: Efficient way to store a limited number of booleans
 
On 2007-12-11 12:31:00 -0500, "Victor Bazarov" <v.Abazarov@comAcast.net> said:

> Pete Becker wrote:
>> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malaterre@gmail.com>
>> said:
>>>
>>> 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;

>
> 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.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)


mathieu 12-11-2007 05:43 PM

Re: Efficient way to store a limited number of booleans
 
On Dec 11, 6:32 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> mathieu wrote:
> > On Dec 11, 6:16 pm, Pete Becker <p...@versatilecoding.com> wrote:
> >> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malate...@gmail.com>
> >> said:

>
> >>> 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;

>
> > s/unsigned/unsigned char/g

>
> 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 12-11-2007 05:52 PM

Re: Efficient way to store a limited number of booleans
 
Pete Becker wrote:
> On 2007-12-11 12:31:00 -0500, "Victor Bazarov"
> <v.Abazarov@comAcast.net> said:
>> Pete Becker wrote:
>>> On 2007-12-11 12:13:39 -0500, mathieu <mathieu.malaterre@gmail.com>
>>> said:
>>>>
>>>> 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;

>>
>> 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.


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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask



Abhishek Padmanabh 12-12-2007 06:02 AM

Re: Efficient way to store a limited number of booleans
 
On Dec 11, 10:13 pm, mathieu <mathieu.malate...@gmail.com> wrote:
> 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>?


All times are GMT. The time now is 08:05 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.