Efficient way to store a limited number of booleans

Discussion in 'C++' started by mathieu, Dec 11, 2007.

  1. mathieu

    mathieu Guest

    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
     
    mathieu, Dec 11, 2007
    #1
    1. Advertising

  2. mathieu

    Pete Becker Guest

    On 2007-12-11 12:13:39 -0500, mathieu <> 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)
     
    Pete Becker, Dec 11, 2007
    #2
    1. Advertising

  3. mathieu

    mathieu Guest

    On Dec 11, 6:16 pm, Pete Becker <> wrote:
    > On 2007-12-11 12:13:39 -0500, mathieu <> 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
     
    mathieu, Dec 11, 2007
    #3
  4. Pete Becker wrote:
    > On 2007-12-11 12:13:39 -0500, mathieu <>
    > 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, Dec 11, 2007
    #4
  5. mathieu wrote:
    > On Dec 11, 6:16 pm, Pete Becker <> wrote:
    >> On 2007-12-11 12:13:39 -0500, mathieu <>
    >> 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
     
    Victor Bazarov, Dec 11, 2007
    #5
  6. mathieu

    mathieu Guest

    On Dec 11, 6:32 pm, "Victor Bazarov" <> wrote:
    > mathieu wrote:
    > > On Dec 11, 6:16 pm, Pete Becker <> wrote:
    > >> On 2007-12-11 12:13:39 -0500, mathieu <>
    > >> 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
     
    mathieu, Dec 11, 2007
    #6
  7. mathieu

    Pete Becker Guest

    On 2007-12-11 12:31:00 -0500, "Victor Bazarov" <> said:

    > Pete Becker wrote:
    >> On 2007-12-11 12:13:39 -0500, mathieu <>
    >> 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)
     
    Pete Becker, Dec 11, 2007
    #7
  8. mathieu

    mathieu Guest

    On Dec 11, 6:32 pm, "Victor Bazarov" <> wrote:
    > mathieu wrote:
    > > On Dec 11, 6:16 pm, Pete Becker <> wrote:
    > >> On 2007-12-11 12:13:39 -0500, mathieu <>
    > >> 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
     
    mathieu, Dec 11, 2007
    #8
  9. Pete Becker wrote:
    > On 2007-12-11 12:31:00 -0500, "Victor Bazarov"
    > <> said:
    >> Pete Becker wrote:
    >>> On 2007-12-11 12:13:39 -0500, mathieu <>
    >>> 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
     
    Victor Bazarov, Dec 11, 2007
    #9
  10. On Dec 11, 10:13 pm, mathieu <> 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>?
     
    Abhishek Padmanabh, Dec 12, 2007
    #10
  11. mathieu

    James Kanze Guest

    On Dec 11, 6:16 pm, Pete Becker <> wrote:
    > On 2007-12-11 12:13:39 -0500, mathieu <> 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;


    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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Dec 12, 2007
    #11
  12. Abhishek Padmanabh wrote:
    > On Dec 11, 10:13 pm, mathieu <> 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>?


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

    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, Dec 12, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kenneth Keeley

    Retirn only a limited number of results.

    Kenneth Keeley, Oct 28, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    291
    Anton Sokolovsky
    Oct 28, 2004
  2. Patrick
    Replies:
    1
    Views:
    374
    pete kirkham
    Aug 22, 2003
  3. Scott

    Number of WebMethods limited in .asmx file?

    Scott, Jul 26, 2004, in forum: ASP .Net Web Services
    Replies:
    0
    Views:
    194
    Scott
    Jul 26, 2004
  4. Replies:
    9
    Views:
    150
    smallpond
    Jan 4, 2010
  5. æœã®æœ¨
    Replies:
    3
    Views:
    1,024
    Juha Nieminen
    Apr 18, 2012
Loading...

Share This Page