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

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

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


在你链接的文件的注释中有解释:

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

and:

 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的效率低于一次测试多个字节的效率,就像这段代码所做的那样。

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

在大多数(但不是全部)现代软件开发中,这种对效率细节的关注是不必要的,或者不值得为额外的代码复杂性付出代价。

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


如果你想了解更多关于单词边界的知识,可以看看这个问题和这个很棒的维基百科页面


我也认为上面的答案是一个更清晰和更详细的讨论。


你不需要也不应该写这样的代码——尤其是如果你不是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

也就是说坏事发生了。


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

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

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

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


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

“正确”是绝对必要的。

“可维护性”取决于你对代码的维护程度:strlen作为标准C库函数已经有40多年的历史了。它不会改变。因此,对于这个函数来说,可维护性并不重要。

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

速度快还有另一个好处:当程序员发现调用“strlen”是他们可以测量字符串中字节数的最快方法时,他们就不会再自己编写代码来提高速度了。

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

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.代码不是很可移植。但它是标准C库的一部分,也是实现的一部分——它不需要是可移植的。

pp。有人发布了一个例子,其中调试工具抱怨访问超过字符串结尾的字节。可以设计一个实现来保证以下内容:如果p是一个指向字节的有效指针,那么对同一对齐块中的字节的任何访问,根据C标准将是未定义的行为,将返回一个未指定的值。

公私合伙制。Intel在他们后来的处理器中添加了指令,形成了strstr()函数的构建块(在字符串中查找子字符串)。他们的描述令人难以置信,但他们可以让特定的功能快100倍。(基本上,给定一个包含“Hello, world!”的数组a和一个以16字节“hellohellohellohelloh”开头并包含更多字节的数组b,它会计算出字符串a不会比从索引15开始更早地出现在b中)。


除了这里精彩的回答之外,我还想指出问题中链接的代码是用于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。


简而言之,这是标准库可以通过了解使用什么编译器进行编译来实现的性能优化—您不应该编写这样的代码,除非您正在编写标准库并且可以依赖于特定的编译器。具体来说,它是同时处理字节的对齐数——在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),则逐字节检查字符串以确定零的位置。

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


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

您看到的是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

因此,修改代码的动机比您想象的要低。

