为什么glibc的strlen要这么复杂才能快运行？

Question

我正在查看 strlen 代码 here，我想知道是否真的需要代码中使用的优化？例如，为什么像下面这样的东西不能同样好或更好？

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

更简单的代码不是更好and/or编译器更容易优化吗？

link 后面的页面上 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 (tege@sics.se),
   with help from Dan Sahlin (dan@sics.se);
   commentary by Jim Blandy (jimb@ai.mit.edu).

   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 == '[=12=]')
      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中，可以对效率进行详细推理。

与一次测试多个字节相比，遍历单个字符查找 null 的效率较低，如此代码所示。

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

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

像这样关注效率的一个地方是在标准库中，就像您链接的示例一样。

如果您想阅读更多关于单词边界的信息，请参阅this question, and this excellent wikipedia page

我也认为的讨论更加清晰和详细。

Answer 2

您不需要并且您永远不应该编写这样的代码——尤其是如果您不是 C 编译器/标准图书馆供应商。它是用于实现 strlen 的代码，带有一些非常可疑的速度黑客和假设（未使用断言测试或在评论中提及）：

unsigned long 是 4 或 8 个字节
字节是8位
可以将指针转换为 unsigned long long 而不是 uintptr_t
只需检查 2 或 3 个最低位为零即可对齐指针
一个人可以访问一个字符串作为 unsigned longs
可以读取数组末尾而不会产生任何不良影响。

更重要的是，一个好的编译器甚至可以替换写成

的代码

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

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

strlen函数被C11 7.24.6.3描述为：

Description

The strlen function computes the length of the string pointed to by s.

Returns

The strlen function returns the number of characters that precede the terminating null character.

现在，如果 s 指向的字符串在字符数组中的长度刚好足以包含字符串和终止 NUL，则行为将是undefined 如果我们访问空终止符之后的字符串，例如在

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

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

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

链接的 strlen 实现首先单独检查字节，直到指针指向 unsigned long 的自然 4 或 8 字节对齐边界。 C 标准规定访问未正确对齐的指针具有 未定义的行为 ，因此绝对必须这样做才能使下一个肮脏的技巧更加肮脏。（实际上，在 x86 以外的某些 CPU 体系结构上，未对齐的字或双字加载会出错。C 是不是可移植的汇编语言，但此代码以这种方式使用它).这也使得读取对象末尾成为可能，而不会在内存保护在对齐块（例如 4kiB 虚拟内存页面）中工作的实现中出现错误风险。

现在是肮脏的部分：代码 破坏了 承诺并一次读取 4 或 8 个 8 位字节（long int），并使用使用无符号加法的位技巧可以快速找出在这 4 或 8 个字节中是否有 any 零字节 - 它使用特制的数字来导致进位位改变位被一个位面具抓住了。从本质上讲，这将找出掩码中的 4 或 8 个字节中的任何一个是否为零，据推测 比循环遍历每个字节更快 。最后有一个循环来找出哪个字节是第一个零（如果有的话），然后 return 结果。

最大的问题是，在 sizeof (unsigned long) 的情况下，在 sizeof (unsigned long) - 1 的情况下，它会读取到字符串的末尾 - 只有空字节位于 last访问的字节（即小端最重要，大端最不重要），是否不越界访问数组！

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

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

缓冲区的大小经过精心设计，可以准确容纳 hello world 字符串和终止符。但是在我的 64 位处理器上，unsigned long 是 8 个字节，因此对后一部分的访问将超过此缓冲区。

如果我现在用 -fsanitize=undefined 和 -fsanitize=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

即坏事发生了。

Answer 3

简而言之：在一次可以获取大量数据的架构上逐字节检查字符串可能会很慢。

如果空终止检查可以在 32 位或 64 位基础上完成，它会减少编译器必须执行的检查量。考虑到特定系统，这就是链接代码试图做的事情。他们对寻址、对齐、缓存使用、非标准编译器设置等做出假设。

在您的示例中逐字节读取在 8 位 CPU 上或在编写用标准 C 编写的可移植库时是一种明智的方法。

