为什么glbc的strlen需要如此复杂才能快速运行？

Question

我在这里浏览了strlen代码，我想知道代码中使用的优化是否真的需要？例如，为什么像下面这样的工作不能同样好或更好？

unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '\0'; i++)
        continue;
    return i;
}

代码越简单，编译器就越容易优化吗？

链接后面页面上的strlen代码如下所示：

/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund ([e-mail]),
   with help from Dan Sahlin ([e-mail]);
   commentary by Jim Blandy ([e-mail]).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <string.h>
#include <stdlib.h>

#undef strlen

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
strlen (str)
     const char *str;
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, magic_bits, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  magic_bits = 0x7efefeffL;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      /* We tentatively exit the loop if adding MAGIC_BITS to
     LONGWORD fails to change any of the hole bits of LONGWORD.

     1) Is this safe?  Will it catch all the zero bytes?
     Suppose there is a byte with all zeros.  Any carry bits
     propagating from its left will fall into the hole at its
     least significant bit and stop.  Since there will be no
     carry from its most significant bit, the LSB of the
     byte to the left will be unchanged, and the zero will be
     detected.

     2) Is this worthwhile?  Will it ignore everything except
     zero bytes?  Suppose every byte of LONGWORD has a bit set
     somewhere.  There will be a carry into bit 8.  If bit 8
     is set, this will carry into bit 16.  If bit 8 is clear,
     one of bits 9-15 must be set, so there will be a carry
     into bit 16.  Similarly, there will be a carry into bit
     24.  If one of bits 24-30 is set, there will be a carry
     into bit 31, so all of the hole bits will be changed.

     The one misfire occurs when bits 24-30 are clear and bit
     31 is set; in this case, the hole at bit 31 is not
     changed.  If we had access to the processor carry flag,
     we could close this loophole by putting the fourth hole
     at bit 32!

     So it ignores everything except 128's, when they're aligned
     properly.  */

      longword = *longword_ptr++;

      if (
#if 0
      /* Add MAGIC_BITS to LONGWORD.  */
      (((longword + magic_bits)

        /* Set those bits that were unchanged by the addition.  */
        ^ ~longword)

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */
       & ~magic_bits)
#else
      ((longword - lomagic) & himagic)
#endif
      != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

为什么这个版本运行得很快？

它不是做了很多不必要的工作吗？

Answer 1

您链接的文件中的注释对此进行了解释：

 27 /* Return the length of the null-terminated string STR.  Scan for
 28    the null terminator quickly by testing four bytes at a time.  */

以及：

 73   /* Instead of the traditional loop which tests each character,
 74      we will test a longword at a time.  The tricky part is testing
 75      if *any of the four* bytes in the longword in question are zero.  */

在C语言中，可以对效率进行详细的推理。

与一次测试多个字节相比，遍历单个字符查找空值的效率要低一些，就像这段代码所做的那样。

额外的复杂性来自于需要确保被测字符串在正确的位置对齐，以开始一次测试多个字节（沿着长字边界，如注释中所述），以及需要确保在使用代码时不违反关于数据类型大小的假设。

在大多数（但不是所有）现代软件开发中，这种对效率细节的关注是不必要的，或者不值得付出额外代码复杂性的代价。

像这样关注效率是有意义的一个地方是在标准库中，就像你链接的例子一样。

如果你想阅读更多关于单词边界的内容，请看这个问题，以及这个优秀的维基百科页面

我还认为，上述答案是一个更清晰、更详细的讨论。

Answer 2

关于这方面的一些细节/背景，评论中有很多（轻微或完全）错误的猜测。

您看到的是glibc的优化C回退优化实现。（适用于没有手写asm实现的ISA）。或者该代码的旧版本，仍然在glibc源代码树中。https://code.woboq.org/userspace/glibc/string/strlen.c.html 是基于当前glibc git树的代码浏览器。显然，它仍然被一些主流的glibc目标使用，包括MIPS。（谢谢@zwol）。

因此，改变这段代码的动机比你想象的要低。

这是比特黑客代码(https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord）并不是在服务器/台式机/笔记本电脑/智能手机上运行的。它比简单的每次字节循环要好，但与现代CPU的高效asm相比，即使是这种bithack也相当糟糕（尤其是x86，其中AVX2 SIMD允许使用一对指令检查32个字节，如果数据在现代CPU上的L1d缓存中处于热状态，并且具有2/时钟向量负载和ALU吞吐量，则允许主循环中的每个时钟周期检查32到64个字节。例如，对于启动开销不占主导地位的中型字符串。）

glibc使用动态链接技巧将strlen解析为CPU的最佳版本，因此即使在x86中也有SSE2版本（16字节向量，x86-64的基线）和AVX2版本（32字节向量）。

x86在向量寄存器和通用寄存器之间具有高效的数据传输，这使得使用SIMD在循环控制依赖于数据的隐式长度字符串上加速函数非常好pcmpeqb/pmovmskb可以一次测试16个单独的字节。

GLEBC有一个类似于使用AdvSIMD的AArch64版本，还有一个用于AArch64处理器的版本，其中矢量-

同样相关：为什么启用优化后，代码速度会慢6.5倍？有更多关于x86 asm forstrlen的快与慢的详细信息，它有一个大的缓冲区和一个简单的asm实现，可能有助于gcc了解如何内联。（一些gcc版本不明智地内联rep scasb，速度非常慢，或者像这样一次4字节的bithack。因此gcc的内联strlen配方需要更新或禁用。）

Asm没有C风格的“未定义行为”；无论您喜欢什么方式访问内存中的字节都是安全的，包含任何有效字节的对齐加载都不会出错。内存保护与页面粒度一致；比这窄的对齐访问不能跨越页面边界。在x86和x64上读取同一页中的缓冲区末尾是否安全？同样的推理也适用于此C hack让编译器为该函数的独立非内联实现创建的机器代码。

当编译器发出代码来调用一个未知的非内联函数时，它必须假设函数修改任何/所有全局变量和它可能有指针指向的任何内存。也就是说，除了没有地址转义的本地变量之外的所有东西都必须在同步中通话中的记忆。显然，这适用于用asm编写的函数，也适用于库函数。如果不启用链接时优化，它甚至适用于单独的翻译单元（源文件）。

最重要的因素是，这个strlen不能嵌入任何其他内容。这样做不安全；它包含严格的别名UB（通过无符号长*读取字符数据）char*可以别名其他任何内容，但反之则不正确。

这是用于提前编译库（glibc）的库函数。它不会将链接时间优化内联到调用方。这意味着它只需编译为独立版本的strlen的安全机器代码。它不必是便携式/安全的。

GNUC库只需使用GCC进行编译。显然，不支持用clang或ICC编译它，即使它们支持GNU扩展。GCC是一种先进的编译器，可以将C源文件转换为机器代码的目标文件。不是解释器，所以除非它在编译时内联，否则内存中的字节就是内存中的字节。i、 e.当不同类型的访问发生在不同的函数中，而这些函数之间没有内联时，严格的别名并没有危险。

请记住，strlen的行为由ISO C标准定义。该函数名是实现的一部分。GCC等编译器甚至将名称视为内置函数，除非您使用-fno内置strlen，因此strlen（“foo”）可以是编译时常量3。库中的定义仅在gcc决定实际发出对它的调用时使用，而不是内联它自己的配方或其他东西。

当编译器在编译时看不到UB时，您会得到正常的机器代码。机器代码必须适用于no-UB情况，即使您想这样做，也没有办法检测调用方用于将数据放入指向内存的类型。

Glibc被编译成一个独立的静态或动态库，不能与链接时间优化内联。glibc的构建脚本不会创建“胖”静态库，其中包含机器代码gcc GIMPLE内部表示，以便在内联到程序时优化链接时间。（即，libc.a将不参与-flto链接时间优化到主程序中。）以这种方式构建glibc在实际使用该.c的目标上可能不安全。

事实上，正如@zwol所评论的，LTO不能在构建glibc本身时使用，因为这样的“脆弱”代码可能会在glibc源文件之间内联时中断。（strlen有一些内部用法，例如，可能作为printf实现的一部分）

这个strlen做了一些假设：

• CHAR_BIT是8的倍数。在所有GNU系统上都是如此。POSIX 2001甚至保证CHAR_BIT==8。（对于具有CHAR_BIT=16或32的系统来说，这看起来是安全的，就像一些DSP一样；如果sizeof（long）=sizeof（char）=1，unlined-prologue循环将始终运行0次迭代，因为每个指针总是对齐的p

这两个是不可能的，它们只是不可移植到一些C实现。这段代码是（或曾经是）C实现的一部分，在它工作的平台上，所以这很好。

下一个假设是潜在的UB：

• 包含任何有效字节的对齐加载都不会出错，只要忽略实际需要的对象之外的字节，它是安全的。（在每个GNU系统和所有普通CPU上的asm中都是如此，因为内存保护是以对齐的页面粒度进行的。在x86和x64上读取同一页面中的缓冲区结尾是否安全？在C中，当UB在编译时不可见时是安全的。如果没有内联，这里就是这种情况。编译器无法证明读取超过第一个缓冲区t0是UB；它可以是一个包含{1,2,0,3}的Cchar[]数组（例如）

最后一点是什么使得读超过C对象的结尾是安全的。即使在内联当前编译器时，这也是非常安全的，因为我认为他们目前不认为暗示执行路径是不可访问的。但是不管怎样，如果你让它内联，严格的混淆现象已经是一个搅局者了。

然后你就会遇到像Linux内核的旧的不安全的memcpyCPP宏这样的问题，它使用指针强制转换到无符号长（gcc、严格混淆现象和恐怖故事）。（现代Linux使用-fno-严格-混淆现象编译，而不是小心may_alias属性。）

这个strlen可以追溯到这样一个时代，那时你一般都可以逃避这样的事情；在GCC3之前，它是非常安全的，即使没有“仅当不内联时”的警告。

（例如，在一个char buf[]上调用它，而不是在一个无符号长[]转换为const char*的数组上调用它）。一旦机器代码被固定下来，它只是在处理内存中的字节。非内联函数调用必须假定被调用方读取任何/所有内存。

GCC type属性may\u alias为类型提供与char*相同的别名处理。（由@KonradBorowsk建议）。GCC标头目前将其用于x86 SIMD向量类型，如\uuuuM128i，因此您可以始终安全地执行\uMM\uLoaduSI128（（\uuuM128i*）foo）。（请参阅“在硬件SIMD向量指针和相应类型之间重新解释”是否为未定义行为？有关这是什么意思和不是什么意思的更多详细信息。）

strlen(const char *char_ptr)
{
  typedef unsigned long __attribute__((may_alias)) aliasing_ulong;

  // handle unaligned startup somehow, e.g. check for page crossing then check an unaligned word
  // else check single bytes until an alignment boundary.
  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;

  for (;;) {
     // alignment still required, but can safely alias anything including a char[]
     unsigned long ulong = *longword_ptr++;

     ...
  }
}

您可以使用对（1）表示一个类型，对（T）=1。
typedef无符号长__attribute__（（may_alias，对齐（1）））unaligned_aliasing_ulong；。这对于strlen的未对齐启动部分可能很有用，如果您不只是在第一个对齐边界之前执行char-at-a-time。（主循环需要对齐，这样如果终止符正好在未映射页面之前，就不会出错。）

在ISO中表示别名加载的一种可移植方法是使用memcpy，现代编译器知道如何将其作为单个加载指令内联。例如

   unsigned long longword;
   memcpy(&longword, char_ptr, sizeof(longword));
   char_ptr += sizeof(longword);

这也适用于未对齐的负载，因为memcpy的工作方式类似于通过char-at-a-time访问。但是在实践中，现代编译器非常理解memcpy。

这里的危险是，如果GCC不能确定char_ptr是字对齐的，它就不会在一些可能不支持asm中未对齐负载的平台上内联它。MIPS在MIPS64r6之前，或更早的ARM。如果你有一个实际的函数调用memcpy只是为了加载一个单词（并把它留在其他内存中），那将是一场灾难。GCC有时可以看到代码何时对齐指针。或者在到达ulong边界的char-at-a-time循环之后，您可以使用
p=__builtin_assume_aligned（p， sizeof（无符号长））；

这并没有避免可能的UB，但是对于当前的GCC来说，这在实践中并不危险。

当您希望一个广泛使用的标准库函数的每一点性能时，手动优化的asm可能会更好。特别是像memcpy这样的东西，但也包括strlen。在这种情况下，将C与x86内部函数结合使用以利用SSE2不会容易得多。

但在这里，我们只是讨论一个没有任何ISA特定功能的naive vs.bithack C版本。

（我认为我们可以将其视为一种假设，strlen已经得到了广泛的应用，因此让它尽可能快地运行是很重要的。因此问题变成了我们能否从更简单的源代码中获得高效的机码。不，我们不能。）

当前的GCC和clang不能自动向量化循环，其中迭代计数在第一次迭代之前是未知的。（例如，在运行第一次迭代之前，必须能够检查循环是否将运行至少16次迭代。）是可能的（显式长度缓冲区），但不是strcpy或strlen（隐式长度字符串），给定当前编译器。

这包括搜索循环，或任何其他具有依赖于数据的if（）break的循环以及计数器。

ICC（英特尔x86编译器）可以自动矢量化一些搜索循环，但仍然只能为简单/朴素的Cstrlen创建朴素的每次字节asm，就像OpenBSD的libc使用的那样。（锁销）。（来自@Peske的回答）。

手工优化的libcstrlen对于当前编译器的性能是必需的。当主内存可以保持大约8个字节/周期，而L1d缓存可以提供16到64个字节/周期时，一次运行1个字节（在宽超标量CPU上可能每个周期展开2个字节）是可悲的。（自从Haswell和Ryzen以来，现代主流x86 CPU的每个周期加载2个32字节。不包括AVX512，因为它可以降低时钟速度，只使用512位向量；这就是为什么glibc可能不急于添加AVX512版本。尽管有256位向量，AVX512VL BW屏蔽比较成一个屏蔽和ktest或kortest可以通过减少其UOP/迭代，使strlen更加超线程友好。）

我在这里包括非x86，即“16字节”。e、 g.我认为，大多数AARC64 CPU至少可以做到这一点，有些甚至可以做到更多。还有一些具有足够的执行吞吐量，使strlen能够跟上负载带宽。

当然，处理大字符串的程序通常应该跟踪长度，以避免经常重复查找隐式长度C字符串的长度。但短到中等长度的性能仍然受益于手写实现，我相信有些程序最终会在中等长度的字符串上使用strlen。

Answer 3

您不需要也不应该编写这样的代码——尤其是如果您不是C编译器/标准库供应商。它是用来实现strlen的代码，带有一些非常可疑的速度黑客和假设（没有用断言测试或在评论中提到）：

• 无符号长为4或8字节

更重要的是，一个好的编译器甚至可以替换按原样编写的代码

size_t stupid_strlen(const char s[]) {
    size_t i;
    for (i=0; s[i] != '\0'; i++)
        ;
    return i;
}

（请注意，它必须是与size_t兼容的类型），编译器内置于strlen的内联版本，或者将代码矢量化；但是编译器不太可能优化复杂的版本。

C11 7.24.6.3将strlen的功能描述为：

描述

退换商品

现在，如果s指向的字符串位于一个字符数组中，其长度刚好足以包含字符串和终止NUL，那么如果我们通过null终止符访问字符串，则行为将是未定义的，例如在

char *str = "hello world";  // or
char array[] = "hello world";

因此，在完全可移植/符合标准的C中，正确实现这一点的唯一方法是在你的问题中写入它的方式，除了琐碎的转换——你可以通过展开循环等来假装更快，但它仍然需要完成一个一次字节。

（正如评论者所指出的，当严格的可移植性负担太大时，利用合理或已知安全的假设并不总是一件坏事。尤其是在代码中，这是一个特定的C实现的一部分。但是在知道如何/何时可以改变规则之前，你必须了解规则。）

链接的strlen实现首先单独检查字节，直到指针指向无符号长的自然4或8字节对齐边界。C标准说访问一个没有正确对齐的指针有未定义的行为，所以这绝对是为了让下一个肮脏的把戏变得更肮脏。（在x86以外的一些CPU体系结构上，错误对齐的字或双字负载会出错。C不是可移植的汇编语言，但是这段代码就是这样使用它的）。这也使得在内存保护工作在对齐块（例如4kiB虚拟内存页）中的实现中，可以读取对象的末尾，而不会有出错的风险。

现在到了肮脏的部分：代码打破promise，一次读取4或8个8位字节（一个long int），并使用带无符号加法的位技巧来快速计算这4个字节中是否有零字节或8字节-它使用巧尽心思构建的数字，这将导致进位改变被位掩码捕获的位。本质上，这将计算出掩码中的4或8个字节中是否有任何一个是零，据说比循环这些字节更快。最后，在结尾处有一个循环来找出哪个字节是第一个零（如果有的话），并返回结果。

最大的问题是，在sizeof（无符号长）-1倍的sizeof（无符号长）的情况下，它将读取超过字符串的末尾-只有当空字节在最后访问的字节（即：在小端最重要，在大端最不重要），它不访问数组出界！

即使用于在C标准库中实现strlen，该代码也是糟糕的代码。它有几个实现定义和未定义的方面，不应在任何地方使用它，而应使用提供的系统strlen-我在这里将函数重命名为the_strlen，并添加了以下main：

int main(void) {
    char buf[12];
    printf("%zu\n", the_strlen(fgets(buf, 12, stdin)));
}

缓冲区的大小经过仔细调整，以便它能够准确地容纳hello world字符串和终止符。然而，在我的64位处理器上，无符号长是8字节，因此对后一部分的访问将超过此缓冲区。

如果现在使用-fsanize=undefined和-fsanize=address编译并运行生成的程序，我会得到：

% ./a.out
hello world
=================================================================
==8355==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340
READ of size 8 at 0x7ffffe63a3f8 thread T0
    #0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b)
    #1 0x55fbec46b139 in main (.../a.out+0x2139)
    #2 0x7f4f0848fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x55fbec46a949 in _start (.../a.out+0x1949)

Address 0x7ffffe63a3f8 is located in stack of thread T0 at offset 40 in frame
    #0 0x55fbec46b07c in main (.../a.out+0x207c)

  This frame has 1 object(s):
    [32, 44) 'buf' <== Memory access at offset 40 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (.../a.out+0x1b6b) in the_strlen
Shadow bytes around the buggy address:
  0x10007fcbf420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007fcbf470: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04]
  0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==8355==ABORTING

即坏事发生了。