This bithack code (https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord) isn't what actually runs on your server/desktop/laptop/smartphone. It's better than a naive byte-at-a-time loop, but even this bithack is pretty bad compared to efficient asm for modern CPUs (especially x86 where AVX2 SIMD allows checking 32 bytes with a couple instructions, allowing 32 to 64 bytes per clock cycle in the main loop if data is hot in L1d cache on modern CPUs with 2/clock vector load and ALU throughput. i.e. for medium-sized strings where startup overhead doesn't dominate.)

glibc使用动态链接技巧将strlen解析为适合CPU的最佳版本,因此即使在x86内部也有SSE2版本(16字节向量,x86-64的基线)和AVX2版本(32字节向量)。

x86在矢量寄存器和通用寄存器之间有高效的数据传输,这使得它特别适合使用SIMD来加速隐式长度字符串上的函数,其中循环控制是依赖于数据的。Pcmpeqb / pmovmskb可以一次测试16个独立的字节。

glibc有一个类似的使用AdvSIMD的AArch64版本,还有一个用于AArch64 cpu的版本,其中vector->GP寄存器使管道停止,所以它实际上使用了这个bithack。但是使用计数前导零来查找寄存器内的字节,并在检查页面交叉后利用AArch64的高效无对齐访问。

同样相关的:为什么这个代码在启用优化后会慢6.5倍?有一些关于x86 asm中strlen的快与慢的更多细节,以及一个简单的asm实现,这可能对GCC了解如何内联有好处。(一些gcc版本不明智地内联代表scasb非常慢,或者像这样一个4字节一次的bitthack。因此GCC的内联strlen配方需要更新或禁用。)

Asm doesn't have C-style "undefined behaviour"; it's safe to access bytes in memory however you like, and an aligned load that includes any valid bytes can't fault. Memory protection happens with aligned-page granularity; aligned accesses narrower than that can't cross a page boundary. Is it safe to read past the end of a buffer within the same page on x86 and x64? The same reasoning applies to the machine-code that this C hack gets compilers to create for a stand-alone non-inline implementation of this function.

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


为什么这是安全的glibc的一部分,而不是其他。

最重要的因素是这个strlen不能内联到其他任何东西。这样做不安全;它包含严格别名UB(通过无符号长*读取字符数据)。Char *允许别名其他任何东西,但反之则不成立。

这是一个预先编译库(glibc)的库函数。它不会与链接时间优化内联到调用者中。这意味着它只需要编译为strlen的独立版本的安全机器代码。它不必是便携的/安全的;

GNU C库只需要用GCC编译。显然不支持使用clang或ICC编译,尽管它们支持GNU扩展。GCC是一个提前编译器,它将C源文件转换为机器代码的目标文件。不是解释器,所以除非它在编译时内联,否则内存中的字节就是内存中的字节。例如,当不同类型的访问发生在不同的函数中,并且它们之间没有内联时,严格混叠UB是没有危险的。

记住,strlen的行为是由ISO C标准定义的。函数名是具体实现的一部分。像GCC这样的编译器甚至把这个名字当作内置函数,除非你使用-fno-builtin-strlen,所以strlen("foo")可以是一个编译时常数3。只有当gcc决定真正发出对它的调用,而不是内联自己的菜谱或其他东西时,才会使用库中的定义。

当UB在编译时对编译器不可见时,你得到正常的机器代码。机器代码必须适用于no- ub情况,即使您希望这样做,asm也无法检测调用者用于将数据放入指向内存中的类型。

Glibc被编译为独立的静态或动态库,不能内联链接时间优化。当内联到程序中时,glibc的构建脚本不会创建包含机器代码+ gcc GIMPLE内部表示的“胖”静态库,用于链接时间优化。(即libc。A不会参与-flto链接时间优化到主程序中。)以这种方式构建glibc对于实际使用该.c的目标来说可能是不安全的。

事实上,正如@zwol所言,LTO不能在构建glibc本身时使用,因为这样的“脆弱”代码可能会在glibc源文件之间内联时被破坏。(有一些strlen的内部使用,例如可能作为printf实现的一部分)


这个strlen做了一些假设:

CHAR_BIT is a multiple of 8. True on all GNU systems. POSIX 2001 even guarantees CHAR_BIT == 8. (This looks safe for systems with CHAR_BIT= 16 or 32, like some DSPs; the unaligned-prologue loop will always run 0 iterations if sizeof(long) = sizeof(char) = 1 because every pointer is always aligned and p & sizeof(long)-1 is always zero.) But if you had a non-ASCII character set where chars are 9 or 12 bits wide, 0x8080... is the wrong pattern. (maybe) unsigned long is 4 or 8 bytes. Or maybe it would actually work for any size of unsigned long up to 8, and it uses an assert() to check for that.

这两个都不是可行的UB,它们只是无法移植到一些C实现。这段代码是(或曾经是)在它可以工作的平台上的C实现的一部分,所以这很好。

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

An aligned load that contains any valid bytes can't fault, and is safe as long as you ignore the bytes outside the object you actually want. (True in asm on every GNU systems, and on all normal CPUs because memory protection happens with aligned-page granularity. Is it safe to read past the end of a buffer within the same page on x86 and x64? safe in C when the UB isn't visible at compile time. Without inlining, this is the case here. The compiler can't prove that reading past the first 0 is UB; it could be a C char[] array containing {1,2,0,3} for example)

最后一点使得在这里读取C对象的结束部分是安全的。即使在与当前编译器内联时,这也是相当安全的,因为我认为它们目前并不认为这意味着执行路径不可达。但无论如何,如果你让它内联,严格的混叠已经是一个阻碍。

然后你就会遇到像Linux内核旧的不安全的memcpy CPP宏那样的问题,它使用指针强制转换为无符号长(gcc、严格别名和可怕的故事)。(现代Linux使用-fno-strict-aliasing编译,而不是小心使用may_alias属性。)

这个strlen可以追溯到那个时代,那时你可以随便做这样的事情;在GCC3之前,它是非常安全的,甚至没有“仅当不内联”的警告。


只有在调用/ret边界时才可见的UB不会伤害我们。(例如,在char类型的buf[]上调用此函数,而不是在unsigned long类型的[]转换为const char*的数组上调用此函数)。一旦机器代码固定下来,它就只是处理内存中的字节。非内联函数调用必须假设被调用方读取所有内存。


安全地写这个,没有严格的混叠UB

GCC类型属性may_alias为类型提供了与char*相同的别名处理。(由@KonradBorowsk建议)。GCC头文件目前将它用于x86 SIMD向量类型,如__m128i,因此您可以始终安全地执行_mm_loadu_si128((__m128i*)foo)。(参见硬件SIMD向量指针和相应类型之间的' reinterpret_cast '是否是未定义的行为?了解更多关于这意味着什么和不意味着什么的细节。)

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)来表示align (T) = 1的类型。 Typedef unsigned long __attribute__((may_alias, aligned(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的工作方式就像每次访问一个字符一样。但是在实践中,现代编译器非常了解memcpy。

The danger here is that if GCC doesn't know for sure that char_ptr is word-aligned, it won't inline it on some platforms that might not support unaligned loads in asm. e.g. MIPS before MIPS64r6, or older ARM. If you got an actual function call to memcpy just to load a word (and leave it in other memory), that would be a disaster. GCC can sometimes see when code aligns a pointer. Or after the char-at-a-time loop that reaches a ulong boundary you could use p = __builtin_assume_aligned(p, sizeof(unsigned long));

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


为什么手工优化C源代码是必要的:当前的编译器还不够好

如果您希望广泛使用的标准库函数的每一点性能都得到优化,那么手工优化asm会更好。尤其是像memcpy这样的东西,但也有strlen。在这种情况下,使用C和x86 intrinsic来利用SSE2并不容易。

但这里我们只讨论一个朴素的C版本,而没有任何特定于isa的特性。

(我认为我们可以认为strlen已经被广泛使用,所以让它尽可能快地运行是很重要的。所以问题就变成了我们能否从更简单的资源中获得高效的机器代码。不,我们不能。)

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

这包括搜索循环,或具有依赖于数据的if()和计数器的任何其他循环。

ICC (Intel的x86编译器)可以自动向量化一些搜索循环,但是对于像OpenBSD的libc这样的简单/天真的C strlen,仍然只能生成一次字节的asm。(Godbolt)。(来自@Peske的回答)。

A hand-optimized libc strlen is necessary for performance with current compilers. Going 1 byte at a time (with unrolling maybe 2 bytes per cycle on wide superscalar CPUs) is pathetic when main memory can keep up with about 8 bytes per cycle, and L1d cache can deliver 16 to 64 per cycle. (2x 32-byte loads per cycle on modern mainstream x86 CPUs since Haswell and Ryzen. Not counting AVX512 which can reduce clock speeds just for using 512-bit vectors; which is why glibc probably isn't in a hurry to add an AVX512 version. Although with 256-bit vectors, AVX512VL + BW masked compare into a mask and ktest or kortest could make strlen more hyperthreading friendly by reducing its uops / iteration.)

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

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


其他答案中没有提到的一件重要的事情是,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.

(强调我的。)


为什么像下面这样的作品不一样好或更好呢?

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

OP的代码有功能错误。

不过修改起来很容易。


在编写可移植代码时,需要注意首先确保函数正确,然后再考虑性能改进。

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

Type

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

常量

S应该是const char *。

Non-2的补

(这个问题目前影响的处理器数量少得可怜,所以实际上只是一个学究气的问题。Non-2的补体很可能在下一个C中被指定(C23?))。

s[i] != '\0'可以在-0处触发,当char是有符号的,而不是2的补码。不应该如此。Str…()函数,就好像字符是作为unsigned char访问一样。

对于本小节中的所有函数,每个字符都应被解释为unsigned char类型(因此每种可能的对象表示都是有效的,具有不同的值)。


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

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

现在,我们有了一个更好的、可移植的strlen()候选程序,并将其与“复杂的”替代程序进行比较。