查看 C 标准库以获取有关如何编写 fast/good 代码的建议并不是一个好主意，因为它不可移植并且依赖于非标准假设或定义不明确的行为。如果您是初学者，阅读此类代码可能比教育更有害。

Answer 4

您希望代码正确、可维护且快速。这些因素具有不同的重要性：

"correct"绝对必要。

"maintainable" 取决于您要维护代码的程度：strlen 40 多年来一直是标准 C 库函数。它不会改变。因此，可维护性对于这个功能来说并不重要。

"Fast"：在许多应用程序中，strcpy、strlen 等使用了大量的执行时间。要通过改进编译器来实现与这个复杂但不是很复杂的 strlen 实现相同的整体速度增益，需要付出巨大的努力。

速度快还有另一个优势：当程序员发现调用 "strlen" 是他们可以测量字符串中字节数的最快方法时，他们就不会再想自己编写代码来制作东西了快点。

因此，对于 strlen，速度比您将要编写的大多数代码重要得多，而可维护性则不那么重要。

为什么一定要这么复杂？假设您有一个 1,000 字节的字符串。简单的实现将检查 1,000 个字节。当前的实现可能会一次检查 64 位字，这意味着 125 个 64 位或八字节字。它甚至可能使用矢量指令一次检查 32 个字节，这会更复杂，甚至更快。使用向量指令会导致代码稍微复杂一点但非常简单，检查 64 位字中八个字节中的一个是否为零需要一些巧妙的技巧。因此，对于中长字符串，这段代码的速度预计会快四倍。对于像 strlen 这样重要的函数，值得编写一个更复杂的函数。

PS。代码不是很便携。但它是标准 C 库的一部分，是实现的一部分——它不需要可移植。

PPS。有人发布了一个示例，其中调试工具抱怨访问字符串末尾之后的字节。可以设计一个保证以下内容的实现：如果 p 是指向字节的有效指针，那么根据 C 标准，对同一对齐块中的字节的任何访问都是未定义的行为，将 return 一个未指定的价值。

PPPS。英特尔已将指令添加到其后来的处理器中，这些指令构成了 strstr() 函数（在字符串中查找子字符串）的构建块。他们的描述令人难以置信，但他们可以使该特定功能的速度可能提高 100 倍。（基本上，给定一个包含 "Hello, world!" 的数组 a 和一个以 16 个字节 "HelloHelloHelloH" 开头且包含更多字节的数组 b，它会计算出字符串 a 不会早于从索引 15 开始出现在 b 中).

Answer 5

除了这里的出色答案外，我想指出问题中链接的代码是针对 GNU 实现的 strlen。

OpenBSD implementation of strlen 与问题中提出的代码非常相似。实现的复杂度由作者决定。

...
#include <string.h>

size_t
strlen(const char *str)
{
    const char *s;

    for (s = str; *s; ++s)
        ;
    return (s - str);
}

DEF_STRONG(strlen);

编辑：我上面链接的 OpenBSD 代码看起来是没有自己的 asm 实现的 ISA 的后备实现。 strlen 根据体系结构有不同的实现。 amd64 strlen, for example, is asm. Similar to PeterCordes' comments/ 的代码指出非后备 GNU 实现也是 asm。

Answer 6

简而言之，这是标准库可以通过了解它使用什么编译器来进行的性能优化 - 你不应该编写这样的代码，除非你正在编写标准库并且可以依赖于特定的编译器.具体来说，它同时处理对齐字节数——在 32 位平台上为 4 个，在 64 位平台上为 8 个。这意味着它可以比简单的字节迭代快 4 或 8 倍。

要解释这是如何工作的，请考虑下图。这里假设32位平台（4字节对齐）。

假设 "Hello, world!" 字符串的字母 "H" 作为参数提供给 strlen。因为 CPU 喜欢在内存中对齐（理想情况下，address % sizeof(size_t) == 0），对齐前的字节使用慢速方法逐字节处理。

然后，对于每个对齐大小的块，通过计算 (longbits - 0x01010101) & 0x80808080 != 0 它检查整数中的任何字节是否为零。当至少一个字节高于 0x80 时，此计算会出现误报，但通常情况下它应该有效。如果不是这种情况（因为它在黄色区域），则长度会增加对齐大小。

