检查 char 数组中前导字符的最快方法是什么？

Question

我的代码遇到了瓶颈，所以这个问题的主要问题是性能。

我有一个十六进制校验和，我想检查一个字符数组的前导零。这就是我正在做的：

bool starts_with (char* cksum_hex, int n_zero) {
  bool flag {true};
  for (int i=0; i<n_zero; ++i)
    flag &= (cksum_hex[i]=='0');
  return flag;
}

如果cksum_hex有，则上述函数返回truen_zero前导零，。但是，对于我的应用程序，此功能非常昂贵（占总时间的 60%）。换句话说，它是我代码的瓶颈。所以我需要改进它。

我还检查了std::string::starts_with哪些在 C++20 中可用，我发现性能没有差异：

// I have to convert cksum to string
std::string cksum_hex_s (cksum_hex);
cksum_hex_s.starts_with("000");     // checking for 3 leading zeros

有关我正在使用的更多信息 g++ -O3 -std=c++2a，我的 gcc 版本是 9.3.1。

问题

• 检查 char 数组中前导字符的更快方法是什么？
• 有没有更有效的方法来做到这一点 std::string::starts_with？
• 按位运算在这里有帮助吗？

Answer 1

如果你修改你的函数以提前返回

bool starts_with (char* cksum_hex, int n_zero) {
  for (int i=0; i<n_zero; ++i)
  {
    if (cksum_hex[i] != '0') return false;
  }
  return true;
}

在大n_zero和false结果的情况下它会更快。否则，也许您可​​以尝试分配一个全局字符数组'0'并使用std::memcmp：

// make it as big as you need
constexpr char cmp_array[4] = {'0', '0', '0', '0'};
bool starts_with (char* cksum_hex, int n_zero) {
    return std::memcmp(cksum_hex, cmp_array, n_zero) == 0;
}

这里的问题是您需要假设 的某个最大可能值n_zero。

活生生的例子

=== 编辑 ===

考虑到抱怨没有分析数据来证明建议的方法是合理的，这里是：

• 比较早期回报实施与memcmp实施的基准结果
• 将memcmp实现与 OP 原始实现进行比较的基准测试结果

使用的数据：

const char* cs1 = "00000hsfhjshjshgj";
const char* cs2 = "20000hsfhjshjshgj";
const char* cs3 = "0000000000hsfhjshjshgj";
const char* cs4 = "0000100000hsfhjshjshgj";

memcmp在所有情况下都是最快的，但cs2有提前返回的实现。

Answer 2

想必你也有二进制校验和？ 与其先将其转换为 ASCII 文本，不如查看4*n高位以n直接检查半字节，0而不是检查n字节是否与 相等'0'。

例如，如果您将散列（或它的高 8 字节）作为 auint64_t或unsigned __int128，则将其右移以仅保留高n半字节。

我展示了一些示例，说明当两个输入都是运行时变量时它们如何为 x86-64 编译，但这些也可以很好地编译到其他 ISA，如 AArch64。这段代码都是可移植的 ISO C++。

bool starts_with (uint64_t cksum_high8, int n_zero)
{
    int shift = 64 - n_zero * 4;       // A hex digit represents a 4-bit nibble
    return (cksum_high8 >> shift) == 0;
}

clang 在 x86-64 上做得很好，-O3 -march=haswell可以启用 BMI1/BMI2

high_zero_nibbles(unsigned long, int):
        shl     esi, 2
        neg     sil                  # x86 shifts wrap the count so 64 - c is the same as -c
        shrx    rax, rdi, rsi        # BMI2 variable-count shifts save some uops.
        test    rax, rax
        sete    al
        ret

这甚至适用于n=16(shift=0) 测试所有 64 位。它没有n_zero = 0测试任何位；它会通过将 a 移动uint64_t一个移位计数 >= 其宽度来遇到 UB 。（在像 x86 这样包装越界移位计数的 ISA 上，适用于其他移位计数的代码生成将导致检查所有 16 位。只要 ​​UB 在编译时不可见......）希望你n_zero=0无论如何都不打算打电话给这个。

