how to optimize C++/C code for a large number of integers

Question

I have written the below mentioned code. The code checks the first bit of every byte. If the first bit of every byte of is equal to 0, then it concatenates this value with the previous byte and stores it in a different variable var1. Here pos points to bytes of an integer. An integer in my implementation is uint64_t and can occupy upto 8 bytes.

uint64_t func(char* data)
{
    uint64_t var1 = 0; int i=0;
    while ((data[i] >> 7) == 0) 
    {
        variable = (variable << 7) | (data[i]);
        i++;
    }   
   return variable; 
}

Since I am repeatedly calling func() a trillion times for trillions of integers. Therefore it runs slow, is there a way by which I may optimize this code?

EDIT: Thanks to Joe Z..its indeed a form of uleb128 unpacking.

Answer 1

Can you change your encoding? As you've discovered, using a bit on each byte to indicate if there's another byte following really sucks for processing efficiency.

A better way to do it is to model UTF-8, which encodes the length of the full int into the first byte:

0xxxxxxx // one byte with 7 bits of data
10xxxxxx 10xxxxxx // two bytes with 12 bits of data
110xxxxx 10xxxxxx 10xxxxxx // three bytes with 16 bits of data
1110xxxx 10xxxxxx 10xxxxxx 10xxxxxx // four bytes with 22 bits of data
// etc.

But UTF-8 has special properties to make it easier to distinguish from ASCII. This bloats the data and you don't care about ASCII, so you'd modify it to look like this:

0xxxxxxx // one byte with 7 bits of data
10xxxxxx xxxxxxxx // two bytes with 14 bits of data.
110xxxxx xxxxxxxx xxxxxxxx // three bytes with 21 bits of data
1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx // four bytes with 28 bits of data
// etc.

This has the same compression level as your method (up to 64 bits = 9 bytes), but is significantly easier for a CPU to process.

From this you can build a lookup table for the first byte which gives you a mask and length:

// byte_counts[255] contains the number of additional
// bytes if the first byte has a value of 255.
uint8_t const byte_counts[256]; // a global constant.

// byte_masks[255] contains a mask for the useful bits in
// the first byte, if the first byte has a value of 255.
uint8_t const byte_masks[256]; // a global constant.

And then to decode:

// the resulting value.
uint64_t v = 0;

// mask off the data bits in the first byte.
v = *data & byte_masks[*data];

// read in the rest.
switch(byte_counts[*data])
{
    case 3: v = v << 8 | *++data;
    case 2: v = v << 8 | *++data;
    case 1: v = v << 8 | *++data;
    case 0: return v;
    default:
        // If you're on VC++, this'll make it take one less branch.
        // Better make sure you've got all the valid inputs covered, though!
        __assume(0);
}

No matter the size of the integer, this hits only one branch point: the switch, which will likely be put into a jump table. You can potentially optimize it even further for ILP by not letting each case fall through.

Answer 2

Can you change the encoding?

Google came across the same problem, and Jeff Dean describes a really cool solution on slide 55 of his presentation:

• http://research.google.com/people/jeff/WSDM09-keynote.pdf‎
• http://videolectures.net/wsdm09_dean_cblirs/

The basic idea is that reading the first bit of several bytes is poorly supported on modern architectures. Instead, let's take 8 of these bits, and pack them as a single byte preceding the data. We then use the prefix byte to index into a 256-item lookup table, which holds masks describing how to extract numbers from the rest of the data.

I believe it's how protocol buffers are currently encoded.

Answer 3

I have only tested this minimally; I am happy to fix glitches with it. With modern processors, you want to bias your code heavily toward easily predicted branches. And, if you can safely read the next 10 bytes of input, there's nothing to be saved by guarding their reads by conditional branches. That leads me to the following code:

// fast uleb128 decode
// assumes you can read all 10 bytes at *data safely.
// assumes standard uleb128 format, with LSB first, and 
// ... bit 7 indicating "more data in next byte"

uint64_t unpack( const uint8_t *const data )
{
    uint64_t value = ((data[0] & 0x7F   ) <<  0)
                   | ((data[1] & 0x7F   ) <<  7)
                   | ((data[2] & 0x7F   ) << 14)
                   | ((data[3] & 0x7F   ) << 21)
                   | ((data[4] & 0x7Full) << 28)
                   | ((data[5] & 0x7Full) << 35)
                   | ((data[6] & 0x7Full) << 42)
                   | ((data[7] & 0x7Full) << 49)
                   | ((data[8] & 0x7Full) << 56)
                   | ((data[9] & 0x7Full) << 63);

    if ((data[0] & 0x80) == 0) value &= 0x000000000000007Full; else
    if ((data[1] & 0x80) == 0) value &= 0x0000000000003FFFull; else
    if ((data[2] & 0x80) == 0) value &= 0x00000000001FFFFFull; else
    if ((data[3] & 0x80) == 0) value &= 0x000000000FFFFFFFull; else
    if ((data[4] & 0x80) == 0) value &= 0x00000007FFFFFFFFull; else
    if ((data[5] & 0x80) == 0) value &= 0x000003FFFFFFFFFFull; else
    if ((data[6] & 0x80) == 0) value &= 0x0001FFFFFFFFFFFFull; else
    if ((data[7] & 0x80) == 0) value &= 0x00FFFFFFFFFFFFFFull; else
    if ((data[8] & 0x80) == 0) value &= 0x7FFFFFFFFFFFFFFFull;

    return value;
}