如果整数中的任何字节结果为零（或 0x81），则逐字节检查字符串以确定零的位置。

这可能会导致越界访问，但是因为它在一个对齐范围内，所以很可能没问题，内存映射单元通常没有字节级精度。

Answer 7

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

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

在 x86 和 ARM 等流行的 ISA 上，glibc 使用手写 asm

因此，更改此代码的任何内容的动机比您想象的要低。

这个 bithack 代码 (https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord) 并不是 server/desktop/laptop/smartphone 上的运行。它比一个简单的一次一个字节的循环要好，但是 与现代 CPUs 的高效 asm 相比，即使这个 bithack 也很糟糕（尤其是 AVX2 SIMD 允许的 x86使用几条指令检查 32 字节，如果现代 CPUs 上的 L1d 缓存中的数据很热，则主循环中每个时钟周期允许 32 到 64 字节，具有 2/时钟向量加载和 ALU 吞吐量。即对于中型启动开销不占主导地位的字符串。）

glibc 使用动态 linking 技巧将 strlen 解析为您的 CPU 的最佳版本，因此即使在 x86 中也有一个 SSE2 version (16-byte vectors, baseline for x86-64) and an AVX2 version（32 字节向量).

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

glibc 有一个类似 using AdvSIMD, and a version for AArch64 CPUs where vector->GP registers stalls the pipeline, so it does actually use this bithack 的 AArch64 版本。但是一旦命中就使用计数前导零来查找寄存器内字节，并在检查页面交叉后利用 AArch64 的高效未对齐访问。

也相关：有一些关于 x86 asm 中快与慢的更多细节，对于 strlen 具有大缓冲区和简单的 asm 实现，这可能有助于 gcc 了解如何内联。（一些 gcc 版本不明智地内联 rep scasb 这非常慢，或者像这样一次 4 字节的 bithack。因此 GCC 的 inline-strlen 配方需要更新或禁用。）

Asm 没有 C 风格的“未定义行为”；随心所欲地访问内存中的字节是安全的，并且包含任何有效字节的对齐加载不会出错。内存保护以对齐页面粒度发生；比不能跨越页面边界更窄的对齐访问。同样的推理适用于此 C hack 让编译器为该函数的独立非内联实现创建的机器码。

当编译器发出代码来调用未知的非内联函数时，它必须假定该函数修改 any/all 全局变量和它可能具有指针的任何内存。也就是说，除了本地人之外，没有地址转义的所有内容都必须在整个调用过程中在内存中保持同步。这显然适用于用 asm 编写的函数，也适用于库函数。如果您不启用 link 时间优化，它甚至适用于单独的翻译单元（源文件）。

为什么这是安全的作为 glibc 的一部分，但不是否则。

最重要的因素是这个 strlen 不能内联到其他任何东西。 这样做不安全；它包含 strict-aliasing UB（通过 unsigned long* 读取 char 数据）。 char* 可以为其他任何东西起别名 but the reverse is not true.

这是提前编译库 (glibc) 的库函数。 它不会通过 link-time-optimization 内联到调用者中。 这意味着它只需要编译为独立版本的安全机器代码 strlen.它不一定是便携式/安全 C.

GNU C库只需要用GCC编译。显然用 clang 或 ICC 编译它是，即使它们支持 GNU 扩展。 GCC 是一种提前编译器，可将 C 源文件转换为机器代码的目标文件。不是解释器，所以除非它在编译时内联，否则内存中的字节只是内存中的字节。即，当不同类型的访问发生在不相互内联的不同函数中时，严格别名 UB 并不危险。

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

当 UB 在编译时 对编译器 不可见时，您将获得正常的机器代码。机器代码必须适用于无 UB 情况，即使您想要，asm 也无法检测调用者使用什么类型将数据放入指定的-记忆。

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

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

这个strlen做了一些假设：

