Bit arrays with STL containers

This is a discussion on Bit arrays with STL containers within the C++ Programming forums, part of the General Programming Boards category; No worries. I didn't read your reply in that context either. I just hate to misquote. That's all...

  1. #16
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,438
    No worries. I didn't read your reply in that context either. I just hate to misquote. That's all
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #17
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by Mario F. View Post
    Some time ago I went through the need to store 4 integrals ranging from 0-10 in the least possible space in memory.
    One thing that struck me was a little different approach.

    You need 4 bits for a value 0-10, true. But that leaves some space "unused" for values 11-15. One way to take advantage of this is to combine more than one of these ranged ints in a larger container. So if you really want to squeeze things, you might find that a 32-bit hunk of memory could contain 8 of these ranged ints if each uses 4 bits; but if you manipulate things a little, you might find that 9 of these ranged ints could fit into a 32-bit unsigned long. I don't know if it's worth the effort, but this is one example of a way to reduce memory footprint by 11&#37;.

    Attached is some code yammerings I've been messing with along this line.

    [Of course, for 4, there is no real gain.]
    Attached Files Attached Files
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #18
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    Typical vectors have three pointers and no size variables. I wonder where your additional two bytes come from.
    For some reason I had it stuck in my head. I think I just had to get it out so it wouldn't clutter up my brain. I really don't know wtf I was thinking. Now that I look at it, it seems like a psychological manifestation of an unconsious need to self sabatoge. My unconsious fear of success is causing me to behave in a manner that will lead me down a path to pain and humiliation. In other words, I knew better and yet still posted crap for some reason.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > [Of course, for 4, there is no real gain.]
    I pointed out earlier that for 4 values, each with 11 possible values, it's possible to store them using 14 bits instead of 16. Unfortunately, extracting the individual values is expensive - it basically involves using &#37; and / to extract digits from what is effectively a base-11 4-digit number - so unless one is really memory-bottlenecked, it's not worth it for a 1/8-th reduction in memory use.

    Edit: On a related subject, the transmission protocol used by radio-controlled clocks, which was devised in the 60s, uses binary-coded decimal, which uses 4 bits per decimal digit, although one actually only needs a little more than 3. Presumably this is because 40 years ago the electronics to do the necessary processing for an efficient encoding was too expensive for home users. So today the transmitter has to use thousands of watts more than necessary, to comply with the old protocol.
    Last edited by robatino; 07-03-2007 at 05:24 AM.

  5. #20
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,438
    Most excellent, Dave!

    It doesn't apply here since the need here is indeed fixed on just 4 segments, each representing an integral between 0 and 10.

    However, you did show me how to do it if that was not the case. Thanks.

    EDIT: On second second, this might be fun to try.
    Last edited by Mario F.; 07-03-2007 at 05:24 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #21
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Quote Originally Posted by Mario F. View Post
    I was totally unaware of that language feature. The section about portability made me wonder though... Do you know of any present problems in their usage among the recent Linux, Mac and Windows flavors?
    Ah... sort of. I mean, the code I posted above creates (on my compilers) a struct of size 2. This on the other hand, is a structure of size 4...
    Code:
    struct pakd {
       unsigned int a:4;
       unsigned int b:4;
       unsigned int c:4;
       unsigned int d:4;
    };
    Oddly enough, this is size 4 on both Visual Studio 2003 and Sun Forte 10 and 11.

    I would expect portability problems if this were a system where the bit placement really mattered, like you were dumping them into a device register. But to be honest, portability issues is par for the course there. For your application, I can't imagine how it would cause a problem since the packing doesn't actually change how your program runs.


    One other thing though... I realize that this is an academic exercise but do you really want to pack this memory? No matter how you do it, it's going to add cycles to your program.
    Callou collei we'll code the way
    Of prime numbers and pings!

  7. #22
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,438
    Yes. I read about that on Stroustrup's. After learning about it I had to go to da Book and check it out. He mentions the performance downgrade and also the code size being increased.

    I don't see the need to use it here since my needs are rather small, other than saving me from the bitwise operators, it will add nothing (or rather, it will add lots ) to what I'm doing. I was just glad I learned about them.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #23
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Oddly enough, this is size 4 on both Visual Studio 2003 and Sun Forte 10 and 11.
    My guess is that unsigned int takes up 4 bytes, so effectively only half of an unsigned int is used. Nonetheless, the struct still takes up 4 bytes.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #24
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Quote Originally Posted by laserlight View Post
    My guess is that unsigned int takes up 4 bytes, so effectively only half of an unsigned int is used. Nonetheless, the struct still takes up 4 bytes.
    Actually, it is odd because for the first time ever, Solaris and Microsoft compilers agree on something.
    Callou collei we'll code the way
    Of prime numbers and pings!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Noob STL question about Containers.
    By Swerve in forum C++ Programming
    Replies: 2
    Last Post: 03-15-2009, 12:02 PM
  2. bit level permutation function
    By zxcv in forum C Programming
    Replies: 2
    Last Post: 07-27-2008, 01:26 PM
  3. bind on member functions of stl containers
    By synss in forum C++ Programming
    Replies: 3
    Last Post: 07-03-2008, 04:38 AM
  4. pointers & arrays and realloc!
    By zesty in forum C Programming
    Replies: 14
    Last Post: 01-19-2008, 03:24 PM
  5. stl - searching for elements in containers
    By Raven Arkadon in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2005, 10:10 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21