为什么要快速运行glibc的问题太复杂了？

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 (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 == '\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

你不会需要你千万别写代码这样的-特别是如果你不是一个C编译器/标准库供应商。它是用于以strlen一些非常可疑的速度hack和假设（未经断言测试或在注释中提及）实现的代码：

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

而且，好的编译器甚至可以替换编写为

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功能描述为：

描述

2. 该strlen函数计算s指向的字符串的长度。

退货

3. 该strlen函数返回终止空字符之前的字符数。

现在，如果by指向的字符串s位于字符数组中，长度足以容纳该字符串和终止NUL，则如果我们通过空终止符访问该字符串，则行为将不确定，例如

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

因此，实际上，完全可移植/符合标准的C 正确实现此目标的唯一方法是将其写入您的问题中，除了进行微不足道的转换外-您可以通过展开循环等来假装更快，但是仍然需要这样做一次一个字节。

（如评论者所指出的那样，当严格的可移植性负担太大时，利用合理或已知安全的假设并不总是一件坏事。特别是在代码中，它是一个特定C实现的一部分。但是，您必须了解在知道如何/何时弯曲它们之前先确定规则。）

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

现在到了最脏的部分：代码违反了承诺，一次读取了4或8个8位字节（a long int），并使用了一个带无符号加法的位技巧来快速找出这4或8个字节中是否有零字节字节-它使用特制的数字来导致进位更改由位掩码捕获的位。从本质上讲，这将找出掩码中4或8个字节中的任何一个是否为零比循环遍历每个字节更快。最后，最后有一个循环，找出哪个字节是第一个零（如果有的话），并返回结果。

最大的问题是，在sizeof (unsigned long) - 1偶尔的sizeof (unsigned long)情况下，它将读取超过字符串末尾的内容-仅当空字节位于最后访问的字节中时（即在Little-endian中是最高有效，而在Big-endian中是最低有效）。 ，它不会超出范围访问数组！

即使用于strlen在C标准库中实现的代码也是错误的代码。它具有几个实现定义和未定义的方面，并且不应在任何地方使用，而不是系统提供的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 2

有关此内容的一些详细信息/背景，在评论中有很多（轻微或完全）错误的猜测。

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

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

因此，对此代码进行任何更改的动机都比您想象的要低。

此bithack代码（https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord）并不是服务器/台式机/笔记本电脑/智能手机上实际运行的代码。它比幼稚的一次字节循环更好，但是与现代CPU的高效asm（尤其是x86，其中AVX2 SIMD允许通过几个指令检查32个字节，每个时钟允许32到64个字节）相比，即使是这个bithack也非常糟糕。如果现代CPU的L1d缓存中的数据很热，且具有2 /时钟矢量负载和ALU吞吐量，则在主循环中循环（例如，对于启动开销不占主导的中型字符串）。

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

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

glibc具有一个类似于AdvSIMD的AArch64版本，以及一个用于vector- > GP寄存器使管道停顿的AArch64 CPU版本，因此它确实使用了bithack。但是一旦命中就使用count-leading-zeros来查找内部寄存器字节，并在检查页面交叉之后利用AArch64的有效未对齐访问。

还相关：为什么启用优化后，此代码的速度是6.5x的慢？有关在x86 asm中strlen使用大型缓冲区和简单的asm实现的快速与慢速方式的更多详细信息，这可能对gcc知道如何内联非常有用。（某些gcc版本不明智地内联rep scasb，这非常慢，或者像这样每次4字节的bithack。因此，GCC的内联形式的食谱需要更新或禁用。）

Asm没有C风格的“不确定行为”；您可以随意访问内存中的字节，这是安全的，而且包含任何有效字节的对齐负载也不会出错。内存保护以对齐页面粒度进行；对齐的访问范围比不能跨越页面边界的范围窄。 在x86和x64的同一页面中读取缓冲区的末尾是否安全？ 同样的道理也适用于此C hack使编译器为该功能的独立非内联实现创建的机器代码。

当编译器发出代码以调用未知的非内联函数时，它必须假定该函数会修改任何/所有全局变量以及它可能具有指向的任何内存。也就是说，除了本地电话外，所有未进行地址转义的电话都必须在整个通话过程中在内存中同步。显然，这适用于用asm编写的函数，也适用于库函数。如果您未启用链接时优化，则它甚至适用于单独的翻译单元（源文件）。

为什么这作为glibc的一部分是安全的，但并非如此。

最重要的因素是，它strlen不能内联到其他任何内容。 这样做并不安全；它包含严格混叠UB（char通过读取数据unsigned long*）。 char*允许为别的东西加上别名，但是反过来不是真的。

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

GNU C库仅需与GCC一起编译。显然，即使它们支持GNU扩展，也不支持使用clang或ICC对其进行编译。GCC是一种提前编译器，可以将C源文件转换为机器代码的目标文件。不是解释器，因此除非在编译时内联，否则内存中的字节只是内存中的字节。也就是说，当具有不同类型的访问发生在彼此不内联的不同功能中时，严格别名的UB并不危险。

请记住，strlen的行为是由 ISO C标准定义的。该功能名称专门是实现的一部分。除非您使用-fno-builtin-strlen，否则像GCC这样的编译器甚至会将名称视为内置函数，因此strlen("foo")可以是编译时常量3。库中的定义仅在gcc决定实际向其发出调用而不是内联其自己的配方或其他内容时才使用。

如果在编译时UB 对编译器不可见，您将获得健全的机器代码。本机代码必须工作，为无UB的情况下，即使你想要到，有没有办法为ASM检测类型调用者用什么来把数据放到指向的内存。

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

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

这strlen有一些假设：

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

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

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

• 包含任何有效字节的对齐负载不会出错，并且只要您忽略实际想要的对象外部的字节即可，它是安全的。（在每个GNU系统和所有普通CPU上都正确存在asm，因为内存保护是使用对齐页面粒度进行的。 通过x86和x64上同一页面内缓冲区的末尾读取是否安全？在UB时在C中安全吗？在编译时不可见。在没有内联的情况下就是这种情况。编译器无法证明从第一个读取的内容0是UB；例如，它可能是一个char[]包含{1,2,0,3}以下内容的C 数组）

最后一点是使在这里可以安全地读取C对象末尾的内容。即使在与当前编译器内联时，这也是非常安全的，因为我认为他们当前不认为隐含执行路径是不可行的。但是无论如何，严格的别名已经成为热门，如果您让它内联。

然后，您将遇到类似Linux内核的旧的不安全的memcpy CPP宏的问题，该宏使用了指向unsigned long（gcc，严格混叠和恐怖故事）的指针广播。

这strlen可以追溯到您可以摆脱一般的东西的时代 ; 在没有GCC3之前没有“仅在不内联时”的警告之前，它曾经是非常安全的。

仅在跨越呼叫/重拨边界时才可见的UB不会伤害我们。（例如，在调用此char buf[]阵列上，而不是unsigned long[]浇注到一个const char*）。机器代码一成不变后，就只处理内存中的字节。非内联函数调用必须假定被调用方读取任何/所有内存。

安全地编写此文件，而无需严格混淆UB

在GCC类型属性may_alias给出了一个类型相同的别名，任何的待遇char*。（由@KonradBorowsk建议）。目前，GCC标头将其用于x86 SIMD矢量类型，__m128i因此您始终可以放心使用_mm_loadu_si128( (__m128i*)foo )。（有关此功能的含义和含义的更多详细信息，请参见在硬件向量指针和相应类型之间的“ reinterpret_cast”操作是否是未定义的行为？）

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

  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;
  for (;;) {
     unsigned long ulong = *longword_ptr++;  // can safely alias anything
     ...
  }
}

