Variable Sized Integers

Remco Bloemen

2014-02-27

In this article I’ll show different methods to compactly encode integers which are likely to be small. In the process I’ll show some neat bit-fiddeling techniques and I’ll try to develop a coding that is both faster and denser.

Existing work

Variable sized integer codings are used in several existing projects, usually when very efficient use of storage space is required and large values can occur but small values are much more frequent. Typical cases would be content sizes, or anything that follows a power-law distribution, which according to Zipf’s law happens very often. I’ll start by showing three well-known variable integer coders.

EBML (Matroska)

The Matroska file format, with file extenstion .mkv, is a popular choice for high definition video content. Matroska is a modern and flexible container format based on the EBML specification. An EBML formatted file consists of a stream of key, size, value triples known as ‘tags’. Here the key is an one to four byte identifier and the size is the varint encoded length of the value. These tags can be nested, making the format heirarchical and easily extended.

The varint is between 1 and 9 bytes, the most significant bits of the first byte determine the total number of bytes used in the encoding.

EBML varint format:

value encoded as
< 2⁷ 1xxx xxxx₂
< 2¹⁴ 01xx xxxx xxxx xxxx₂
< 2²¹ 001x xxxx xxxx xxxx xxxx xxxx₂
< 2²⁸ 0001 xxxx xxxx xxxx xxxx xxxx xxxx xxxx₂
< 2⁶⁴ 0000 0001 xxxx xxxx …(48 bits)… xxxx xxxx₂

Note

EBML uses this format to encode tags and field sizes, not to encode integer valued fields. For example, encoding an integer valued field with value 123₁₆ would result in a size of two bytes, which is varint encoded as 02₁₆ and then prefixed to the integer’s bytes giving the output 020123₁₆. Since the size is 0–8 bytes, which is always encoded as a single byte, the net effect is a one-byte prefix.

The varint coder is defined in EbmlElement.cpp, but the original code is too complicated to show it here. It contains special cases for the end of the read/write buffer, some minor variants for signed integers and special values, but is is also rather entangled with other functions. I will therefore show a simplified version, with my own variable names and comments to clarify. I did not try to optimize the functions. Please rever to the original sourcecode at the links above before making any judgements.

EBML write function (simplified).

Higher cases where marked marked as “TODO” in original code

EBML read function (simplified).

Google Protocol Buffers

Google Protocol Buffers is designed as a highly efficient alternative to xml for data exchange between processes and data storage. It is apparently the default remote procedure call protocol for Google’s internal software, so one can assume that the code is very well designed and povides a significant improvement over existing alternatives. A fundamental part of the specification are “base 128 varints”. These varints are the default encoding format for integer field types and they are used to encode data lengths.

The varint format consist of groups of eight bits, bytes. The most significant bit in each byte is a flag that is one when more groups are comming and zero if this is was the last group. The other seven bits are part of the encoded number, but counterintuitively the format starts with the least significant group of seven bits first.

Google Protocol Buffers varint format:

value encoded as
< 2⁷ 0xxx xxxx₂
< 2¹⁴ 1xxx xxxx 0xxx xxxx₂
< 2²¹ 1xxx xxxx 1xxx xxxx 0xxx xxxx₂
< 2²⁸ 1xxx xxxx 1xxx xxxx 1xxx xxxx 0xxx xxxx₂
< 2⁶⁴ 1xxx xxxx 1xxx xxxx …(48 bits)… 0xxx xxxx₂

The code has some special cases at the end of the buffer and for 32-bit and signed integer which I will not go into. When the pointer is not to close to the end of the buffer then the encoding is done using Coded​Input​Stream​::​Read​Varint​64​Fallback and the decoding is done using Coded​Output​Stream​::​Write​Varint​64​To​Array​Inline. The functions are defined as follows:

Google Protocol Buffers writer.

