如何针对大量整数优化C++/C代码

Question

我写了下面提到的代码.代码检查每个字节的第一位.如果每个字节的第一位等于0,则它将该值与前一个字节连接,并将其存储在不同的变量var1中.这里pos指向整数的字节.我的实现中的一个整数是uint64_t,最多可占用8个字节.

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; 
}

因为我反复为func()调用数万亿次整数.因此它运行缓慢,有没有办法优化这段代码？

编辑:感谢Joe Z ..确实是一种uleb128拆包的形式.

Answer 1

我只测试了这个最低限度; 我很乐意用它修复故障.使用现代处理器,您希望将代码严重偏向容易预测的分支.而且,如果你可以安全地读取接下来的10个字节的输入,那么通过条件分支保护它们的读取就没有什么可以保存的.这导致我得到以下代码:

// 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;
}

基本思想是小值是常见的(因此大多数if语句都不会被访问),但是组装需要屏蔽的64位值是可以有效流水线化的.有了一个很好的分支预测器,我认为上面的代码应该可以很好地工作.您也可以尝试删除else关键字(不更改任何其他内容)以查看是否会产生影响.分支预测变量是微妙的动物,数据的确切特征也很重要.如果不出意外,您应该能够else从逻辑角度看待关键字是可选的,并且仅用于指导编译器的代码生成并提供优化硬件分支预测器行为的途径.

最终,这种方法是否有效取决于数据集的分布.如果你尝试这个功能,我很想知道结果如何.此特定功能侧重于标准uleb128,其中值首先发送LSB,位7 == 1表示数据继续.

有SIMD方法,但它们都不适合7位数据.

此外,如果您可以inline在标题中标记,那么这也可能有所帮助.这一切都取决于调用它的位数,以及这些位置是否在不同的源文件中.但是,一般情况下,强烈建议尽可能使用内联.

Answer 2

您的代码存在问题

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;    
}

首先是一件小事:i应该是未签名的.

第二:你没有断言你没有超越界限pos.例如,如果你的所有值pos阵列0,那么你会到达pos[size]哪里size是数组的大小,因此你调用未定义的行为.您应该将数组的大小传递给函数并检查它i是否小于此大小.

第三:如果pos[i]有等于零最显著位为i=0,..,k与k>10,则以前下班的丢弃(你推旧值超出var1).

第三点实际上有助于我们:

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; 
}

总之:我们分离了逻辑并摆脱了所有丢弃的条目.加速取决于您拥有的实际数据.如果丢弃了很多条目,那么var1使用这种方法可以节省大量的写入.

另一件事:大多数情况下,如果一个函数被大规模调用,那么你可以做的最好的优化是减少它.也许你可以想出一个额外的条件,使这个函数的调用无用.

请记住,如果您实际使用10个值,则第一个值最终会被截断.

64位意味着有9个值,它们的全部7位信息被表示,只留下一个位于第十位.您可能想切换到uint128_t.