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

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

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


当前回答

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

// 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()候选程序,并将其与“复杂的”替代程序进行比较。

其他回答

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

(强调我的。)

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

 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

也就是说坏事发生了。

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

// 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()候选程序,并将其与“复杂的”替代程序进行比较。

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

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

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

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