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 回答