CHAR_BIT是8的倍数。在所有 GNU 系统上都是如此。 POSIX2001连保CHAR_BIT == 8。（对于具有 CHAR_BIT= 16 或 32 的系统，这看起来是安全的，例如某些 DSP；如果 sizeof(long) = sizeof(char) = 1，未对齐序言循环将始终运行 0 次迭代，因为每个指针始终对齐并且p & sizeof(long)-1 始终为零。）但是如果您有一个非 ASCII 字符集，其中字符为 9 或 12 位宽，则 0x8080... 是错误的模式。
（可能）unsigned long 是 4 或 8 个字节。或者它可能实际上适用于任何大小的 unsigned long 最多 8，并且它使用 assert() 来检查它。

这两个不可能是 UB，它们只是某些 C 实现的不可移植性。此代码是（或曾经是） C 实现的一部分，在它确实可以工作的平台上，所以没关系。

下一个假设是潜在的C UB：

包含任何有效字节的对齐加载不会出错，只要您忽略实际需要的对象之外的字节，它就是安全的。（在每个 GNU 系统和所有正常 CPUs 上的 asm 中都是正确的，因为内存保护发生在对齐的页面粒度。在编译时 UB 不可见时在 C 中是安全的。没有内联，这里就是这种情况。编译器无法证明读取第一个 0 是 UB；它可能是一个包含 {1,2,0,3} 的 C char[] 数组，例如）

最后一点是可以安全地读取 C 对象末尾的原因。即使在当前编译器内联时，这也非常安全，因为我认为他们目前不认为暗示执行路径是不可到达的。但是无论如何，如果你让这个内联，那么严格的别名已经是一个问题了。

然后你会遇到像 Linux 内核旧的不安全 memcpy CPP 宏 这样的问题，它使用指向 unsigned long 的指针转换（ gcc, strict-aliasing, and horror stories)。（现代 Linux 使用 -fno-strict-aliasing 编译，而不是小心使用 may_alias 属性。）

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

只有越过 call/ret 边界才能看到的 UB 不会伤害我们。（例如，在 char buf[] 上调用它，而不是在 unsigned long[] 的数组上调用转换为 const char*）。一旦机器代码一成不变，它就只是处理内存中的字节。非内联函数调用必须假定被调用方读取 any/all 内存。

安全地写这个，没有严格别名的 UB

GCC type attribute may_alias gives a type the same alias-anything treatment as char*. (Suggested by @KonradBorowsk). GCC headers currently use it for x86 SIMD vector types like __m128i so you can always safely do _mm_loadu_si128( (__m128i*)foo ). (See 了解有关其含义和不含义的更多详细信息。）

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++;

     ...
  }
}

您可以使用 aligned(1) 来表达一个带有 alignof(T) = 1 的类型。
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;。这对于 strlen 的未对齐启动部分可能很有用，如果您不只是在第一个对齐边界之前一次执行一个字符的话。（主循环需要对齐，这样如果终止符就在未映射的页面之前，您就不会出错。）

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

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

这也适用于未对齐的加载，因为 memcpy 就像一次 char 访问一样工作。但在实践中，现代编译器理解 memcpy 非常好。

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

这并不能避免读取对象可能的 UB，但对于当前的 GCC，这在实践中并不危险。

为什么需要手动优化的 C 源代码：当前的编译器不够好

当您希望为广泛使用的标准库函数提供最后一滴性能时，手动优化的 asm 可能会更好。特别是 memcpy，还有 strlen。在这种情况下，使用带有 x86 内在函数的 C 来利用 SSE2 并不会容易得多。

但这里我们只是在谈论没有任何 ISA 特定功能的简单 vs. bithack C 版本。

（我认为我们可以假定 strlen 的使用范围足够广泛，因此使其尽可能快地运行很重要。所以问题就变成了我们是否可以获得高效的机器来自更简单来源的代码。不，我们不能。）

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

这包括搜索循环，或任何其他具有数据相关 if()break 和计数器的循环。

ICC（Intel 的 x86 编译器）可以自动矢量化一些搜索循环，但仍然只为简单/朴素的 C strlen 像 OpenBSD 的 libc 使用的那样生成朴素的一次字节 asm。 (Godbolt). (From ).

