Simple batch decoding of unary codes

Unary codes are a form of universal variable-length code (UVLC) that are sometimes used on their own but more commonly used as a building block for more general families of UVLCs like Golomb, Rice or Gamma/Exp-Golomb codes. There are multiple conventions in use, the one I’ll use in the following has codewords terminated with a “1” bit and is 0-based, i.e. the codebook goes

0 -> 11 -> 012 -> 0013 -> 00014 -> 00001

and so forth. That is, some value i is encoded by sending i “0” bits and a single “1” bit at the end. You sometimes see the opposite convention (variable-length run of 1s terminated by a single 0), but having the runs be 0 bits is a bit nicer in code. The main reason is that “count leading/trailing zero bits” instructions are readily available on most machines these days; these can also be used to count leading/trailing ones by doing a bitwise complement first, but that extra work disappears when we use 0s in the first place.

In this post, I want to consider the case where we’re decoding a bunch of unary-coded values in a row. For the sake of concreteness, let’s consider an actual decoder that uses LSB-first bit packing and a Little Endian byte stream, using variant 4 from “Reading bits in far too many ways (part 2)”. That decoder will usually look something like this on a 64-bit platform:

  // refill
  uint64 next = read64LE(bitptr);
  bitbuf |= next << bitcount;
  bitptr += (63 - bitcount) >> 3;
  bitcount |= 56;

  if ((bitbuf & ((1ull << 56) - 1)) == 0) {
      return error("too many 0s in a row");
  }

  // unary code value = trailing zero count
  uint64 code = ctz64(bitbuf);
  decoded[i] = code;

  // consume bits
  // code len=coded value + 1 bit for trailing 1
  uint64 len = code + 1;
  bitcount -= len;
  bitbuf >>= len;

This should be fairly straightforward. Unary codes are usually expected to not be too long, and a common mistake is to not check properly and then run into overflow issues or UB when such inputs show up, hence the explicit limit in this version. Theoretical UVLCs can encode any non-negative integer; in practice, any format I’ve ever seen that doesn’t enforce hard limits has nasty (and frequently exploitable) overflow bugs. If you really do need to support very large codes, I would recommend still writing your loops for the expected case (short runs, unless you’re using a unary code in the wrong place) and treating long runs as an exception that you handle more carefully.

Anyway, back to our topic. The code above works, but it’s relatively expensive. As many bitstream decoding tasks, this is completely serial, and we also have a lot of overhead in the bitstream handling. The unary code corresponds to a geometric distribution with success probability 1/2, so the expected code value works out to 1, and hence the expected number of bits consumed every iteration is 2. But we still need to do the refill handling every iteration because any given code could be a long one.

In the usual setting where unary codes are arbitrarily interleaved with other codes, it’s hard to do much better than this. For example, even a basic Rice code alternates unary prefixes with a fixed-length suffix, and that combination destroys a lot of valuable structure that the constituent parts (namely, unary and fixed-length codes) have on their own. Table-driven decoders can accelerate common cases and even handle multiple symbols at once (provided their codewords are short enough), but often at the cost of increased logistical difficulties, and the fundamentally serial nature of decoding with the critical path through most of the decode stays the same.

By contrast, if we can assume a sequence of pure unary codes with nothing in between, things immediately get simpler. For example, if our bit buffer contains at least 2 set bits, we know that we can decode two code words before needing to refill, which lets us unroll the loop and amortize the refill overhead. This is cheaper than it sounds because this test, using the well-known trick to clear the lowest set bit (if any), boils down to:

  // clear lowest set bit in bitbuf:
  uint64 next = bitbuf & (bitbuf - 1);
  if (next != 0) {
      // we know we have at least two set bits in bitbuf,
      // and can use ctz on "bitbuf" and "next" to determine
      // the next two code values in parallel.
  } else {
      // only one set bit in bitbuf, do single decode as before
  }

This strategy works and does in fact result in an almost perfect 2x speed-up without needing a table-based decode (which would add at least one L1D access’s worth of time to the critical path between iterations), but I won’t spend any more time on this here, because with a pure unary code stream, we also have a much better option.

Tunstall-style decoding