inline uint8* CodedOutputStream::WriteVarint64ToArrayInline(
    uint64 value, uint8* target)
{
    // Splitting into 32-bit pieces gives better performance on 32-bit
    // processors.
    uint32 part0 = static_cast<uint32>(value      );
    uint32 part1 = static_cast<uint32>(value >> 28);
    uint32 part2 = static_cast<uint32>(value >> 56);

    int size;

    // Here we can't really optimize for small numbers, since the value is
    // split into three parts.  Cheking for numbers < 128, for instance,
    // would require three comparisons, since you'd have to make sure part1
    // and part2 are zero.  However, if the caller is using 64-bit integers,
    // it is likely that they expect the numbers to often be very large, so
    // we probably don't want to optimize for small numbers anyway.  Thus,
    // we end up with a hardcoded binary search tree...
    if (part2 == 0) {
        if (part1 == 0) {
            if (part0 < (1 << 14)) {
            if (part0 < (1 << 7)) {
                size = 1; goto size1;
            } else {
                size = 2; goto size2;
            }
            } else {
            if (part0 < (1 << 21)) {
                size = 3; goto size3;
            } else {
                size = 4; goto size4;
            }
            }
        } else {
            if (part1 < (1 << 14)) {
            if (part1 < (1 << 7)) {
                size = 5; goto size5;
            } else {
                size = 6; goto size6;
            }
            } else {
            if (part1 < (1 << 21)) {
                size = 7; goto size7;
            } else {
                size = 8; goto size8;
            }
            }
        }
    } else {
        if (part2 < (1 << 7)) {
            size = 9; goto size9;
        } else {
            size = 10; goto size10;
        }
    }
    
    GOOGLE_LOG(FATAL) << "Can't get here.";
    
    size10: target[9] = static_cast<uint8>((part2 >>  7) | 0x80);
    size9 : target[8] = static_cast<uint8>((part2      ) | 0x80);
    size8 : target[7] = static_cast<uint8>((part1 >> 21) | 0x80);
    size7 : target[6] = static_cast<uint8>((part1 >> 14) | 0x80);
    size6 : target[5] = static_cast<uint8>((part1 >>  7) | 0x80);
    size5 : target[4] = static_cast<uint8>((part1      ) | 0x80);
    size4 : target[3] = static_cast<uint8>((part0 >> 21) | 0x80);
    size3 : target[2] = static_cast<uint8>((part0 >> 14) | 0x80);
    size2 : target[1] = static_cast<uint8>((part0 >>  7) | 0x80);
    size1 : target[0] = static_cast<uint8>((part0      ) | 0x80);
    
    target[size-1] &= 0x7F;
    return target + size;
}

Google Procol Buffers reader.

bool CodedInputStream::ReadVarint64Fallback(uint64* value) {
    if (BufferSize() >= kMaxVarintBytes ||
        // Optimization:  If the varint ends at exactly the end of the buffer,
        // we can detect that and still use the fast path.
        (buffer_end_ > buffer_ && !(buffer_end_[-1] & 0x80))) {
        // Fast path:  We have enough bytes left in the buffer to guarantee that
        // this read won't cross the end, so we can skip the checks.
        
        const uint8* ptr = buffer_;
        uint32 b;
        
        // Splitting into 32-bit pieces gives better performance on 32-bit
        // processors.
        uint32 part0 = 0, part1 = 0, part2 = 0;
        
        b = *(ptr++); part0  = (b & 0x7F)      ; if (!(b & 0x80)) goto done;
        b = *(ptr++); part0 |= (b & 0x7F) <<  7; if (!(b & 0x80)) goto done;
        b = *(ptr++); part0 |= (b & 0x7F) << 14; if (!(b & 0x80)) goto done;
        b = *(ptr++); part0 |= (b & 0x7F) << 21; if (!(b & 0x80)) goto done;
        b = *(ptr++); part1  = (b & 0x7F)      ; if (!(b & 0x80)) goto done;
        b = *(ptr++); part1 |= (b & 0x7F) <<  7; if (!(b & 0x80)) goto done;
        b = *(ptr++); part1 |= (b & 0x7F) << 14; if (!(b & 0x80)) goto done;
        b = *(ptr++); part1 |= (b & 0x7F) << 21; if (!(b & 0x80)) goto done;
        b = *(ptr++); part2  = (b & 0x7F)      ; if (!(b & 0x80)) goto done;
        b = *(ptr++); part2 |= (b & 0x7F) <<  7; if (!(b & 0x80)) goto done;
        
        // We have overrun the maximum size of a varint (10 bytes).  The data
        // must be corrupt.
        return NULL;
        
    done:
        Advance(ptr - buffer_);
        *value = (static_cast<uint64>(part0)) |
            (static_cast<uint64>(part1) << 28) |
            (static_cast<uint64>(part2) << 56);
        return true;
    } else {
        return ReadVarint64Slow(value);
    }
}

Looking at the comments, a lot of thought went into the performance. Loops are unrolled and the code is filled with goto’s.

Unicode

This list would not be complete without to of the most popular variable sized integer coders, UTF-8 and UTF-16. Yes, that’s right, these unicode encodings can also be seen as varint coders. They encode the valid unicode codepoints in the range 0–10FF₁₆ to sequences of bytes or words.

UTF-8 format:

value encoded as
< 2⁷ 0xxx xxxx₂
< 2¹¹ 110x xxxx 10xx xxxx₂
< 2¹⁶ 1110 xxxx 10xx xxxx 10xx xxxx₂
< 2²¹ 1111 0xxx 10xx xxxx 11xx xxxx 10xx xxxx₂

