I've implemented bit packing because I wanted to store a large array of integers (actually, indexes to another array) in memory and have efficient random access over them.
But what is shown implemented here is more like a compression / decompression routine, because it's predicated on the idea you want to read / write long strings of numbers. If that's the case, it's probably better to use a cheap and fast stream compression algorithm - you'll lose some speed, but likely gain significant space (depending on data of course).
I have used it extensively for both memory reduction and message size reduction. In the latter case, we had fixed-size messages with multiple components, so packing the values made more sense. We had things like custom floating-point formats, encodings that packed X n-bit integers into Y 32-bit integers, common exponent encodings, and other stuff.
Many of those encodings and packings, particularly for the fixed-size messages, used structure bitfield magic. We has a few variable-sized messages too, though, where I had to do things like what the OP did.
If you look at the code[1], there is basically a special cased/"unrolled" pack and unpack routine for each "bit size" integer that is not already machine addressable. Each routine seems (disclaimer: I didn't check all of them) to operate on the lowest common multiple of words between "bit size" and word size.
I believe he wrote the rest of the program as a benchmark for his "chunk oriented" routines using large amounts of data. It doesn't make the pack and unpack routines any less suited to processing small amounts of data.
With a little work, you could use those routines to allow random access to a large packed array with a small buffer -- in the simplest implementation, calculate if the integer you're trying to address is in the buffer, if not, unpack the correct chunk and overwrite the buffer with it.
I think the author knows there are better options for compressing large streams, but still chose to use the situation as a simple benchmark to test the performance of his (admittedly trivial) packing and unpacking routines.
You're right that the benchmark is biased due to cache effects/etc from processing in a large stream, however. A more honest (and useful) benchmark would be to test the performance of packed and unpacked integers under a random access pattern.
Depends a lot on your data. Our custom bit packed compression scheme is ten times smaller than protobufs using Google varint and about half the size of bzip2. We have a very specific, well-understood domain for these numbers and a lot of data to collect over limited bandwidth.
Bit packing in the normal fashion as in the article - where you assume an exact bit length for all elements - isn't normally optimal. Arithmetic coding can use fractional bits, but bit backing forces you to a power of 2 domain.
8 comments
[ 3.4 ms ] story [ 28.9 ms ] threadBut what is shown implemented here is more like a compression / decompression routine, because it's predicated on the idea you want to read / write long strings of numbers. If that's the case, it's probably better to use a cheap and fast stream compression algorithm - you'll lose some speed, but likely gain significant space (depending on data of course).
Many of those encodings and packings, particularly for the fixed-size messages, used structure bitfield magic. We has a few variable-sized messages too, though, where I had to do things like what the OP did.
I believe he wrote the rest of the program as a benchmark for his "chunk oriented" routines using large amounts of data. It doesn't make the pack and unpack routines any less suited to processing small amounts of data.
With a little work, you could use those routines to allow random access to a large packed array with a small buffer -- in the simplest implementation, calculate if the integer you're trying to address is in the buffer, if not, unpack the correct chunk and overwrite the buffer with it.
[1] http://pastebin.com/ugGnk00p
My point is rather that if you are in a position to bulk read / write, there is probably a better option.
You're right that the benchmark is biased due to cache effects/etc from processing in a large stream, however. A more honest (and useful) benchmark would be to test the performance of packed and unpacked integers under a random access pattern.
If your input is randomly distributed integers in the interval [0, 2^n), a bit-packed coding is the most efficient possible.