Prefix codes map from a known input alphabet to variable-sized (in general) code words. Tunstall coding is the dual approach that maps a variable number of input symbols to code words of a fixed size. Decoding typically uses a table that has space for the maximum number of symbols emitted, plus their count.

Unary codes are not actually a “natural” Tunstall code; code words can get arbitrarily long. But it’s trivial to “glue them together”. Let’s see what happens when we try to just grab a fixed number of bits—8 being the most convenient choice by far, since it means we just process bytes at a time—and attempt to do a table-based decode. I’ll write our 8 individual bits from left to right and label them with letters so you can follow along for the explanation below:

0,1,1,0, 0,1,0,0a b c d  e f g h

Suppose we don’t remember what came before it, and we haven’t yet looked at what comes after that byte. What can we say about these unary code values?

At position “a”, our current run of zeros gets extended by 1, and at position “b”, we have the end of a code. We don’t know what the actual value being coded is; that depends on how many 0s preceded this byte, which we pretend to not remember for now. We’ll get back to this.

At position “c”, we have another 1 bit, immediately after “b”, so we know that’s for sure a value of 0. Likewise, at “f”, we have another 1, and this one was preceded by two “0” bits, so we also know with certainty that it’s the end of a codeword for the value 2. Finally, positions “g” and “h” start a run of at least 2 zero bits, but we don’t know how long it’s going to get until we look at the next byte (and possibly more bytes after that).

Okay, so we don’t quite have a regular Tunstall code, because we need some sort of carried state between codewords. But it’s not far off: from those 8 bits, we can definitely tell that we’re going to get 3 values out of decoding this byte, we know how many extra 0s need to get added to the tally before emitting that first code, and we know how many 0s we had left over at the end that will go into some future code that terminates at the next “1” bit in the stream, wherever that ends up being.

Note that each unary code (in our formulation) contains exactly one “1” bit, so the number of code words emitted is always the same as the population count of the input byte.

What this tells us is that we can build a 256-entry table that encodes what to do with each byte value. In that table, we store up to 8 small integers (uint8 is plenty, since the actual values contained in the table are all below 8) and the “carry-out” (the length of the final run of 0s that hasn’t found a 1 yet). We also either store the number of output values or calculate it via a “population count” instruction, if available. One special case: every byte value that’s non-0 has at least one value emitted from it, meaning the “carry” gets reset somewhere in the middle. If the byte is 0, however, the current run of 0s extends by another eight bits without emitting a code. Putting this all together, we get a decoder loop that looks something like this:

  uint8 byte = *bitptr++;
  if (byte != 0) {
      // at least 1 bit set -> we emit values
      TableEntry tab = g_unary_table[byte];

      // first value has carry added
      decoded[i] = carry + tab.value[0];

      // remaining values are copied directly
      for (j = 1; j < tab.count; j++) {
          decoded[i + j] = tab.value[j];
      }

      i += tab.count;
      carry = tab.carry;
  } else {
      // run of zeros: no code emitted just yet,
      // add 8 to current carry
      carry += 8;
      if (carry >= 57) {
          return error("too many 0s in a row");
      }
  }

That give us a different way of accomplishing the same thing we already had. But this one doesn’t involve any variable bit IO. And while it looks more complicated, it actually has a lot of potential for further simplifications.

The optimized version

This time, I’ll give the final version first, and then explain the changes to get there:

  uint8 byte = *bitptr++;
  if (byte != 0) {
      uint64 values = g_unary_table[byte];
      // emit values from table, adding carry into the first value (bottom byte)
      write64LE(decoded + i, values + carry);
      // next carry is in top byte of table
      carry = values >> 56;
      // number of values emitted is the population count
      i += popcnt32(byte);
  } else {
      carry += 8;
      if (carry >= 57) {
          return error("too many 0s in a row");
      }
  }

First, I made the table just be a table of uint64 values, and assume that decoded is an array of bytes with a bit of padding, so we can safely overshoot the expected number of code values by at least 7 without writing out of bounds.