手动优化的 libc strlen 对于当前编译器 的性能是必需的。一次 1 个字节（在宽超标量 CPUs 上每个周期可能展开 2 个字节）是可悲的，因为主内存每个周期可以跟上大约 8 个字节，而 L1d 缓存每个周期可以提供 16 到 64 个字节。（自 Haswell 和 Ryzen 以来，在现代主流 x86 CPUs 上每个周期加载 2x 32 字节。不计算 AVX512，它可以降低时钟速度只是为了使用 512 位向量；这就是为什么 glibc 可能并不着急添加一个 AVX512 版本。尽管使用 256 位向量，AVX512VL + BW masked compare into a mask and ktest or kortest can make strlen more hyperthreading friendly by reducing its uops / iteration. )

我在这里包括非 x86，即“16 字节”。例如大多数 AArch64 CPUs 至少可以做到这一点，我认为，有些肯定更多。有些有足够的执行吞吐量 strlen 来跟上负载带宽。

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

Answer 8

其他答案未提及的一件重要事情是，FSF 非常谨慎地确保专有代码不会进入 GNU 项目。在 GNU Coding Standards under Referring to Proprietary Programs 中，有一条关于以一种不会与现有专有代码混淆的方式组织您的实现的警告：

Don’t in any circumstances refer to Unix source code for or during your work on GNU! (Or to any other proprietary programs.)

If you have a vague recollection of the internals of a Unix program, this does not absolutely mean you can’t write an imitation of it, but do try to organize the imitation internally along different lines, because this is likely to make the details of the Unix version irrelevant and dissimilar to your results.

For example, Unix utilities were generally optimized to minimize memory use; if you go for speed instead, your program will be very different.

（强调我的。）

Answer 9

why wouldn't something like the following work equally good or better?

// OP's code - what is needed to portably function correctly?
unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '[=10=]'; i++)
        continue;
    return i;
}

OP 的代码存在功能错误。

虽然修改起来很容易。

在编写可移植代码时，需要注意首先使函数正确，然后再寻求性能改进。

即使是非常简单、看似正确的代码也可能在功能上存在缺陷。

类型

一个字符串长度在size_t范围内，可能与unsigned long不同。函数签名问题与 size_t (*f)() = strlen 不匹配。 ULONG_MAX < SIZE_MAX 和字符串长度很大的不常见平台的问题。

const

s 应该是 const char *.

非2的补码

（这个问题影响了今天极少数的处理器，所以实际上只是一个迂腐的问题。非 2 的补码可能会在下一个 C（C23？）中得到规范）。

当 char 是 有符号 而不是 2 的补码时，s[i] != '[=19=]' 可能会在 -0 上触发。它不应该。 str...() 函数就像字符被访问为 unsigned char.

For all functions in this subclause, each character shall be interpreted as if it had the type unsigned char (and therefore every possible object representation is valid and has a different value).

修复OP简单代码的这些方面

size_t strlen(const char *s) {
    size_t i;
    for (i = 0; ((const unsigned char *)s)[i] != '[=11=]'; i++)
        continue;
    return i;
}

现在有了一个更好的、便携的 strlen() 候选者，将其与“复杂”的替代品进行比较。

为什么glibc的strlen要这么复杂才能快运行？

Why does glibc's strlen need to be so complicated to run quickly?

c

optimization

portability

glibc

strlen

在 x86 和 ARM 等流行的 ISA 上，glibc 使用手写 asm

为什么这是安全的作为 glibc 的一部分，但不是否则。

安全地写这个，没有严格别名的 UB

为什么需要手动优化的 C 源代码：当前的编译器不够好

为什么glibc的strlen要这么复杂才能快运行？

Why does glibc's strlen need to be so complicated to run quickly?

c

optimization

portability

glibc

strlen

在 x86 和 ARM 等流行的 ISA 上，glibc 使用手写 asm

为什么这是安全的 作为 glibc 的一部分，但 不是 否则。

安全地写这个，没有严格别名的 UB

为什么需要手动优化的 C 源代码：当前的编译器不够好

为什么这是安全的作为 glibc 的一部分，但不是否则。