您也可以使用aligned(1)来表示类型alignof(T) = 1。
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

在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有时可以看到代码何时对齐指针。或者，在一次字符循环达到一个无限边界之后，您可以使用
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编译器）可以自动向量化某些搜索循环，但仍只能strlen像OpenBSD的libc一样，为简单的/天真C生成天真字节一次的asm 。（Godbolt）。（来自@Peske的答案）。

手动优化的libc strlen对于当前编译器的性能是必需的。当主存储器每个周期可以保持大约8个字节，并且L1d缓存每个周期可以传递16到64个字节时，一次进入1个字节（在宽的超标量CPU上每个周期可能展开2个字节）是可悲的。（自Haswell和Ryzen以来，现代主流x86 CPU上每个周期2个32字节负载。不算AVX512会仅使用512位向量而降低时钟速度；这就是为什么glibc可能不急于添加AVX512版本尽管具有256位向量，但将AVX512VL + BW屏蔽的掩码与掩码进行比较，ktest或者kortest可以strlen通过减少其uops /迭代来使更多的超线程友好。）

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

当然，使用大型字符串的程序通常应跟踪长度，以避免不得不重做频繁发现隐式长度C字符串的长度。但是中短长度的性能仍然可以从手写实现中受益，而且我敢肯定，某些​​程序的确会在中长字符串上使用strlen。