This format is a lot less size efficient than the previous ones, but it satisfies a few additional constraints due to ascii compatibility. Values less than 127, the ascii values, are encoded as themselves and non ascii values are encoded using only non-ascii bytes. Furthermore the start of a sequence can always be identified by the bitstring 11xx xxxx, this allows a decoder to resynchronize on a corrupt bitstream.

The UTF-16 format has a preprocessing step, if the value is higher than 10000₁₆ then 10000₁₆ is subtracted from the value befor encoding using the pattern in the second row otherwise the value is written out plainly:

UTF-16 format:

value encoded as
< 2¹⁶ xxxx xxxx xxxx xxxx₂
< 2²⁰ 1110 10xx xxxx xxxx 1110 11xx xxxx xxxx₂

To let the decoder identify between the first and second row, the first row must not start with 1110 10₂! With a nice disregard for sepparation of concerns the Unicode standard was modified to exclude the whole range 1110 1xxx xxxx xxxx solely for UTF-16. In fact, UTF-8 originally went up to 31 bits, but was limited to 21 bits to conform with UTF-16.

Improving

One can learn a few things from the the three formats above. The EBML and UTF-8 format have the advantage that the the total number of bytes to read is known after the first byte is read, the Google format lacks this advantage. However, Google’s format shares with UTF-8 that values less than 127 are encoded as themselfs, this is fundamental to the ascii-compatibility of UTF-8. There are both pro’s and con’s to this approach, the pro is that users with non-unicode tools might be able to read the file, the con is that user might not feel inclined to update their tools untill something breaks horribly.

I personally shun backwards compatibility, it often does more harm than good. Besides, a non compatible solution saves me one instruction on my processor. Therefore my format will be the same as EBML’s. (Should you want the backwards compatibility, you can reverse the ones and zeros in the prefix and modify the source accordingly).

custom varint format:

value encoded as
< 2⁷ 1xxx xxxx₂
< 2¹⁴ 01xx xxxx xxxx xxxx₂
< 2²¹ 001x xxxx xxxx xxxx xxxx xxxx₂
< 2²⁸ 0001 xxxx xxxx xxxx xxxx xxxx xxxx xxxx₂
< 2⁶⁴ 0000 0001 xxxx xxxx …(48 bits)… xxxx xxxx₂

Loop free, almost branch free

Now that the format is settled, how are we going to encode/decode it efficiently? The EBML implementation is filled with loops within loops, that can never be efficient. The Google one solves this by unrolling the loop and jumping into it using a decission tree. But both solution still require conditional branching wich can cause branch misprediction and the associated performance penalty of ten to twenty cycles.

So I would like to avoid fors and’ ifs where possible. And in fact this can be done to a large degree! Using GCC’s builtin function __builtin_clzll we can quickly count the number of zero bits left of the most significant one bit. Another usefull function is builtin_bswap64, which converts between little-endian and big-endian. I’ve wrapped the builtin functions in leading_zeros and byte_swap so one can provide compiler independent implementations for them. Additionally GCC’s __builtin_clzll is undefined for the value zero, which I would like to be set to 64. Testing shows that in practice it returns zero on zero input, the following corrects that:

I have also defined two macro’s, expect_false and expect_true which give the compiler a clue about wich branch is more likely, these are purely optional. With these functions one can construct the following variabel integer encoder for the format given above:

Line 2 calculates the number of bytes required using that we encode the value in groups of seven bits. The number of bits in to write down a value xx in binary is log2x\lfloor \log_2 x\rfloor . Note that leading_zeros returns the value 64log2x64 - \lfloor \log_2 x\rfloor . Which gives the following derivation for the number of seven bit blocks required:

log2x7964log2x7 \lceil \frac{\lfloor \log_2 x\rfloor }7 \rceil ≟ 9 - \lfloor \frac{64 - \lfloor \log_2 x\rfloor }7 \rfloor

Lines 4–9 handle the case where the encoded value fits in a uint64. Line 4 shifts the value to the most significant bytes. Line 5 adds the one bit that marks the number of bytes. Line 6 converts the in memory representation from little-endian to big-endian. Line 7 writes the eight bytes of value in one go by reinterpreting the buffer as an uint64 array. This will always write eight bytes to the buffer, but we have the assumption that this is can always be done. Line 8 increments the buffer pointer by the correct amount.

Lines 11–15 handle the very large value case, which is unlikely to happen. An all-zero prefix byte is written and the big endian value is written in one go.

Removing ambiguity

Optimizing the Google format.

Benchmarking

Written size

Writing time

Reading time