短(ASCII，每个字符 7 位)字符串存储和C++中的比较优化

Question

在我的项目中，我使用了大量的 ASCII 7 位短字符串集，并且必须以最佳性能处理(存储、比较、搜索等)这些字符串。 基本上，我构建了一些uint64_t类型的 Index 数组，每个元素存储一个单词的 9 个字符，并将该索引用作任何字符串比较操作的 Numeric 元素。 当前的实现工作速度很快，但如果您愿意，可以对其进行一些改进。

此函数最多可将 9 个初始字符转换为uint64_t值 - 该数字的任何比较都等同于标准"strcmp"函数。

#include <cstdint>
#include <iostream>
uint64_t cnv(const char* str, size_t len)
{
uint64_t res = 0;
switch (len)
{
default:
case 9: res = str[8];
case 8: res |= uint64_t(str[7]) << 7;
case 7: res |= uint64_t(str[6]) << 14;
case 6: res |= uint64_t(str[5]) << 21;
case 5: res |= uint64_t(str[4]) << 28;
case 4: res |= uint64_t(str[3]) << 35;
case 3: res |= uint64_t(str[2]) << 42;
case 2: res |= uint64_t(str[1]) << 49;
case 1: res |= uint64_t(str[0]) << 56;
case 0: break;
}
return res;
}
int main()
{
uint64_t v0 = cnv("000", 3);
uint64_t v1 = cnv("0000000", 7);
std::cout << (v1 < v0);
}

Answer 1

您可以一次加载 8 个字节的原始字符串，而不是将它们压缩在生成的整数中(如果您的机器具有小端数表示形式，则反转它们)。

#include <iostream>
uint64_t ascii2ulong (const char  *s, int len)
{
uint64_t i = (*(uint64_t*)s);
if (len < 8) i &= ((1UL << (len<<3))-1);
#ifndef BIG_ENDIAN
i = (i&0x007f007f007f007fUL) | ((i & 0x7f007f007f007f00) >> 1);
i = (i&0x00003fff00003fffUL) | ((i & 0x3fff00003fff0000) >> 2);
i = ((i&0x000000000fffffffUL) << 7) | ((i & 0x0fffffff00000000) << (7-4));
// Note: Previous line: an additional left shift of 7 is applied
// to make room for s[8] character
#else
i = ((i&0x007f007f007f007fUL) << 7)  | ((i & 0x7f007f007f007f00) >> 8);
i = ((i&0x00003fff00003fffUL) << 14) | ((i & 0x3fff00003fff0000) >> 16);
i = ((i&0x000000000fffffffUL) << (28+7)) | ((i & 0x0fffffff00000000) >> (32-7));
#endif
if (len > 8) i |= ((uint64_t)s[8]);
return i;
}

//Test
std::string ulong2str(uint64_t compressed) {
std::string s;
for (int i = 56; i >= 0; i-=7) 
if (char nxt=(compressed>>i)&0x7f) s+= nxt;
return s;
}
int main() {
std::cout << ulong2str(ascii2ulong("ABCDEFGHI", 9))<<std::endl;
std::cout << ulong2str(ascii2ulong("ABCDE", 5))<<std::endl;
std::cout << (ascii2ulong("AB", 2) < ascii2ulong("B", 1))<<std::endl;
std::cout << (ascii2ulong("AB", 2) < ascii2ulong("A", 1))<<std::endl;
return 0;
}

但请注意：以这种方式这样做会正式违反分配的地址范围(如果您的原始字符串分配了 <8 个字节)。如果运行具有内存健全性检查的程序，则可能会产生运行时错误。为了避免这种情况，您当然可以使用memcpy来复制尽可能多的字节来代替uint64_t i = (*(uint64_t*)s);：

uint64_t i;
memcpy(&i,s,std::min(len,8));

如果在您的计算机上使用一些硬件加速进行memcpy(这很可能)，则在效率方面可能还不错。