こんにちは、サイボウズ・ラボの光成です。
PicoHTTPParserは@kazuhoさんたちが開発している高速なHTTPパーサです。 同じ作者によるHTTPサーバH2Oにも使われています。
11月4日の開発ブログによると、その時点でNode.jsなどに使われているhttp-parserの10倍程度の速度を誇るそうです（現在はhttp-parserも速度向上しその差は縮まりました。それでも4倍以上の差があるようです）。
該当ブログにはその高速化のためのノウハウが書かれていて大変興味深いです。ただIntel系CPUに搭載されているSIMD命令は用いられていませんでした。今回、@kazuhoさんと一緒に文字列処理専用のSSE4.2を用いることで1.7～1.9倍の高速化を達成しました（Improving Parser Performance using SSE Instructions (in case of PicoHTTPParser)）。このエントリではその文字列処理命令の詳細について紹介したいと思います。
SSE4.2の文字列処理専用命令
SIMD命令とは1, 2, 4, 8byteの整数や浮動小数点数を4～32個並列に演算させることで高速化させる命令群のことです。 最近のコンパイラはある程度の単純なループなら自動ベクトル化してSIMD命令を使うため、利用者が特に意識しなくてもその恩恵を受ける場面が増えています。
しかしSSE4.2の文字列処理命令（以下pcmpXstrYと表記）はそれらのSIMD命令とは異なり、並列計算するためのものではありません。strlen, strstr, memmemなどの文字や文字列を検索する関数を高速化することに特化した命令群です。この命令群は非常に複雑です。Intelのマニュアルでも5ページに渡って解説されていますが、この情報だけではいろいろ不足しています。ここでは数ある機能の中から、ある範囲の文字を探すモードにしぼって紹介しましょう。
文字の範囲検索
PicoHTTPParserではHTTPのパースの際に、文字種の範囲をチェックしながら探索する場面が多いです。 プロファイラを見てもそのあたりが処理時間のかなりを占めています。
for (; ; ++buf) {
CHECK_EOF();
if (buf == ':') {
break;
} else if (buf < ' ') {
*ret = -1;
return NULL;
}
}
CHECK_EOF();はデータの終端になったかの範囲チェックをするマクロです。
define CHECK_EOF() if (buf == buf_end) { *ret = -2; return NULL; }
文字列には、'\0'ターミネートしているCの文字列と、ポインタとデータサイズの組(p, size)で表す文字列があります。 Cの文字列を扱うstrlen, strstrなどは、最近のコンパイラでは既にSSE4.2を使ったものになっているので敢えてコードを書く必要はありません。 しかし、ANSI標準関数には後者の(p, size)の形の文字列を扱う関数は殆どありません。 そのため自分でコードを書いた方が性能向上が望めます。
たとえば上記部分は(p, size)の中で「コロン':'あるいは0以上でスペース' '未満の文字」を探しています。このようなある範囲の文字を探す場面は他でも頻出します。こういう場合、以前は文字ごとの属性をもつ256byteのテーブルを持ち、その属性に応じて分岐することが多かったかもしれません。
ただ最近のCPUの分岐予測の性能向上はめざましいです。扱うデータがHTTPのようにある程度パターンがある場合、多少のifを組み合わせも分岐をさせた方が高速になることが多いです。PicoHTTPParserもその方針をとっています。それでも先程のプロファイル結果のようにそのあたりがボトルネックになっています。
さて、一般的には入力データtext=(p, size)と範囲指定の組み合わせパターン(range, rangeSize)を渡して、そのパターンにマッチする場所を返す関数
const char *findChar_rangeC(
const char *p, size_t size,
const char *range, size_t rangeSize) {
assert((rangeSize % 2) == 0);
for (size_t i = 0; i <; size; i++) {
const char c = p[i];
for (size_t j = 0; j < rangeSize / 2; j++) {
if (range[j * 2] <= c && c <= range[j * 2 + 1]) return p + i;
}
}
return NULL;
}
が高速化されるとうれしいです。ここでrangeはどれかのj ∈ [0, rangeSize/2)について
range[2 * j] <= c && c <= range[2 * j + 1]
となる文字cがマッチするという仕様です。
アセンブリ言語によるfindChar_range
そしてこの関数findChar_rangeCを高速にするための命令がまさにpcmpestriです。
input : range=(xmm0, rax)
p=(xmm1, rdx)
output : rcx(ポジション)
pcmpestri xmm0, xmm1/mem, imm8
ここでxmm0, xmm1は16byteのSSEレジスタ、memはメモリを表します。ai, biを1byteとして xmm0=[a15:a14:...:a0], xmm1=[b15:b14:...:b0] と表します。 raxはxmm0の長さ(1～16byte)、rdxはxmm1の長さ(1～16byte)を与えます。 imm8は8bit定数で、byte/word単位、符号つき/符号なし、検索モードなど様々なモードを指定します。詳細はたとえばSSE4.2の文字列処理命令の紹介をごらんください。ここでは符号なしbyte単位の文字列で範囲指定検索をするのでimm8 = 4となります。
範囲指定の場合b0, b1, ..の中から
(a0 <= c && c <= a1) || (a2 <= c && c <= a3) || (a4 <= c && c <= a5)...
がtrueになる場所をecxで返します。見つからなければ16を返します。同時にCFlag, ZFlag, SFlagなども変化します。
前述のfindChar_rangeCに相当するアセンブリ言語による（Linux用）コードはLIST1となります。
; rdi = p ; rsi = size ; rdx = range ; rcx = rangeSize findChar_rangeA: 1 movdqu (%rdx), %xmm0 ; xmm0 = range 2 mov %rcx, %rax ; rax = rangeSize 3 mov %rsi, %rdx ; rdx = size 4 jmp .in 5 .lp 6 add $16, %rdi ; p += 16 7 sub $16, %rdx ; size -= 16 8 .in: 9 pcmpestri $4,(%rdi), %xmm0 10 ja .lp 11 jae .exit 12 lea (%rdi, %rcx, 1), %rax ; rax = rdi + rcx 13 ret 14 .exit: 15 xor %eax, %eax 16 ret
fincChar_rangeCのような複雑なコードをわずか16行で書けるのは驚きです。メインループは5～10行です。CFlag = ZFlag = falseとなる間ループします。このコードは最適化されたstrlenと同等の速度で動作します。
このコードには二つ注意点があります。一つ目はLIST1の6, 7行目を
add %rcx, %rdi add %rcx, %edx
としてはいけません。先ほど述べたようにpcmpestriはその結果をrcxに返すのでループが回っている限り16です。ですからこのコードでも正しく動作はします。しかし遅くなるのです。 6行目のaddが定数の場合、9行目のpcmpestriに使われるrdiのメモリの先読みがうまくいくのですが変数になると値の確定までに遅延が生じるためのようです。
もう一つの注意点は後述します。
intrinsc関数によるfindChar_range
今アセンブリ言語で書く方法を紹介しましたが、もう一つintrinsic関数を使った方法も紹介します。正直なところ、pcmpXstrY命令はフラグの扱いがややこしいためアセンブリ言語で書く方が楽で速くなることが多いです。
しかし、AVXとSSEの命令を混在させるとペナルティを食らうことがあります。コンパイラのオプションによってAVX, SSEのどちらを使っているか判別しながら正しいニーモニックを使わせるようにするのはなかなか難しくトラブルを招きかねないです。intrinsicの場合はコンパイラが適切に判断してくれるのでそちらのほうがよいでしょう。
intrinsic関数で書くと次のようになります（LIST2）。
# ifdef _MSC_VER
# include <intrin.h>
# else
# include <x86intrin.h>
# endif
1 const char *fincChar_rangeI(
2 const char *p, size_t size,
3 const char *range, size_t rangeSize) {
4 const __m128i r = _mm_loadu_si128((const __m128i*)range);
5 __m128i v;
6 for (;;) {
7 v = _mm_loadu_si128((const __m128i*)p);
8 if (!_mm_cmpestra(r, rangeSize, v, size, 4)) break;
9 p += 16;
10 size -= 16;
11 }
12 if (_mm_cmpestrc(r, rangeSize, v, size, 4)) {
13 return p += _mm_cmpestri(r, rangeSize, v, size, 4);
14 }
15 return NULL;
16}
__m128iが16byteのSSEレジスタを表す組み込みの型です。_mm_loadu_si128(mem)によりmemから16byteデータを読み込んで__m128iに設定します。昔のPentium 4では16byteアライメントされていないデータの読み込みはとても遅かったのですが、Sandy Bridge以降そのコストはほぼ無視できるレベルになりました。
7行目でpcmpestri相当のことをしています。pcmpestri自体は16byteアライメントされていないデータにも対応しているのですが、 _mm_cmpestra(r, rangeSize, *(const __m128i*)p, size, 4); と書いてしまうと、コンパイラはpがアライメントされていると仮定したコードを生成してしまうため6行目で 明示的にloadしています。intrinsicが面倒な部分の一つです。
_mm_cmpestraの最後のaはLIST1の10行目のjaのaに対応しています。intrinsicはフラグをばらばらに返すことができないため扱うフラグによって名前を変えています。これもintrinsicが面倒な部分です。
breakしたあと、11行目でCFlagをチェックするために同じ引数で_mm_cmpestrc()を呼んでいます。 LIST1の11行目に対応しています。12行目はrcxを加算する部分です。同様に_mm_cmpestri()を同じ引数で呼んでいます。
本来ならこれらの_mmcmpestr{a,c,i}は全て同じ引数なのでフラグを変更しなければ一度呼べば十分です。しかし今のところコンパイラはそこまでの最適化はしないようです。VC/gccは2個にはまとめますが、clang-3.5は3個のpcmpestri命令を生成しました。まあループの外なので速度にcriticalな影響を与えるわけではありません。
ここで記述したfindChar_range相当のものを作り、PicoHTTPParserに数カ所埋め込むことで1.7～1.9倍の速度向上となりました。差分を見ると小さいパッチで大きな性能向上をえられていることに驚かれるかもしれません。
境界読み出しに関する注意
最後に先ほど後述すると書いた点について説明します。pcmpXstrY命令は(p, size)を与えたときsize < 16でも正しく動くのですが、内部的にはpから16byteのデータを読んでしまうのです。通常これが問題になることはありません。
しかしもし[p, p+16]がOSが管理しているシステムのページ境界をまたいでいて、かつ後ろのページに読み込み属性が付与されていない場合アクセス違反で落ちてしまいます。
図は(p % 16) == 0で p + 4から16byte読もうとしたときにページ境界をまたいだ例です。
これを回避するには大きく三つの方法があります。
一つはreadが最大15byteオーバーランすることが分かっているのでそのプログラムで扱う文字列データ領域をmallocするとき全て+16してしまうことです。一番お手軽です。ただPicoHTTPParserはそのコードがperlなど別のものから呼び出されるためそういう仮定は置けませんでした。
したがってsizeが16byte未満になったときは通常の探索コードにフォールバックするようにしました。これが二つ目の方法です。
三つ目はfincChar_range()の中でページ境界をまたぎそうなときだけ慎重にデータをreadする関数を呼ぶようにすることです。これは一番汎用的ですがなかなかやっかいです。コンパイラが提供するライブラリ関数はそのような実装になっています。面白いところでもありますが、長くなったのでまたの機会といたします。
まとめ
SSE4.2の文字列処理命令はIntelのSIMD命令のなかでも異色で使い方も難しいです。しかし、分かって使うと少しの労力で大きな効果を得ることがあります。このドキュメントが何かのお役に立てると幸いです。
