使用uint64_t批量比较短字符串
原理
想要判断字符串相等，常见的有利用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。
可以自己写个测试代码看看两个函数生成的整数值，具体的值会和字节序有关，但只要每个字符串都按相同的字节序进行处理，就不会有问题：
int main() |
{ |
std::cout << string2uint64("hello123") << '\n'; |
std::cout << string2uint64Unalign("hello123") << '\n'; |
std::cout << string2uint64("hell\0\0\0\0") << '\n'; |
std::cout << string2uint64Unalign("hell") << '\n'; |
} |
// 输出 |
3689065399400031592 |
3689065399400031592 |
1819043176 |
1819043176 |
性能测试
理解了原理，现在该看看性能了。
有经验的读者应该会有两个担心的点，第一个在于一次memcpy的内存复制开销是否会成为性能杀手，第二个在于memccpy做了额外的检测会不会导致执行速度减慢。
我也有这些担心，所以我设计了一个性能测试。测试使用随机生成的8字节长度的字符串，然后让两种优化方法和strcmp每次都就行八次匹配，只有最后一次会得到相等的结果。这样我们可以让字符串相等的判断逻辑尽量处理足够多的字符内容，以便模拟日常开发中的场景。
用随机生成字符串是有讲究的，因为用字符串常量编译器会在编译时就进行计算导致结果没有意义。这不能怪编译器，因为字符串比较操作实在太常用所以必须抓住一切机会就行优化。随机生成比较用的数据暂时能阻止编译器的优化。
生成随机字符串的代码我直接让AI写了，AI很适合生成这种只用一两次的阅后即焚的小型函数：
std::string generateRandomString(std::size_t length = 8) { |
const std::string charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" |
"abcdefghijklmnopqrstuvwxyz" |
"0123456789"; |
std::random_device rd; |
std::mt19937 gen(rd()); |
std::uniform_int_distribution<> distrib(0, charset.size() - 1); |
std::string result; |
result.reserve(length); |
for (std::size_t i = 0; i < length; ++i) { |
result += charset[distrib(gen)]; |
} |
return result; |
} |
写的确实很一般，但勉强能用。测试部分当然是我手写的，这块代码很简单：
void bench_strcmp(benchmark::State &state) |
{ |
const char *target = "hello123"; |
std::vector<std::string> data; |
for (int i = 0; i < 7; ++i) { |
data.push_back(generateRandomString()); |
} |
data.push_back("hello123"); |
for (auto _ : state) { |
for (const auto &str: data) { |
benchmark::DoNotOptimize(strcmp(target, str.c_str()) == 0); |
} |
} |
} |
BENCHMARK(bench_strcmp); |
void bench_fast(benchmark::State &state) |
{ |
const char *target = "hello123"; |
const uint64_t v = string2uint64(target); |
std::vector<std::string> data; |
for (int i = 0; i < 7; ++i) { |
data.push_back(generateRandomString()); |
} |
data.push_back("hello123"); |
for (auto _ : state) { |
for (const auto &str: data) { |
benchmark::DoNotOptimize(v == string2uint64(str.c_str())); |
} |
} |
} |
BENCHMARK(bench_fast); |
void bench_not_need_align(benchmark::State &state) |
{ |
const char *target = "hello123"; |
std::vector<std::string> data; |
for (int i = 0; i < 7; ++i) { |
data.push_back(generateRandomString()); |
} |
data.push_back("hello123"); |
const uint64_t v = string2uint64Unalign(target); |
for (auto _ : state) { |
for (const auto &str: data) { |
benchmark::DoNotOptimize(v == string2uint64Unalign(str.c_str())); |
} |
} |
} |
BENCHMARK(bench_not_need_align); |
首先是在Intel CPU的Linux上使用GCC的测试结果：
接着是在Intel cpu的Windows上使用msvc编译器的结果：