4 ms·

How Fast is Bit Packing?

18 points by ANTSANTS 14y ago

barrkel 14y ago
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).
- vonmoltke 14y ago
  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.
- ANTSANTS 14y ago
  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 http://pastebin.com/ugGnk00p
  - barrkel 14y ago
    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.
    - ANTSANTS 14y ago
      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.
- jrabone 14y ago
  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.
  - barrkel 14y ago
    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.
    - csense 14y ago
      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.

18 points by ANTSANTS 14y ago

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

vonmoltke 14y ago
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.
ANTSANTS 14y ago
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 http://pastebin.com/ugGnk00p
- barrkel 14y ago
  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.
  - ANTSANTS 14y ago
    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.
jrabone 14y ago
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.
- barrkel 14y ago
  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.
  - csense 14y ago
    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.