お手軽に使える高速なSSE4.2専用文字検索ライブラリ

サイボウズ・ラボの光成です。

今回はC/C++用文字検索ライブラリmie_stringを紹介します。

mie_stringはテキストの中から複数文字のいずれかが存在する場所を高速に検索する関数を提供します。

本文ではその使い方と性能を紹介します。また後半ではSIMD命令を使うときに悩ましい端数処理について詳解します。

準備

mie_stringではCのintrinsic関数（SSE4.2）を使ったものとアセンブリ言語で書いたものの二つを用意しました。

intrinsic関数を使う場合はMIE_STRING_INLINEを定義してからmie_string.hをincludeしてください。 これ以外のファイルは不要です。C/C++のどちらからも使えます。

includeするだけでつかえるので簡単ですね。

なお、コンパイルオプションにはgcc/clangなら-msse42や-mavx、Visual Studioなら/arch:AVXなどの指定を忘れないでください。

asmバージョンを使いたい場合はLinuxなら

nasm -f elf64 mie_string_x64.asm

Visual Studioなら

nasm -f win64 -D_WIN64 mie_string_x64.asm

で作られたオブジェクトファイルmie_string_x64.o(bj)をリンクしてください。NASMはNASMやapt install nasmなどで取得できます。 asm版の方がintrinsic版よりも1～2割ほど高速です。

使い方

提供する関数は二つです。

一つはstd::stringのfind_first_of相当の

const char *mie_findCharAny(const char *text, size_t size, const char *key, size_t keySize);

です。 たとえば[text, text + size)の範囲からスペースかタブあるいは改行を探したいときは

mie_findCharAny(text, size, " \t\r\n", 4);

とします。文字が見つかったときはそのポインタ、見つからなかったときはNULLを返します。 keySizeは16以下という制約があるので注意してください。

もう一つは検索したい文字を範囲で指定できる

const char *mie_findCharRange(const char *text, size_t size, const char *key, size_t keySize);

です。 たとえば16進数の文字0123456789abcdefを探したいときは['0', '9']と['a', 'f']の二つの範囲を指定するため、

mie_findCharRange(text, size, "09af", 4);

とします（注意 : 範囲指定は境界を含みます）。最大8種類の範囲を指定できます。

この場合は文字種が16なので

mie_findCharAny(text, size, "0123456789abcdef", 16);

としてもかまいません。

性能

mie_findCharAny, mie_findCharRangeの比較対象として、次の関数を用意しました。 一つ目は

const char *loop_find_sp(const char *text, size_t size)
{
  for (size_t i = 0; i < size; i++) {
    char c = text[i];
    if (c == ' ' || c == '\r' || c == '\n' || c == '\t') return text + i;
  }
  return NULL;
}

と検索対象をifの中に列挙したものです。 次に対応する文字だけ1になっている256byteのテーブルspTblを事前に用意して

const char *tbl_find_sp(const char *text, size_t size)
{
  for (size_t i = 0; i < size; i++) {
    unsigned char c = text[i];
    if (spTbl[c]) return text + i;
  }
  return NULL;
}

とテーブルで判定する関数も用意しました。

それからC++のstd::string標準メソッドfind_first_ofとも比べました。

今回は見つける文字の頻度を変えて作成した1MiBのデータに対して該当する場所を全て探すベンチマークをとりました。

実験環境はCore i7-6700 3.4GHz（Skylake）+ gcc-4.8です。

横軸は、該当文字が見るかるまでどのぐらいの速度で探せるか、CPUの1cycleあたりの探索byte数です。 値が大きいほど速いことを示します。

縦軸は1MiBのデータの中での該当文字の出現間隔です。値が大きいほど出現頻度は小さいです。 一般的に平均探索長が小さいほど探索byte数/cycleは小さくなります。これは関数呼び出しなどのオーバーヘッドが無視できなくなるためです。

逆に平均探索長が長いとループにおける分岐予測もヒットしやすくなり探索byte数/cycleは小さくなる傾向にあります。

10バイトごとに頻繁に見つかるようなところでもloopやテーブルを用いたものより2倍程度速いです。 出現頻度が少ないところでは5倍以上高速になります。簡単に使えて高速なのですばらしいですね。

またC++のfind_first_ofはとても遅いことがわかります。これは探す文字種が可変なため2重ループになってしまうからです。

同様に16進数探索もベンチマークをとりました。

最初のテストと同様の傾向が見られます。 条件をいくつか変えて評価したところ、mie_findCharAnyやmie_findCharRangeはkeyの長さが増えても速度が変わりませんでした。 テーブルを使った場合に似て、これは興味深い性質です。

なお、標準関数のmemchrはSIMD命令を使って64byte単位で探す実装になっています（glibcのmemchr.S）。 出現頻度が少ないところではSSE4.2を使った実装よりも高速なので、一文字だけを探す場合はmemchrを使ってください。 ただVisual Studio 2015のmemchrはglibcほど最適化はされていないのでmie_findCharAnyの方が速いようです。