Second, I am explicitly writing these up to 8 values using a single Little Endian 64-bit write. Third, the first value being emitted, which needs the carry correction, is in the low-order byte of values, so we can simply add carry to values to do the correction. The values contained in the table are never larger than 7 (because the first set bit in the byte can have at most seven 0s preceding it before we run out of bits in the byte!) and carry is guaranteed to be less than 57. The table values for carry are also at most 7 and the byte == 0 case explicitly ensures that it doesn’t get larger than that. Therefore, this addition never overflows out of the low byte.

Finally, fourth, we store the next carry value in the top byte of the table entry, purely so our table entries don’t need to get bigger than a single uint64. This looks a bit weird at first glance: can’t we have 8 values from the same byte, if the byte was all-1 bits, i.e. 0xff? Indeed, we can, but that is the only case where we emit 8 values, and in that case the 8 values being emitted are 0 and the carry is also 0. So yes, the two table fields are double-booked in that one case, but since they contain the same value, it doesn’t matter.

Okay, that’s a pretty short decoder loop, and it’s an interesting approach, but what did that buy us?

Well, this turns out to be much faster than the one-at-a-time decoder. The one-at-a-time decoder produces one value per iteration. This one consumes input bits at a fixed rate of eight bits per iteration, and assuming these bits are approximately uniformly distributed (as they should be, unless you’re using the unary code in a setting where it’s inappropriate), the expected number of set bits in each byte is four, meaning that each iteration of our loop averages four values written, not just one.

Does this mean we should expect around a 4x speed-up over the one-at-a-time version?

Actually, no! Because this formulation has an ace up its sleeve. Note that it always consumes a single input byte each iteration, and advances the input cursor by one byte. And the relatively-high-latency table access (usually on the order of 4-5 cycles for a L1 hit these days, compared to 1 cycle latency for an arithmetic operation) only depends on the byte value we loaded, and not on anything else in this loop.

If we look at the dataflow graph for the whole process, note that the critical paths for the loop-carried variables go as follows:

• bitptr (the input cursor) just keeps adding 1 to previous iteration’s value; 1 cycle latency. An out-of-order CPU will know, within a single cycle of starting the current iteration, where to fetch the byte for the next iteration.
• carry for the next iteration depends on values for this iteration (loaded from the table), but the only thing it does it get added to the new values in the next iteration. In the common path (when the byte read wasn’t 0, which occurs about 99.6% of the time) there’s a new definition of carry every loop iteration. The only thing that depends on this iteration’s carry is the next iteration’s store, subsequent iterations don’t care, so carry actually isn’t on the critical path at all.
• i, the output index, gets incremented by the population count of byte, but all the byte loads are independent of each other (they only depend on bitptr), and i only flows into the stores, which nothing directly depends on. The length of the carried dependency is only the length of the add, 1 cycle again. The remaining latency is off the critical path; we might need to pipeline across several iterations to hide the latency of the population count, but there’s nothing that stops out-of-order CPUs from doing exactly that.

In short, the critical iteration-to-iteration path for this decoder is a single clock cycle! There’s a lot more work that happens, but it’s not on the critical path to starting new iterations; an out-of-order CPU with sufficient potential for instruction-level parallelism can go hog wild on this loop.

What does this mean in practice? Well, I benchmarked both the Tunstall-style decoder and the one-at-a-time decoder above, and on my home machine (a Zen 4 CPU), the Tunstall-style decoder is approximately 9x faster. We’re not talking small fry here; the difference is substantial.

So what?

This may seem like a random curiosity, but it’s not, because there’s something much deeper at play here.

Over the past three decades or so, we’ve gotten huge increases in computing power, but they’re all critically dependent on parallelism. Be it instruction-level parallelism that is what out-of-order CPUs set out to extract, thread-level parallelism that is unlocked by multi-core CPUs, or the massive exploitation of data parallelism that is at the heart of GPUs and SIMD instruction sets.

One thing I’ve kept running into during the past 10 years is that we have ridiculous amounts of compute power available to us, but a lot of our data formats are set up all wrong to benefit from any of it. It’s not like nobody is noticing – if you look at say the VLDB conferences, there’s been a steady stream of papers figuring out ways to put all those sources of parallelism to use for the past several decades – but it feels like large parts of the data compression and “data wrangling” world dealing with (de)serialization are stuck in the same rut they’ve been in since at least the 1970s, with variable-sized encodings that mix everything into a single stream absolutely everywhere. At best, these take heroics to extract a little parallelism; more commonly, it’s either not possible, or at least not economical, to do so at all.

