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

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

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


当前回答

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

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

其他回答

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

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

其他答案中没有提到的一件重要的事情是,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的效率低于一次测试多个字节的效率,就像这段代码所做的那样。

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

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

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


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


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

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

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

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