Code
2024-04-04 07:00:04

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

我正在查看这里的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)

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

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

当前回答

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

Unsigned long是4或8字节 字节是8位 一个指针可以转换为unsigned long long而不是uintptr_t 只需检查最低的2或3位是否为零，就可以对指针进行对齐 可以将字符串作为无符号长字符串访问 可以读取数组的末尾而没有任何不良影响。

更重要的是，一个好的编译器甚至可以取代编写为

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函数描述为:

描述 strlen函数的作用是:计算s指向的字符串长度。 返回 函数的作用是:返回终止空字符前的字符数。

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

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

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

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

The linked strlen implementation first checks the bytes individually until the pointer is pointing to the natural 4 or 8 byte alignment boundary of the unsigned long. The C standard says that accessing a pointer that is not properly aligned has undefined behaviour, so this absolutely has to be done for the next dirty trick to be even dirtier. (In practice on some CPU architecture other than x86, a misaligned word or doubleword load will fault. C is not a portable assembly language, but this code is using it that way). It's also what makes it possible to read past the end of an object without risk of faulting on implementations where memory protection works in aligned blocks (e.g. 4kiB virtual memory pages).

Now comes the dirty part: the code breaks the promise and reads 4 or 8 8-bit bytes at a time (a long int), and uses a bit trick with unsigned addition to quickly figure out if there were any zero bytes within those 4 or 8 bytes - it uses a specially crafted number to that would cause the carry bit to change bits that are caught by a bit mask. In essence this would then figure out if any of the 4 or 8 bytes in the mask are zeroes supposedly faster than looping through each of these bytes would. Finally there is a loop at the end to figure out which byte was the first zero, if any, and to return the result.

最大的问题是在sizeof (unsigned long) - 1倍于sizeof (unsigned long)情况下，它将读取超过字符串的末尾-只有当null字节位于最后访问的字节(即在little-endian中是最重要的，而在big-endian中是最不重要的)，它才不会越界访问数组!

这些代码，即使用于在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

也就是说坏事发生了。

2019-08-26 04:46:13

其他回答

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

为了解释这是如何工作的，考虑下面的图像。假设这里是32位平台(4字节对齐)。

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

然后，对于每个对齐大小的块，通过计算(longbits - 0x01010101) & 0x80808080 != 0，它检查整数内是否有字节为零。当至少有一个字节大于0x80时，此计算会出现假阳性，但通常情况下它应该工作。如果不是这样(就像黄色区域一样)，长度会随着对齐大小的增加而增加。

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

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

2019-08-27 09:46:12

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

Unsigned long是4或8字节 字节是8位 一个指针可以转换为unsigned long long而不是uintptr_t 只需检查最低的2或3位是否为零，就可以对指针进行对齐 可以将字符串作为无符号长字符串访问 可以读取数组的末尾而没有任何不良影响。

更重要的是，一个好的编译器甚至可以取代编写为

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函数描述为:

描述 strlen函数的作用是:计算s指向的字符串长度。 返回 函数的作用是:返回终止空字符前的字符数。

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

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

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

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

The linked strlen implementation first checks the bytes individually until the pointer is pointing to the natural 4 or 8 byte alignment boundary of the unsigned long. The C standard says that accessing a pointer that is not properly aligned has undefined behaviour, so this absolutely has to be done for the next dirty trick to be even dirtier. (In practice on some CPU architecture other than x86, a misaligned word or doubleword load will fault. C is not a portable assembly language, but this code is using it that way). It's also what makes it possible to read past the end of an object without risk of faulting on implementations where memory protection works in aligned blocks (e.g. 4kiB virtual memory pages).

Now comes the dirty part: the code breaks the promise and reads 4 or 8 8-bit bytes at a time (a long int), and uses a bit trick with unsigned addition to quickly figure out if there were any zero bytes within those 4 or 8 bytes - it uses a specially crafted number to that would cause the carry bit to change bits that are caught by a bit mask. In essence this would then figure out if any of the 4 or 8 bytes in the mask are zeroes supposedly faster than looping through each of these bytes would. Finally there is a loop at the end to figure out which byte was the first zero, if any, and to return the result.

最大的问题是在sizeof (unsigned long) - 1倍于sizeof (unsigned long)情况下，它将读取超过字符串的末尾-只有当null字节位于最后访问的字节(即在little-endian中是最重要的，而在big-endian中是最不重要的)，它才不会越界访问数组!

这些代码，即使用于在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

也就是说坏事发生了。

2019-08-26 04:46:13

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

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

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

从C标准库中寻找如何编写快速/良好代码的建议并不是一个好主意，因为它将不可移植，并且依赖于不标准的假设或定义不佳的行为。如果您是初学者，阅读这样的代码可能弊大于利。

2019-08-26 09:28:43

其他答案中没有提到的一件重要的事情是，FSF非常谨慎地确保专有代码不会进入GNU项目。在参考私有程序的GNU编码标准中，有一个关于以一种不能与现有私有代码混淆的方式组织你的实现的警告:

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.

(强调我的。)

2019-08-28 00:27:47

除了这里精彩的回答之外，我还想指出问题中链接的代码是用于GNU的strlen实现的。

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

...
#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的代码是asm。类似于PeterCordes的评论/回答指出非后备GNU实现也是asm。

2019-08-26 18:26:57

推荐文章

标签

最新文章

2024 code