其他选项：创建仅保持高面具n*4位，也许通过缩短关键路径cksum_high8，如果这是准备迟n_zero。特别是如果n_zero是内联后的编译时常量，这可以和检查一样快cksum_high8 == 0。（例如 x86-64 test reg, immediate。）

bool high_zero_nibbles_v2 (uint64_t cksum_high8, int n_zero) {
    int shift = 64 - n_zero * 4;         // A hex digit represents a 4-bit nibble
    uint64_t low4n_mask = (1ULL << shift) - 1;
    return cksum_high8 & ~low4n_mask;
}

或者使用位扫描函数计算前导零位并比较>= 4*n. 不幸的是，直到 C++20<bit>的ISO C++才countl_zero最终可移植地公开了这个已经存在了几十年的通用 CPU 特性（例如 386 bsf/ bsr）；在此之前，仅作为编译器扩展，如 GNU C __builtin_clz。

如果您想知道有多少并且没有一个特定的截止阈值，这很好。

bool high_zero_nibbles_lzcnt (uint64_t cksum_high8, int n_zero) {
    // UB on cksum_high8 == 0.  Use x86-64 BMI1 _lzcnt_u64 to avoid that, guaranteeing 64 on input=0
    return __builtin_clzll(cksum_high8) > 4*n_zero;
}

#include <bit>
bool high_zero_nibbles_stdlzcnt (uint64_t cksum_high8, int n_zero) {
    return std::countl_zero(cksum_high8) > 4*n_zero;
}

编译为（Haswell 的叮当声）：

high_zero_nibbles_lzcnt(unsigned long, int):
        lzcnt   rax, rdi
        shl     esi, 2
        cmp     esi, eax
        setl    al                    # FLAGS -> boolean integer return value
        ret

所有这些指令在 Intel 和 AMD 上都很便宜，而且 lzcnt 和 shl 之间甚至还有一些指令级的并行性。

在 Godbolt 编译器资源管理器上查看所有 4 个的 asm 输出。Clang 将 1 和 2 编译为相同的 asm。与-march=haswell. 否则bsr，对于不是 UB 的 C++20 版本，它需要竭尽全力处理input=0 的极端情况。

要将这些扩展到更宽的散列，您可以检查高 uint64_t 是否全为零，然后继续下一个 uint64_t 块。

pcmpeqb在字符串上使用 SSE2 比较，pmovmskb->bsf可以找到第1一位的位置，从而找到'0'字符串表示中有多少个前导字符，如果你有的话。因此，x86 SIMD 可以非常有效地执行此操作，您可以通过内在函数从 C++ 中使用它。

Answer 3

您可以为您制作一个足够大的零缓冲区，而不是与 memcmp 进行比较。

const char *zeroBuffer = "000000000000000000000000000000000000000000000000000";

if (memcmp(zeroBuffer, cksum_hex, n_zero) == 0) {
   // ...
}

Answer 4

您想要检查的事项以使您的应用程序更快：

1. 编译器可以在调用它的地方内联这个函数吗？

要么在头文件中将函数声明为内联函数，要么将定义放在使用它的编译单元中。

2. 不计算比计算更有效更快

是否需要对这个函数的所有调用？高成本通常是在高频循环或昂贵算法中调用的函数的标志。您通常可以通过优化外部算法来减少调用次数，从而减少在函数中花费的时间

3. 是n_zero小还是常数？

编译器非常擅长为通常较小的常量值优化算法。如果编译器知道常量，它很可能会完全删除循环。

4. 按位运算在这里有帮助吗？

它肯定有效果，并允许 Clang（但据我所知不是 GCC）进行一些矢量化。矢量化往往更快，但情况并非总是如此，具体取决于您的硬件和实际处理的数据。它是否是优化可能取决于有多大n_zero。考虑到您正在处理校验和，它应该非常小，因此听起来像是一个潜在的优化。对于已知n_zero使用按位运算允许编译器删除所有分支。我希望，虽然我没有测量，但这会更快。

std::all_of并且std::string::starts_with应该完全按照您的实现进行编译，除了它们将使用&&代替&.