9

这是一个多用途的问题：

  • 这与glibc strlen实现相比如何？
  • 一般来说，有没有更好的方法来解决这个问题和自动矢量化。
#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);
}
4

3 回答 3

7

好吧，此实现基于与您链接的 glibc 实现几乎相同的技巧（确定一个单词是否具有零字节）。他们做的事情几乎相同，除了在 glibc 版本中，一些循环被展开并且位掩码被明确地拼写出来。您发布的代码中的 and 完全是glibcONES版本。HIGHShimagic = 0x80808080Llomagic = 0x01010101L

我看到的唯一区别是 glibs 版本使用稍微不同的标准来检测零字节

if ((longword - lomagic) & himagic)

不做... & ~longword（与HASZERO(x)您的示例中的宏相比，它与 做同样的事情x，但也包括~(x)成员）。显然 glibc 作者认为这个更短的公式更有效。然而，它可能导致误报。因此，他们检查了该之下的误报if。

这确实是一个有趣的问题，什么更有效：单阶段精确测试（您的代码）或从粗略的不精确检查开始的两阶段测试，如果需要，然后进行精确的第二次检查（glibc 代码）。

如果您想查看它们在实际性能方面的比较 - 在​​您的平台和数据上计时。没有别的办法。

于 2012-08-03T00:52:14.923 回答
3

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

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

因此依赖于未定义的行为。

于 2012-08-08T02:05:33.560 回答
0

为了回答您的第二个问题，我认为基于字节的天真strlen实现将导致编译器更好地自动矢量化，如果它很智能并且已启用对矢量指令集扩展（例如 SSE）的支持（例如使用-msse或适当的-march）。不幸的是，即使编译器可以像问题中引用的 C 代码那样生成 32 位或 64 位伪向量化代码，如果它足够聪明的话，它也不会导致任何具有基线 cpus 缺乏这些功能的向量化。 .

于 2012-08-03T01:21:25.437 回答