strlen性能实现

Question

这是一个多功能问题:

• 这与glibc strlen实现相比如何？
• 有没有更好的方法来实现这一点和自动向量化.

随机填充垃圾,因为stackoverflow以某种方式比我更了解代码到汇总比率

#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)成员).显然,glibc的作者认为这种较短的公式更有效.但它可能导致误报.因此他们检查了误报if.

这确实是一个有趣的问题,更有效的:单阶段精确测试(您的代码)或两阶段测试,以粗略的不精确检查开始,如果有必要,通过精确的第二次检查(glibc代码).

如果您想了解它们在实际性能方面的比较 - 在​​您的平台和数据上计算时间.别无他法.