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

c, c++, optimization, performance

Solution

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.

Problem

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.

Original source