mitsunari@cybozu labs

strlen()とmemchr()のSIMD版を作ってみました．

今回は最速よりもお手軽さを重視したのでアセンブリ言語ではなくintrinsic関数を使っています．そのためVisual Studio 2008, gcc 4.xの両方でコンパイルでき32-bit, 64-bit OS上で動作します．
WindowsとLinuxでのみ確認していますが恐らくIntel Mac OS X上でも動作するでしょう(sample source)．

ベンチマークはランダムな長さの文字列の平均長(average length)を変化させつつ取りました．数値は1byteあたりにかかった処理時間比で小さいほど速いことを表します．
strlenが3種類(ANSI, BLOG, SSE2)とmemchrが2種類(ANSI, SSE2)あります．BLOGというのは今回試してみようというきっかけになったCounting Characters in UTF-8 Strings Is Fastの中のCバージョンです．

結果は極端に短いところではSIMDが使えず，かつそのチェックのためのオーバーヘッドがありそれほど速くなりませんが，32文字以上ではは2～5倍高速であることが分かります．
なお，gccのstrlen()は今となっては遅い命令を使っているためよくありません(なぜこうなっているのかちょっと理解に苦しみます)．

一つ細かい注意点としては，高速化のために与えられた範囲外の空間を少しアクセスします(readはするがその値は捨てます)．16byteアライメントされたところを超えることはないのでページングエラーにはなりませんが，purifyなどのツールを使うと警告がでるかもしれません．

intrinsic関数はVCとgccとで共通化され，しかも32bit, 64bit両対応なため汎用性も高いです．strlenSSE2のように30行未満の関数でも十分は効果はでます．利用しない手はないと思われます．

size_t strlenSSE2(const char *p)
{
    const char *const top = p;
    __m128i c16 = _mm_set1_epi8(0);
    /* 16 byte alignment */
    size_t ip = reinterpret_cast<size_t>(p);
    size_t n = ip & 15;
    if (n > 0) {
        ip &= ~15;
        __m128i x = *(const __m128i*)ip;
        __m128i a = _mm_cmpeq_epi8(x, c16);
        unsigned int mask = _mm_movemask_epi8(a);
        mask &= -(1 << n);
        if (mask) {
            return bsf(mask) - n;
        }
        p += 16 - n;
    }
    for (;;) {
        __m128i x = *(const __m128i*)&p[0];
        __m128i y = *(const __m128i*)&p[16];
        __m128i a = _mm_cmpeq_epi8(x, c16);
        __m128i b = _mm_cmpeq_epi8(y, c16);
        unsigned int mask = (_mm_movemask_epi8(b) << 16) | _mm_movemask_epi8(a);
        if (mask) {
            return p + bsf(mask) - top;
        }
        p += 32;
    }
}