c++ - 如何针对大量整数优化 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 位数据。

此外，如果您可以在 header 中标记此 inline，那么这也可能有所帮助。这完全取决于从多少地方调用它，以及这些地方是否在不同的源文件中。不过，一般而言，强烈建议尽可能内联。