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 バージョンでは一部のループがアンロールされ、ビット マスクが明示的に記述されていることを除いて、ほとんど同じことを行います。投稿したコードのONESandは、正確にglibc バージョンを形成しています。HIGHShimagic = 0x80808080Llomagic = 0x01010101L

私が見る唯一の違いは、glibs バージョンがゼロバイトを検出するためにわずかに異なる基準を使用することです

if ((longword - lomagic) & himagic)

実行せずに（あなたの例のマクロと... & ~longword比較してください。これは で同じことを行いますが、メンバーも含みます）。どうやら glibc の作成者は、この短い式の方が効率的であると考えていたようです。それでも、誤検知が発生する可能性があります。そのため、その下で誤検知をチェックします。HASZERO(x)x~(x)if

より効率的なのは興味深い質問です。1 段階の正確なテスト (コード) または大まかな不正確なチェックで始まり、必要に応じて正確な 2 番目のチェック (glibc コード) が続く 2 段階のテストです。

実際のパフォーマンスの観点からそれらを比較したい場合は、プラットフォームとデータで時間を計ってください。他に方法はありません。

于 2012-08-03T00:52:14.923 に答える
3

また、この実装はここでchar配列の終わりを超えて読み取ることができることに注意してください。

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

したがって、未定義の動作に依存します。

于 2012-08-08T02:05:33.560 に答える