How Fast is Bit Packing? | Hacker News Reader

How Fast is Bit Packing?

lemire.me

18 pointsANTSANTS8 comments

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.

[1] http://pastebin.com/ugGnk00p

You don't need to use the routines; the routines are trivial to write. I expect he gets most of his performance from unrolling and cache effects.

My point is rather that if you are in a position to bulk read / write, there is probably a better option.

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.

A real compression algorithm experiences its gain due to low-entropy distribution of the input values.

If your input is randomly distributed integers in the interval [0, 2^n), a bit-packed coding is the most efficient possible.

Reply on news.ycombinator.com