12

我正在阅读“编写出色的代码第 2 卷”，它显示了以下 strlen 实施：

int myStrlen( char *s )
{
    char *start;
    start = s;
    while( *s != 0 )
    {
        ++s;
    }
    return s - start;
}

这本书说这种实现对于没有经验的 C 程序员来说是典型的。在过去的 11 年里，我一直在用 C 编写代码，但我看不出如何在 C 中编写比这更好的函数（我可以想到在汇编中编写更好的东西）。怎么可能用 C 写出比这更好的代码呢？我查看了 glibc 中 strlen 函数的标准库实现，但我无法理解其中的大部分内容。我在哪里可以找到有关如何编写高度优化的代码的更好信息？

4

7 回答 7

14

来自Optimizing strlen()，Colm MacCarthaigh 的一篇博文：

不幸的是，在 C 语言中，我们注定要实现 O(n)，这是最好的情况，但我们还没有完成……我们可以对 n 的大小做一些事情。

它提供了一个很好的例子，说明您可以在哪些方向上加快速度。和它的另一个报价

有时真的非常快只会让你真的非常疯狂。

于 2011-07-05T14:41:04.173 回答
3

维克多，看看这个：
http ://en.wikipedia.org/wiki/Strlen#Implementation

PS你不理解glibc版本的原因可能是因为它使用位移来找到\ 0。

于 2011-07-05T14:36:05.273 回答
3

对于初学者来说，这对于像 UTF-8 这样的编码毫无价值......也就是说，计算 UTF-8 字符串中的字符数更复杂，而字节数当然就像计算一样容易，比如说，一个 ASCII 字符串。

通常，您可以通过读入更大的寄存器在某些平台上进行优化。由于到目前为止发布的其他链接没有这样的例子，这里有一些低端的伪伪代码：

int size = 0;
int x;
int *caststring = (int *) yourstring;
while (int x = *caststring++) {
  if (!(x & 0xff)) /* first byte in this int-sized package is 0 */ return size;
  else if (!(x & 0xff00)) /* second byte etc. */ return size+1;
  /* rinse and repeat depending on target architecture, i.e. twice more for 32 bit */
  size += sizeof (int);
}
于 2011-07-05T14:42:32.623 回答
3

正如其他人指出的那样，更快的算法读取整个单词而不是单个字符，并使用按位运算来查找终止空值。如果您采用这种方法，请注意字对齐指针，因为某些 CPU 架构不允许您从未对齐的地址读取字（即使在不需要对齐的架构上，这也是触发段错误的好方法）。

底线：

除了对性能最关键的情况外，优秀的代码强调可读性而不是速度。尽可能清楚地编写代码，并且只优化被证明是瓶颈的部分。

于 2011-07-05T15:08:34.707 回答
1

读取与机器数据总线大小不同的变量是昂贵的，因为机器只能读取该大小的变量。因此，无论何时请求不同大小（比方说更小）的东西，机器必须做一些工作以使其看起来像请求大小的变量（如移位位）。因此，您最好以机器大小的字读取数据，然后使用 AND 操作检查 0。此外，在扫描字符串时，请确保从对齐的起始地址开始。

于 2011-07-05T14:45:16.883 回答
1

回答 OP 关于在哪里可以找到如何编写代码以提高性能的建议的问题，这里是关于编写优化 C 代码的 MIT OpenCourse 的链接（在页面左侧查​​找“材料”链接）。

于 2011-07-06T12:58:15.430 回答
1

以下应该比朴素算法更快并且适用于 32/64 位。

union intptr {
    char* c;
    long* l;
#define LSIZE sizeof(long)
};

#define aligned_(x, a) \
    ((unsigned long) (x) % (a) == 0)

#define punpktt_(x, from, to) \
    ((to) (-1)/(from) (-1)*(from) (x))
#define punpkbl_(x) \
    punpktt_(x, unsigned char, unsigned long)

#define plessbl_(x, y) \
    (((x) - punpkbl_(y)) & ~(x) & punpkbl_(0x80))
#define pzerobl_(x) \
    plessbl_(x, 1)

static inline unsigned long maskffs_(unsigned long x)
{
    unsigned long acc = 0x00010203UL;
    if (LSIZE == 8)
       acc = ((acc << 16) << 16) | 0x04050607UL;
    return ((x & -x) >> 7) * acc >> (LSIZE*8-8);
}

size_t strlen(const char* base)
{
    union intptr p = { (char*) base };
    unsigned long mask;

    for ( ; !aligned_(p.c, LSIZE); p.c++ )
        if (*p.c == 0)
            return p.c - base;

    while ( !(mask = pzerobl_(*p.l)) )
        p.l++;
    return p.c - base + maskffs_(mask);
}
于 2014-10-26T20:20:38.700 回答