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

Question

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

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的代码有一些非常可疑的速度黑客和假设(没有用断言测试或在评论中提到):

unsigned long是 4 或 8 个字节

字节为 8 位

可以将指针强制转换为 unsigned long long而不是 uintptr_t

可以简单地通过检查 2 或 3 个最低位是否为零来对齐​​指针

可以访问字符串为 unsigned long s

可以读取数组的末尾而不会产生任何不良影响。

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

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

(请注意，它必须是与 size_t 兼容的类型)，带有内置编译器的内联版本 strlen ，或向量化代码；但是编译器不太可能优化复杂版本。
strlen函数由 C11 7.24.6.3 描述作为:

Description

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

Returns

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

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

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

所以真的是完全可移植/符合标准的 C 语言实现这个的唯一方法 正确 你的 就是这么写的问题 ，除了微不足道的转换 - 您可以通过展开循环等来假装更快，但它仍然需要一次完成一个字节。
(正如评论者所指出的那样，当严格的可移植性负担过重时，利用合理或已知安全的假设并不总是一件坏事。尤其是在作为特定 C 实现的一部分的代码中。但您必须了解在知道如何/何时可以弯曲它们之前，规则。)

已链接 strlen实现首先单独检查字节，直到指针指向 unsigned long 的自然 4 或 8 字节对齐边界为止。 . C 标准说访问未正确对齐的指针具有 未定义的行为 ，所以这绝对是为了让下一个肮脏的把戏变得更脏。 (实际上，在 x86 以外的某些 CPU 体系结构上，未对齐的字或双字加载会出错。C 不是可移植的汇编语言，但此代码以这种方式使用它)。这也是可以读取对象末尾而不会在内存保护在对齐块(例如 4kiB 虚拟内存页面)中工作的实现中出现故障的风险的原因。
现在到了肮脏的部分:代码违反了 promise 并一次读取 4 或 8 个 8 位字节(a long int)，并使用一个带有无符号加法的小技巧来快速找出其中是否有任何零字节4 或 8 个字节 - 它使用特制的数字来导致进位位更改位掩码捕获的位。本质上，这将确定掩码中的 4 或 8 个字节中的任何一个是否为零，据说 更快 而不是循环遍历这些字节中的每一个。最后有一个循环，以确定哪个字节是第一个零(如果有)，并返回结果。
最大的问题是在 sizeof (unsigned long) - 1超时 sizeof (unsigned long)情况下它将读取超过字符串的末尾 - 仅当空字节在最后访问的字节中(即在小端中最重要，在大端中最不重要)，它是否不会访问数组界限!

代码，即使用于实现 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

即发生了不好的事情。