位操作快速 strlen

Question

我找到了这段代码

int strlen_my(const char *s)
{
    int len = 0;
    for(;;)
    {
        unsigned x = *(unsigned*)s;
        if((x & 0xFF) == 0) return len;
        if((x & 0xFF00) == 0) return len + 1;
        if((x & 0xFF0000) == 0) return len + 2;
        if((x & 0xFF000000) == 0) return len + 3;
        s += 4, len += 4;
    }
}

我很想知道它是如何工作的。 ¿任何人都可以解释它是如何工作的吗？

Answer 1

它检测是否在小端机器上的特定字节设置了任何位。因为我们只检查一个字节（因为所有的半字节，0 或 0xF，都加倍）并且它恰好是最后一个字节位置（因为机器是小端字节序的，因此数字的字节模式被颠倒了) 我们可以立即知道哪个字节包含 NUL.

Answer 2

循环在每次迭代中占用 char 数组的 4 个字节。四个 if 语句用于确定字符串是否结束，使用位掩码和 AND 运算符读取所选子字符串的第 i 个元素的状态。

Answer 3

它用未定义的行为（未对齐的访问，75% 的概率访问超出数组末尾）换取一个非常可疑的加速（它很可能甚至更慢）。并且不符合标准，因为它 returns int 而不是 size_t。即使平台允许非对齐访问，它们也可能比对齐访问慢得多。

它也不适用于大端系统，或者如果 unsigned 不是 32 位。更不用说多重掩码和条件操作了。

也就是说：

它通过加载一个 unsigned（甚至不能保证超过 16 位）来一次测试 4 个 8 位字节。一旦任何字节包含 '[=15=]' 终止符，它就是 returns 当前长度加上该字节位置的总和。否则它将当前长度增加并行测试的字节数 (4) 并获得下一个 unsigned.

我的建议：优化的坏例子太多了uncertainties/pitfalls。它可能不会更快——只需根据标准版本对其进行分析：

size_t strlen(restrict const char *s)
{
    size_t l = 0;
    while ( *s++ )
        l++;
    return l;
}

可能有一种方法可以使用特殊的向量指令，但除非你能证明这是一个关键函数，否则你应该把它留给编译器——有些人可能 unroll/speedup 这样的循环会好得多。

Answer 4

按位与 1 将从另一个操作数中检索位模式。意思是，10101 & 11111 = 10101。如果该按位与的结果是 0，那么我们知道我们知道另一个操作数是 0。当用 0xFF（个）对单个字节进行与运算时结果为 0 将表示一个 NULL 字节。

代码本身检查四字节分区中 char 数组的每个字节。 注意：此代码不可移植；在另一台机器或编译器上，unsigned int 可能超过 4 个字节。最好使用 uint32_t 数据类型来确保 32 位无符号整数。

首先要注意的是，在小端机器上，组成字符数组的字节将被倒序读入无符号数据类型；也就是说，如果当前地址的四个字节是abcd对应的位模式，那么无符号变量将包含dcba.

对应的位模式

第二个是 C 中的十六进制数常量会产生一个 int 大小的数字，在位模式的小端有指定的字节。意思是，0xFF 在使用 4 字节整数编译时实际上是 0x000000FF。 0xFF00 是 0x0000FF00。等等。

所以程序基本上是在四个可能的位置寻找 NULL 字符。如果当前分区中没有 NULL 字符，则前进到下一个四字节槽。

以字符数组abcdef为例。在 C 中，字符串常量的末尾总是有空终止符，因此该字符串的末尾有一个 0x00 字节。

它将按如下方式工作：

将"abcd"读入unsigned int x:

x: 0x64636261 [ASCII representations for "dcba"]

检查每个字节的空终止符：

  0x64636261
& 0x000000FF
  0x00000061 != 0,

  0x64636261
& 0x0000FF00
  0x00006200 != 0,

并检查其他两个位置；此 4 字节分区中没有空终止符，因此前进到下一个分区。

将"ef"读入unsigned int x:

x: 0xBF006665 [ASCII representations for "fe"]

注意0xBF字节；这超过了字符串的长度，所以我们正在从运行时堆栈中读取垃圾。它可以是任何东西。在不允许未对齐访问的机器上，如果字符串之后的内存不是 1 字节对齐的，这将崩溃。如果字符串中只剩下一个字符，我们将读取两个额外的字节，因此与 char 数组相邻的内存的对齐方式必须是 2 字节对齐的。

检查每个字节的空终止符：

  0xBF006665
& 0x000000FF
  0x00000065 != 0,

  0xBF006665
& 0x0000FF00
  0x00006600 != 0,

  0xBF006665
& 0x00FF0000
  0x00000000 == 0 !!!

所以我们returnlen + 2； len 是 4，因为我们将它递增一次 4，所以我们 return 6，这确实是字符串的长度。

Answer 5

代码 "works" 通过假设字符串像 int 的数组一样布局和访问，尝试一次读取 4 个字节。代码依次读取第一个 int 和每个字节，测试它是否为空字符。理论上，使用 int 的代码将运行比 4 个单独的 char 操作快。

但是有问题：

对齐是个问题：例如*(unsigned*)s 可能会出现段错误。

Endian 是一个问题 if((x & 0xFF) == 0) 可能无法在地址 s

处获取字节

s += 4 是个问题，因为 sizeof(int) 可能不同于 4.

数组类型可能超出int范围，最好使用size_t。

试图解决这些困难。

#include <stddef.h>
#include <stdio.h>

static inline aligned_as_int(const char *s) {
  max_align_t mat; // C11
  uintptr_t i = (uintptr_t) s;
  return i % sizeof mat == 0;
}

size_t strlen_my(const char *s) {
  size_t len = 0;
  // align
  while (!aligned_as_int(s)) {
    if (*s == 0) return len;
    s++;
    len++;
  }
  for (;;) {
    unsigned x = *(unsigned*) s;
    #if UINT_MAX >> CHAR_BIT == UCHAR_MAX
      if(!(x & 0xFF) || !(x & 0xFF00)) break;
      s += 2, len += 2;
    #elif UINT_MAX >> CHAR_BIT*3 == UCHAR_MAX
      if (!(x & 0xFF) || !(x & 0xFF00) || !(x & 0xFF0000) || !(x & 0xFF000000)) break;
      s += 4, len += 4;
    #elif UINT_MAX >> CHAR_BIT*7 == UCHAR_MAX
      if (   !(x & 0xFF) || !(x & 0xFF00)
          || !(x & 0xFF0000) || !(x & 0xFF000000)
          || !(x & 0xFF00000000) || !(x & 0xFF0000000000)
          || !(x & 0xFF000000000000) || !(x & 0xFF00000000000000)) break;
      s += 8, len += 8;
    #else
      #error TBD code
    #endif
  }
  while (*s++) {
    len++;
  }
  return len;
}

Answer 6

所有提案都比简单的 strlen() 慢。

原因是他们没有减少比较的次数，只有一个处理对齐。

在网上查看 Torbjorn Granlund (tege@sics.se) 和 Dan Sahlin (dan@sics.se) 的 strlen() 提案。如果您在 64 位平台上，这确实有助于加快速度。

位操作快速 strlen

Fast strlen with bit operations

c

bitwise-operators

strlen