The basic idea is that small values are common (and so most of the if-statements won't be reached), but assembling the 64-bit value that needs to be masked is something that can be efficiently pipelined. With a good branch predictor, I think the above code should work pretty well. You might also try removing the else keywords (without changing anything else) to see if that makes a difference. Branch predictors are subtle beasts, and the exact character of your data also matters. If nothing else, you should be able to see that the else keywords are optional from a logic standpoint, and are there only to guide the compiler's code generation and provide an avenue for optimizing the hardware's branch predictor behavior.

Ultimately, whether or not this approach is effective depends on the distribution of your dataset. If you try out this function, I would be interested to know how it turns out. This particular function focuses on standard uleb128, where the value gets sent LSB first, and bit 7 == 1 means that the data continues.

There are SIMD approaches, but none of them lend themselves readily to 7-bit data.

Also, if you can mark this inline in a header, then that may also help. It all depends on how many places this gets called from, and whether those places are in a different source file. In general, though, inlining when possible is highly recommended.

Answer 4

First, rather than shifting, you can do a bitwise test on the relevant bit. Second, you can use a pointer, rather than indexing (but the compiler should do this optimization itself. Thus:

uint64_t
readUnsignedVarLength( unsigned char const* pos )
{
    uint64_t results = 0;
    while ( (*pos & 0x80) == 0 ) {
        results = (results << 7) | *pos;
        ++ pos;
    }
    return results;
}

At least, this corresponds to what your code does. For variable length encoding of unsigned integers, it is incorrect, since 1) variable length encodings are little endian, and your code is big endian, and 2) your code doesn't or in the high order byte. Finally, the Wiki page suggests that you've got the test inversed. (I know this format mainly from BER encoding and Google protocol buffers, both of which set bit 7 to indicate that another byte will follow.

The routine I use is:

uint64_t
readUnsignedVarLen( unsigned char const* source )
{
    int shift = 0;
    uint64_t results = 0;
    uint8_t tmp = *source ++;
    while ( ( tmp & 0x80 ) != 0 ) {
        *value |= ( tmp & 0x7F ) << shift;
        shift += 7;
        tmp = *source ++;
    }
    return results | (tmp << shift);
}

For the rest, this wasn't written with performance in mind, but I doubt that you could do significantly better. An alternative solution would be to pick up all of the bytes first, then process them in reverse order:

uint64_t
readUnsignedVarLen( unsigned char const* source )
{
    unsigned char buffer[10];
    unsigned char* p = std::begin( buffer );
    while ( p != std::end( buffer ) && (*source & 0x80) != 0 ) {
        *p = *source & 0x7F;
        ++ p;
    }
    assert( p != std::end( buffer ) );
    *p = *source;
    ++ p;
    uint64_t results = 0;
    while ( p != std::begin( buffer ) ) {
        -- p;
        results = (results << 7) + *p;
    }
    return results;
}

The necessity of checking for buffer overrun will likely make this slightly slower, but on some architectures, shifting by a constant is significantly faster than shifting by a variable, so this could be faster on them.

Globally, however, don't expect miracles. The motivation for using variable length integers is to reduce data size, at a cost in runtime for decoding and encoding.

Answer 5

Your code is problematic

uint64_t func(const unsigned char* pos)
{
    uint64_t var1 = 0; int i=0;
    while ((pos[i] >> 7) == 0) 
    {
        var1 = (var1 << 7) | (pos[i]);
        i++;
    }
    return var1;    
}

First a minor thing: i should be unsigned.

Second: You don't assert that you don't read beyond the boundary of pos. E.g. if all values of your pos array are 0, then you will reach pos[size] where size is the size of the array, hence you invoke undefined behaviour. You should pass the size of your array to the function and check that i is smaller than this size.

Third: If pos[i] has most significant bit equal to zero for i=0,..,k with k>10, then previous work get's discarded (as you push the old value out of var1).

The third point actually helps us:

uint64_t func(const unsigned char* pos, size_t size)
{
    size_t i(0);
    while ( i < size && (pos[i] >> 7) == 0 )
    {
       ++i;
    }
    // At this point, i is either equal to size or
    // i is the index of the first pos value you don't want to use.
    // Therefore we want to use the values
    // pos[i-10], pos[i-9], ..., pos[i-1]
    // if i is less than 10, we obviously need to ignore some of the values
    const size_t start = (i >= 10) ? (i - 10) : 0;
    uint64_t var1 = 0;
    for ( size_t j(start); j < i; ++j )
    {
       var1 <<= 7;
       var1 += pos[j];
    }
    return var1; 
}

In conclusion: We separated logic and got rid of all discarded entries. The speed-up depends on the actual data you have. If lot's of entries are discarded then you save a lot of writes to var1 with this approach.

Another thing: Mostly, if one function is called massively, the best optimization you can do is call it less. Perhaps you can have come up with an additional condition that makes the call of this function useless.

Keep in mind that if you actually use 10 values, the first value ends up the be truncated.

64bit means that there are 9 values with their full 7 bits of information are represented, leaving exactly one bit left foe the tenth. You might want to switch to uint128_t.

Answer 6

A small optimization would be:

while ((pos[i] & 0x80) == 0) 

Bitwise and is generally faster than a shift. This of course depends on the platform, and it's also possible that the compiler will do this optimization itself.