我已经写了下面的代码。这段代码检查每个字节的第一位。如果每个字节的第一位相等于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;
}
else关键字（而不改变其他任何内容）来查看是否有所区别。分支预测器是微妙的生物，您的数据的确切性质也很重要。如果没有其他办法，您应该能够看到else关键字在逻辑上是可选的，并且只是为了指导编译器的代码生成并为优化硬件的分支预测器行为提供一条途径。uleb128，其中值首先发送LSB，第7位等于1表示数据继续。inline，那么可能也会有所帮助。这完全取决于此函数被从哪些位置调用以及这些位置是否在不同的源文件中。但总的来说，在可能的情况下进行内联是强烈推荐的。0x7Full == ((unsigned long long)0x7F)。” - orlp0xBull。 - user123你的代码有问题
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 是否小于此大小。
第三点：如果对于 i=0,..,k，其中 k>10，pos[i] 的最高有效位等于零，则之前的工作将被丢弃（因为您将旧值推出了 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的写操作。uint128_t。CHAR_BIT == 8，但这通常是正常的事情。如果您想要真正实现平台无关性，您可能需要更改它。 - stefani应该是无符号的；它并没有什么特别之处，所以通常的“良好实践”是使用int。（当然，在C++中通常惯用指针。） - James Kanzeint，除非没有特别强烈的理由不使用它。在这里，没有理由不使用int，所以最佳实践是使用它。对于当前的实际代码，除了（除了任何除了 int 之外的类型会向读者传递错误信息之外）没有任何实质性的区别，但是 C++ 中的无符号类型具有相当反直觉的语义，并且最好避免在算术值中使用它们。 - James Kanzeint表示“它也可能是负数”。无符号整数天生就是索引。 - stefanunsigned本身可以用于位操作和模算术，但不是唯一的用途。作为一名经验丰富的C++程序员，我很少仅仅为此目的使用它们，也就是说，我只有一个这样的应用程序。大多数情况下，我使用它们来表示具有自然数意义的东西（例如索引、大小等）。我想这是我们意见不同的问题。 - stefan一个小的优化方法是：
while ((pos[i] & 0x80) == 0)
按位与通常比移位运算更快。当然，这取决于平台，并且编译器也有可能自己进行此优化。
pos[i]>=0的等效条件替换了整个条件。 - Mooing Duck你能改变编码吗？如你所发现，使用每个字节上的一位来指示是否有另一个字节跟随，对处理效率真的很不好。
更好的方法是采用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.
// 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);
}
v = v << 8 | *++data; 这行代码时，我会停下来想：“需要加上更多的括号”。我不确定操作顺序是否正确。 - Mooing Duck(v << 8) | *++data。是正确的，但为了可读性可能需要加上一些括号。 - Cory Nelson你能改变编码吗？
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）您的代码没有在高位字节中加入或运算。最后，维基页面建议您已经反转了测试。（我主要从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;
}
检查缓冲区溢出的必要性可能会使其稍微慢一些，但在某些体系结构中，通过常量进行移位比通过变量进行移位快得多，因此在这些体系结构上可能更快。
然而，总体而言，不要期望奇迹。使用可变长度整数的动机是为了减少数据大小，以换取解码和编码的运行时间成本。
func不通知使用了多少字节？我认为这种设计需要牺牲效率... - Mooing Duck