What this post is trying to demonstrate, more than anything else, is just how much we’re giving up by approaching things this way. Granted, there are other factors at play than speed here, but I would argue that not only is the Tunstall-style decoder for unary codes simpler, it is also easier to make safe, and at lower relative cost. Decoding multiple values per iteration means that any bounds-checking overhead etc. is automatically amortized, so there’s much less incentive to try something fancy and subtle that might backfire later. And note we didn’t even do any SIMD or threading to get there! We got around 4x just from an approach more suited to the problem (to wit, most unary codewords are really short, so we want something that can benefit from this) and more than another 2x just because that new approach happens to also play to the strengths of current machines, whereas fully serial decoding very much does not.

Going back to the motivating examples: straight unary codes are probably not something you see a lot. But something like Rice codes or Exp-Golomb/Gamma codes does show up in scenarios like database indices and posting lists.

There are slick decoders for these that are almost exactly the same cost as just the unary decode portion. I’ve posted about some of these long ago. But you have many more options once you split them into their constituent pieces.

For Rice codes, they decompose into a unary prefix and a fixed-size suffix. As this post shows, we can decode a bunch of pure unary values much quicker than we can a stream that also has other data inside it. A batch of fixed-size codewords is likewise trivial (and can even support arbitrary random access). So, if we have a lot of Rice-coded values, it’s a very good idea to separate out the unary prefix portion from the suffix portion, splitting the whole process into 1. decoding all the unary prefixes in one go and 2. running an extra pass that glues on the suffix bits; this extra pass has completely linear memory access patterns, no data-dependent control flow, and is trivial to optimize.

Something like Exp-Golomb is a bit more complicated, because the suffix portion is variable length, but note that separating the two halves pays dividends here too: knowing all the lengths up front means the suffix loop is not constantly waiting for a L1D memory access to count-leading-zero operation or similar to finish. We once again end up with a loop where we only add a number to a bit position as a loop-carried dependency and everything else can overlap. Or, if we want to get more ambitious, we can realize that we can determine many “bit read” offsets in parallel once we have the predetermined lengths in an array, because now we can do a prefix sum computation on the lengths to get the exact position in the bit stream where each value’s suffix bits start. And suddenly we have something that is amenable to SIMD implementation. (Oodle has been using this approach on parts of the Kraken bitstream for 10 years now.)

Don’t get me wrong, I don’t mean to suggest that everything needs to look this way, but I keep seeing serialization formats that don’t even consider this kind of approach at all, as well as a steady stream of people discovering just how much room for improvement there really is from either changing implementations of wire formats to use more parallelism-friendly approaches or changing these formats to be less inherently serial in the first place.

Not everything needs to be particularly optimized, and batch processing is not suitable for every task, but it is simply astonishingly effective on current computing hardware, and sadly under-utilized.

Appendix: table generation

I did not put this in the body text because it’s fairly straightforward and I wanted to concentrate on the way the decoder works, but for what it’s worth, here’s how the tables for my test program were generated:

  for (int byte = 0; byte < 256; byte++)
  {
      U64 remainder = byte | 256; // add a dummy 1 bit at top
      U64 shift = 0;
      U64 table_entry = 0;

      for (;;)
      {
          // determine next code value (we always have a set bit,
          // so this always works)
          U64 code = ctz64(remainder);

          // shift that bit out
          remainder >>= code + 1;

          if (remainder == 0)
          {
              // if there was only 1 set bit left, that's the sentinel
              // we inserted; our code is the carry.
              //
              // if and only if byte==255, we already have a real value
              // at that position, but in that case, both that final
              // value and the carry are 0, so it doesn't matter.
              table_entry |= code << 56;
              break;
          }
          else
          {
              // not yet done; add this value to the list
              table_entry |= code << shift;
              shift += 8;
          }
      }

      g_unary_table[byte] = table_entry;
  }