使用uint64_t批量比较短字符串

暴灵珊 · 5 天前

记录一下从开源代码里学来的短字符串比较优化。
这个优化只适用于长度在八字节以下的字符串，且只适用于优化相等比较。
原理

想要判断字符串相等，常见的有利用strcmp、利用字符串的hash或者利用正则表达式等。
就速度而言strcmp > hash > 正则，而灵活性上正则 > hash ≈ strcmp。
字符串的相等性比较可以说是程序运行中的热点，因此用于比较字符串的各种函数也是性能优化中的重点，这使得strcmp在通用场景下有着相当不错的性能表现。
不过在细分场景上strcmp就有点心有余而力不足了。我们要讨论的场景就是这种细分场景：两个字符串长度相同且都小于等于八字节。
在这个场景下，绝大多数字符串比较函数都是选择逐字节循环比较的，这个策略其实没有问题，少量数据以固定模式进行循环处理，对于现代cpu来说是个很容易吃到缓存优化的操作，因此速度不会落下风。
但这个方案仍然需要多次比较数据，这是一个瓶颈，我们要讲的优化就是针对减少比较次数这一点进行的。
考虑两个八字节长度的字符串hello123和hello124，如果用逐字节比较的办法，最坏情况下我们需要比较8次。想要减少比较次数我们就得每次比较两个字节以上的数据，甚至是一次就处理全部的八个字节。
碰巧的是现代的x86和ARM芯片上还真有这种一次比较八字节数据的指令，只不过这些指令比较的是64位整数值而不是字符串。我们的优化措施就是利用这些指令来比较字符串内容。
所以现在的问题变成了怎么把字符串转换成整数值。很多读者应该会立即想到hash，但这里用hash是不合适的，hash本身需要处理每一个字符，而且需要添加很多额外的运算，在以前的博客里我测试过在处理短字符串时它的性能是不及strcmp的。而现在我们要实现比strcmp更快的方法，hash自然是不适用的。
剩下只有一种途径了，64位整数正好需要八字节内存，我们的字符串也正好是八字节，所以我们可以考虑把字符串的二进制数据整个复制给整数。这个做法其实在c/c++系统编程里很常见，但对于习惯了go/js的人来说可能有些陌生了：

uint64_t string2uint64(const char *str)
{
uint64_t res = 0;
memcpy((void*)&res, (const void*)str, sizeof(uint64_t));
return res;
}

复制代码

为了代码尽量简短，我用了c-style的类型转换。这个函数其实不安全，想象一下str没有8字节长的情景，这个函数会越界访问。这段代码也不够类型安全。
string2uint64要求字符串必须有至少8字节长度，所以对于不足8字节的字符串，调用的时候得补足：

string2uint64("hello123") // 正好8字节
string2uint64("hell\0\0\0\0") // 补了4个0

复制代码

而且长度的计量单位是字节，因此碰到汉字这种不管什么编码基本都是多字节存储的内容，这个函数也很容易出错。
如果觉得补0很麻烦，实际上我们也有简化手段：使用memccpy。这个函数可以在找到指定字符的时候停止复制，因此我们只要让它找到字符串结尾的0就可以阻止越界访问了：

uint64_t string2uint64Unalign(const char *str)
{
uint64_t res = 0;
memccpy((void*)&res, (const void*)str, 0, sizeof(uint64_t));
return res;
}

复制代码

注意两个版本我都采用了复制而不是直接把字符串的指针转换成uint64_t*，因为后者是真正的踩在了语言标准的红线上，而且也没办法像string2uint64Unalign那样处理长度对齐。
在把字符串转换成整数之后，我们就可以用比较整数的方式比较字符串了：

strcmp("hello", "world") == 0 || strcmp("hello", "Hello") == 0 || strcmp("hello", "hello") == 0;
// 等价于
const auto value = string2uint64("hello\0\0\0");
value == string2uint64("world\0\0\0") || value == string2uint64("Hello\0\0\0") || value == string2uint64("hello\0\0\0");

复制代码

注意为了补足长度而填充进去的0。
可以自己写个测试代码看看两个函数生成的整数值，具体的值会和字节序有关，但只要每个字符串都按相同的字节序进行处理，就不会有问题：
[code]int main(){ std::cout

账号		自动登录	找回密码
密码			立即注册

使用uint64_t批量比较短字符串

浏览过的版块

签约作者