Thread: Bit arrays with STL containers

No worries. I didn't read your reply in that context either. I just hate to misquote. That's all

Originally Posted by Mario F.

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

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

[Of course, for 4, there is no real gain.]

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.

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

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.

Originally Posted by Mario F.

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.

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.

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.

Originally Posted by laserlight

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.