我已经编写了下面提到的代码。代码检查每个字节的第一位。如果每个字节的第一位都等于 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 拆包的一种形式。
我只对此进行了最低限度的测试；我很高兴用它来修复故障。使用现代处理器，您希望将代码严重偏向易于预测的分支。而且，如果您可以安全地读取接下来的 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在标题中标记它，那么这也可能会有所帮助。这完全取决于从多少地方调用它，以及这些地方是否在不同的源文件中。但总的来说，强烈建议尽可能内联。
你的代码有问题
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是否小于此大小。
第三：如果withpos[i]的最高有效位等于 0 ，则之前的工作将被丢弃（当您将旧值推出时）。i=0,..,kk>10var1
第三点实际上对我们有帮助：
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 位信息都被表示出来，只剩下 1 位到第十位。您可能想要切换到uint128_t.
一个小的优化是：
while ((pos[i] & 0x80) == 0)
按位计算，通常比移位快。这当然取决于平台，编译器也有可能自己进行这种优化。
你能改变你的编码吗？正如您所发现的，在每个字节上使用一个位来指示是否有另一个字节在处理效率方面确实很糟糕。
更好的方法是对 UTF-8 建模，它将完整 int 的长度编码为第一个字节：
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.
但是 UTF-8 有一些特殊的属性，使它更容易与 ASCII 区分开来。这会使数据膨胀，并且您不关心 ASCII，因此您可以将其修改为如下所示：
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.
这与您的方法具有相同的压缩级别（最多 64 位 = 9 字节），但 CPU 处理起来要容易得多。
从这里你可以为第一个字节建立一个查找表，它给你一个掩码和长度：
// 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.
然后解码：
// 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);
}
无论整数大小如何，它都只命中一个分支点：开关，它很可能会被放入一个跳转表中。通过不让每个案例都失败，您可以为 ILP 进一步优化它。
能改一下编码吗？
Google 遇到了同样的问题，Jeff Dean 在他的演示文稿的第 55 张幻灯片中描述了一个非常酷的解决方案：
基本思想是现代架构对读取几个字节的第一位的支持很差。相反，让我们取其中的 8 个位，并将它们打包为数据之前的单个字节。然后，我们使用前缀字节来索引 256 项查找表，其中包含描述如何从其余数据中提取数字的掩码。
我相信这就是当前对协议缓冲区进行编码的方式。
首先，您可以对相关位进行按位测试，而不是移位。其次，您可以使用指针，而不是索引（但编译器应该自己进行这种优化。因此：
uint64_t
readUnsignedVarLength( unsigned char const* pos )
{
uint64_t results = 0;
while ( (*pos & 0x80) == 0 ) {
results = (results << 7) | *pos;
++ pos;
}
return results;
}
至少，这与您的代码所做的相对应。对于无符号整数的可变长度编码，这是不正确的，因为 1）可变长度编码是小端，而您的代码是大端，以及 2）您的代码不是高位字节。最后，Wiki 页面表明您已经反转了测试。（我知道这种格式主要来自 BER 编码和 Google 协议缓冲区，它们都将第 7 位设置为指示接下来将有另一个字节。
我使用的例程是：
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);
}
其余的，这并没有考虑到性能，但我怀疑你可以做得更好。另一种解决方案是首先获取所有字节，然后以相反的顺序处理它们：
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;
}
检查缓冲区溢出的必要性可能会使这稍微慢一些，但在某些架构上，按常量移动比按变量移动要快得多，因此这对它们来说可能更快。
然而，在全球范围内，不要指望奇迹。使用可变长度整数的动机是减少数据大小，但代价是运行时解码和编码。