strlen性能实现

Question

这是一个多用途的问题：

• 这与格列布克实现相比如何？
• 是否有更好的方法来做到这一点，在一般和自动矢量化。

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>

/* Todo: Document */
#define WORD_ONES_LOW   ((size_t)-1 / UCHAR_MAX)
#define WORD_ONES_HIGH  (((size_t)-1 / UCHAR_MAX) << (CHAR_BIT - 1))

/*@doc
 * @desc: see if an arch word has a zero
 * #param: w - string aligned to word size
 */
static inline bool word_has_zero(const size_t *w)
{
    return ((*w - WORD_ONES_LOW) & ~*w & WORD_ONES_HIGH);
}

/*@doc
 * @desc: see POSIX strlen()
 * @param: s - string
 */
size_t strlen(const char *s)
{
    const char *z = s;

    /* Align to word size */
    for (; ((uintptr_t)s & (sizeof(size_t) - 1)) && *s != '\0'; s++);

    if (*s != '\0') {
        const size_t *w;

        for (w = (const size_t *)s; !word_has_zero(w); w++);
        for (s = (const char *)w; *s != '\0'; s++);
    }

    return (s - z);
}

Answer 1

这个实现实际上基于与您链接的glibc实现相同的技巧(确定一个单词是否有零字节)。它们所做的几乎是相同的事情，只不过在glibc版本中，有些循环是展开的，位掩码是显式的。您发布的代码中的ONES和HIGHS完全是himagic = 0x80808080L和lomagic = 0x01010101L表单glibc版本。

我所看到的唯一不同之处在于，glibs版本使用了一个稍微不同的标准来检测零字节。

if ((longword - lomagic) & himagic)

不执行... & ~longword (与示例中的HASZERO(x)宏相比，该宏对x执行相同的操作，但也包含~(x)成员)。显然，滑翔作者认为这种较短的公式更有效。然而，它可能导致假阳性。所以他们在if下检查假阳性。

这确实是一个有趣的问题，什么是更有效的:一个单级精确测试(您的代码)或一个以粗糙不精确检查开始的两阶段测试，如果有必要的话，再进行一个精确的第二次检查(glibc代码)。

如果您想了解它们在实际性能方面的比较，请在您的平台上和您的数据上进行比较。没有别的办法了。

Answer 2

此外，请注意，此实现可以在这里读取char数组的末尾：

for (w = (const void *)s; !HASZERO(*w); w++);

因此依赖于不明确的行为。

Answer 3

为了回答第二个问题，我认为天真的基于字节的strlen实现将导致编译器更好的自动矢量化，如果它是智能的，并且支持向量指令集扩展(例如SSE)已经启用(例如使用-msse或适当的-march)。不幸的是，它不会导致基线cpus没有这些特性的矢量化，即使编译器可以生成32位或64位伪矢量化代码，比如问题中引用的C代码，如果它足够聪明.