Answer 3

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

 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 4

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

的OpenBSD实现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根据架构有不同的实现。例如，amd64strlen的代码是asm。与PeterCordes的注释/ 答案相似，后者指出非后备GNU实现也为asm。

Answer 5

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

为了解释它是如何工作的，请考虑以下图像。此处假定为32位平台（4字节对齐）。

假设“世界您好！”的字母“ H” 提供字符串作为的参数strlen。因为CPU喜欢在内存中对齐（理想情况下是address % sizeof(size_t) == 0），所以对齐之前的字节将使用慢速方法逐字节处理。

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

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

这可以进行越界访问，但是由于它位于对齐范围内，因此很有可能不是很好，内存映射单元通常不具有字节级精度。

Answer 6

You want code to be correct, maintainable, and fast. These factors have different importance:

"correct" is absolutely essential.

"maintainable" depends on how much you are going to maintain the code: strlen has been a Standard C library function for over 40 years. It's not going to change. Maintainability is therefore quite unimportant - for this function.

"Fast": In many applications, strcpy, strlen etc. use a significant amount of the execution time. To achieve the same overall speed gain as this complicated, but not very complicated implementation of strlen by improving the compiler would take heroic efforts.

Being fast has another advantage: When programmers find out that calling "strlen" is the fastest method they can measure the number of bytes in a string, they are not tempted anymore to write their own code to make things faster.

So for strlen, speed is much more important, and maintainability much less important, than for most code that you will ever write.

Why must it be so complicated? Say you have a 1,000 byte string. The simple implementation will examine 1,000 bytes. A current implementation would likely examine 64 bit words at a time, which means 125 64-bit or eight-byte words. It might even use vector instructions examining say 32 bytes at a time, which would be even more complicated and even faster. Using vector instructions leads to code that is a bit more complicated but quite straightforward, checking whether one of eight bytes in a 64 bit word is zero requires some clever tricks. So for medium to long strings this code can be expected to be about four times faster. For a function as important as strlen, that's worth writing a more complex function.

PS. The code is not very portable. But it's part of the Standard C library, which is part of the implementation - it need not be portable.

PPS. Someone posted an example where a debugging tool complained about accessing bytes past the end of a string. An implementation can be designed that guarantees the following: If p is a valid pointer to a byte, then any access to a byte in the same aligned block that would be undefined behaviour according to the C standard, will return an unspecified value.

PPPS。英特尔已向其后来的处理器中添加了指令，这些指令构成了strstr（）函数的构建块（在字符串中找到子字符串）。他们的描述令人难以置信，但是它们可以使特定功能快100倍。（基本上，给定一个包含“ Hello，world！”的数组a和一个以16个字节“ HelloHelloHelloH”开头并包含更多字节的数组b，它可以确定字符串a不会早于索引15开始出现在b中） 。

Answer 7

简要地说：在每次可以获取大量数据的体系结构上，逐字节检查字符串可能会很慢。

如果对空终止的检查可以在32位或64位的基础上进行，则它将减少编译器必须执行的检查次数。这是链接代码在考虑特定系统的情况下尝试执行的操作。他们对寻址，对齐，缓存使用，非标准编译器设置等进行了假设。

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

在C标准库中寻找如何编写快速/良好代码的建议不是一个好主意，因为它将是不可移植的，并且依赖于非标准的假设或定义不明确的行为。如果您是初学者，那么阅读此类代码可能比教育更具危害性。