実装詳解

SSE4.2命令自体の解説や主な使い方はHTTPパーサにおけるSSE4.2最適化の威力と注意点で紹介しているのでそちらをごらんください。

mie_string.hを見るとmie_findCharAnyとmie_findCharRangeはmodeが0か4の違いしかないことに気がつきます。 それならマクロではなく関数呼び出しでよいのではないかと思われるかもしれません。

しかし_mm_cmpestri()の第4引数は数値リテラルを要求し、変数を指定するとエラーになるためこのような形をとっています。

またmie_string_x64.asmではSSEとAVXの両方のコードを生成するために一段階マクロをかませています。

それではtextのsizeが16未満になったときに安全にSSEレジスタに値を読み込む方法について説明します。

メモリからSSEレジスタに値を読ませるには16byte単位で動作するmovdqu命令を使います。 しかしtextのsizeが16未満のときにmovdquを使うとそのsizeの先のメモリにもアクセスしてしまいます。 その領域がOSによってread禁止になっていると例外が発生します。 したがって滅多にないことではありますが、安全のためにはそこを読まないようにしなければなりません。

通常ページ境界は4096byteごとにあります。したがってアドレスaddrの下位12bitが4080（=4096-16）より大きく、 かつそこから読み込む範囲が境界を越えないときのみケアする必要があります。

addr + sizeが4096を超えていると読み込むべきデータがあるはずなので範囲を超えてreadしても問題ありません。

それを厳密に式で表すと

addr2 = addr & 0xfff;
「addr2 > 0xff0 && addr2 + size <= 0x1000」がtrueのとき

となります。この判定はコード上の73行目あたりにあります。

このとき、4080byte目から16byteをSSEレジスタに読み込んでaddr & 15だけ右シフトすればOKです。

ところが非常に残念なことにSSEにおいて16byteをbyte単位で右シフトする命令はシフト数を定数でしか指定できません。

仕方がないのでIntelの最適化マニュアルには

inline __m128i shr_byte(__m128i v, size_t shift)
{
    switch (shift) {
    case 0: return v;
    case 1: return _mm_srli_si128(v, 1);
    case 2: return _mm_srli_si128(v, 2);
    case 3: return _mm_srli_si128(v, 3);
    case 4: return _mm_srli_si128(v, 4);
    case 5: return _mm_srli_si128(v, 5);
    case 6: return _mm_srli_si128(v, 6);
    case 7: return _mm_srli_si128(v, 7);
    case 8: return _mm_srli_si128(v, 8);
    case 9: return _mm_srli_si128(v, 9);
    case 10: return _mm_srli_si128(v, 10);
    case 11: return _mm_srli_si128(v, 11);
    case 12: return _mm_srli_si128(v, 12);
    case 13: return _mm_srli_si128(v, 13);
    case 14: return _mm_srli_si128(v, 14);
    case 15: return _mm_srli_si128(v, 15);
    default:
    }
}

という方法が紹介されています。しかし分岐予測は殆ど外れるでしょうからこのコードは速くありません。 というか、かっこ悪いです。

どうしたものかと考えて、今回はシャッフル命令pshufbを使ってみました。これはbyte単位で要素をどこに動かすかを指定できます。 s = 0, ..., 15にたいしてs byteずらす方法を記したデータ16byteを16個分テーブルで用意すればよいのです（合計16x16=256byte）。

shift[1] = { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x80 };
shift[2] = { 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x80, 0x80 };
...

が、このテーブルを見ていると一つ後ろのテーブルの値は一つ前を1ずらしたものであることに気がつきます。

したがって読み込む位置をbyte単位でずらせば32byte用意するだけでよいのでした。 それを元に実装したのが75～77行目です。細かいベンチマークをとったところ上記のshr_byteよりも数倍高速でした。

結局、次の関数で安全に値を読み出せます。

__m128i mie_safe_load(const void *text, size_t size)
{
    static const unsigned char shiftPtn[32] = {
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
        0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
        0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80
    };
    size_t addr = (size_t)text;
    size_t addr2 = addr & 0xfff;
    if (addr2 > 0xff0 && addr2 + size <= 0x1000) {
        addr2 = addr & ~(size_t)15;
        size_t shift = addr & 15;
        __m128i ptn = _mm_loadu_si128((const __m128i*)(shiftPtn + shift));
        return _mm_shuffle_epi8(_mm_load_si128((const __m128i*)addr2), ptn);
    } else {
        return _mm_loadu_si128((const __m128i*)text);
    }
}

実はAVX-512にはこのあたりの処理を考慮した命令が追加されています。が、それはまたの機会にしましょう。

まとめ

今回は複数文字のどれかを高速に探す関数を紹介しました。 ナイーブな実装よりも2～5倍速く、std::string::find_first_ofよりも10倍程度高速でした。 またページ境界をまたがずに安全に値を読むmie_safe_loadも紹介しました。 何かのお役にたてば幸いです。