使用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的人来说可能有些生疏了：

1. uint64_t string2uint64(const char *str)
2. {
3.     uint64_t res = 0;
4.     memcpy((void*)&res, (const void*)str, sizeof(uint64_t));
5.     return res;
6. }

复制代码

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

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

复制代码

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

1. uint64_t string2uint64Unalign(const char *str)
2. {
3.     uint64_t res = 0;
4.     memccpy((void*)&res, (const void*)str, 0, sizeof(uint64_t));
5.     return res;
6. }

复制代码

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

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

复制代码

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