SIMD による文字列のパフォーマンスの改善(か？)

この記事は Qt Blog の "Improving the string performance with more SIMD (or not)" を翻訳したものです。
執筆: Thiago Macieira 2010年8月25日

Benjamin や Samuel などによる SIMD 対応に触発され、また、誰よりもこの件に精通している Intel のエンジニア達から直接様々なことを学ぶ機会を得たため、勤務時間外に私も SIMD 関連のコードを書くことにしました。画面の合成や重ね合わせ、描画などについてはそもそも十分に理解をしていないので、自分の理解が及ぶ分野である QtCore に対して挑戦することにしました。

2010 年の始めに Benjamin は Latin 1(ISO-8859-1)から QString への変換とその逆変換のパフォーマンスを SSE2 と Neon を利用して改善するコードを書きました。このコミット(60fd302e)は Qt 4.7 ブランチに対して行われ、fromLatin1 では４倍の改善が見られました。逆変換では改善の幅はこれに比べてわずかに小さくなりました。これは UTF-16 での文字コードが Latin 1 の範囲に収まるかどうかのチェックが必要なためです。それから、私は 2009 年に QString::operator== 関数を Lars のコードを受けて改善しています。

というわけで、この場所に対して改善を行うことにしました。

この記事を最後まで読んだ後に、みなさんに殴られないようにあらかじめお断りしておきますが、結果的に改善は得られず今回私の書いたコードが qstring.cpp に含まれることはないでしょう。でも、私は多くのことを学ぶことができました。今回のコードは 9a468f59472e8978aa18b75e9786718a8823bbec までの一連のコミットですので、興味のある方はご覧ください。

まず始めに qMemEquals 関数を３種類のやり方で試してみました。バイト単位での比較(memcmpとして知られています)と、ushort での比較、それからデータのアライメントを揃えて 32 ビットで比較するコードです。Qt 4.6 と 4.7 の qMemEquals はこの最後の方法で実装されています。

次に、私はテスト用に生成されるランダムなデータではなく、実際のユースケースに沿ったデータが必要なことに気がつきました。このため、qMemEquals の中身を少し変更し、Qt Demo Browser を利用し各文字列のアライメントプロパティに沿って比較する文字列を抜き出しました。さらにベンチマーク用のデータを生成するための Perl スクリプト を書きました。

さらに数日間 Intel のイントリンシック命令を学び、最適化しうる方法をいくつか試しました。これらのコードはベンチマークツールへのコミットに含まれていますのでこちらもご覧ください。

そして最後に、自分が適切な関数を最適化しているのかを確認するため qMemEquals がどのくらいの頻度で実行されているのかを調べました。これにより、qstring.cpp で最も実行されて(CPU を使用して)いる関数が qMemEquals ではなく ucstrncmp だということが判明しました。この同一性の確認(qMemEquals)は順序比較(ucstrncmp)の特殊なケースだと考えることも出来ます。この結果を受け、ucstrncmp を呼び出す箇所を全て洗い出し、最適化を再度行いました。

結果的にこれらは全く改善されなかったため、結果のグラフなどをお見せすることはできません。しかし、今回の調査を通じて学んだことを書きます。

アライメントについて

SSE2 命令は 16 バイトのブロックに対して作用し、データが 16 バイトにそろっている場合にメモリのロード(とストア)は非常に高速に行われます。しかし、QString::Data に含まれる array 要素のオフセットは 18 バイトであり、比較される全てのデータの 90〜99% は 2 バイトもしくは 10 バイトアライメントがずれてしまいます(これは 32 ビットのプラットフォームの場合で、x86-64 では 2 バイトのみでしょう)。この修正は Qt 4 ではできませんが、Qt 5 で対応することを考えています。このため、データのアライメントを考慮するようにとのコメントを qstring.h の中に残しておきました。これはシステムの malloc 関数が 16 バイトでアライメントされたメモリを返す場合でのみ大きな効果が得られます。32 ビットの Linux では効果がないでしょう。

この傾向は Atom プロセッサでは特に顕著で、ucstrncmp の最良の結果は "アライメントを揃えた" バージョン(ssse3_aligning2, sse2_aligning, ssse3_aligning)になります。

複雑な問題(別名、文字列が短すぎる)

問題解決のため、アライメントを揃えるコードを前処理を追加したのですが、その処理を追加した影響によりアライメントを揃えたロードによる改善が(ほぼ)完全に打ち消されていることが分かりました。そして、この前処理とアライメントを揃えた比較のコードの組み合わせは、ほとんどの場合でアライメントを揃えずに比較した場合より遅い結果になりました。文字列のサイズの統計を見てみると、ほとんどの場合、比較するデータが驚くほど小さい(qMemEquals では 15 QChar 程度、ucstrncmp では 38 QChar 程度)ことが分かりました。これは 16 バイトの比較ループが１回〜３回しか回っていないことになります。簡単に数十キロバイトのオーダーになる画像のデータとは違い、前処理と後処理のコストも重要になってくるため、これらの処理が複雑になると結果として目に見えて影響してきます。

これには CPU に依存して実行時に割り当てられるコードも含まれます。実行時の検知はアーキテクチャの機能レベル(SSE2用、SSE3用、SSSE3用、SSE4.2用)ごとに .cpp ファイルを分ける必要があります。これはコンパイラが、低レベルでも動作すると思われる高レベルの命令を使う可能性があるからです(gcc 4.4 の #pragma と __attribute__ での解決を提案しないでください。理由は こちら です)。

前処理と後処理の最適化とデータのアライメントへの異なるアプローチを考えることに多くの時間を費やし、実際のデータ比較のコードにはあまり時間を費やさなかったと思います。アライメントを揃えるまでには色々な試行錯誤がありました。文字列の始めの部分はアライメントを揃えず比較し、そして最初のアライメント位置(6 番目もしくは 14 番目の QChar)から続ける方法を試したり。実際の文字列のデータの開始位置より前のメモリをロードしてアライメントを揃えようとしたり(もしこのコードを採用していたらみなさんは valgrind の suppression ファイルが必要になったかもしれません)。

Atom プロセッサは驚くほど遅い(そして十分なレジスタを持っていない)

私はほとんどの作業を自分の Core-i7 2.66GHz ワークステーションで行い、ベンチマークもこのマシンで実行しました。Atom N450(1.66GHz) のネットブックに移った時、非常に異なる現実に直面しました。同じデータに対するベンチマークの結果が遅いだけではなく、アライメントやアライメントに関連する複雑な問題の影響がとても大きかったのです。前述の通り、最善の結果はアライメントを揃えたコードでした。SSSE3 の機能が有効になっている最速のコードはその次に速いコード(sse2_aligning)に比べて 10% も早かったのです。

遅い原因を調査するためにアセンブル結果を読んでみたところ、明らかにいくつかのケースでレジスタへの過負荷が見られました。32 ビットの x86 の PIC コードで利用可能な汎用レジスタの数は 6 個だけです(eax, ecx, edx, esi, edi, ebp で、これはフレームポインタ無しの場合です。gcc は PIC が完全に必要ない場合にもそのレジスタを使用しません)。これらの半分は呼出先退避レジスタで、もう半分は呼出元退避レジスタです。半分はデータ自体(ポインタ２つと長さ)で使用されるため、前処理は残されたわずか３つのレジスタで行うことになります。このため、いくつかの中間結果をメモリに移動する必要が出てしまい、パフォーマンスに大きな影響を与えていました。

128 個の汎用レジスタを持つ IA-64 や 32 個の UltraSPARC が私はうらやましいです。レジスタローテーションメカニズムの使用や、UltraSPARC での９個のスクラッチ(呼出元退避)レジスタ(%g1, %g4, %g5, %o0-%o5)、 x86-64 での９個(rax, rcx, rdx, rsi, rdi, r8-r11)や Itanium での 27 個(r2, r3, r8-r11, r14-r31 それに加えて３個の入力レジスタ in0-in2 [r32-r34])等を使用せずともこのような(他の関数を呼び出さない)関数を呼び出せるからです。ARM でもスクラッチレジスタこそ４個しか持っていませんが、８個の呼出先退避レジスタがさらに利用可能です。

Intel と AMD へ、いつになったら 32 ビットマシンで追加の８個の汎用レジスタを使えるようになるの？

QString では文字列長は既に分かっている

新しい SSE 4.2 の文字列比較命令の使い方を学びましたが、その間文字列長を使用したサンプルを１つも見つけられませんでした。全てのサンプルが(あらかじめ文字列長は分からず、NUL マークが最後にある)暗黙の文字列長を使用したものでした。真っ先に言いたいことですが、２つの文字列の長さが異なる場合にはその２つは同じになり得ないためこれはとても重要です。これは qMemEquals の呼ばれる回数が QString::operator== と比較して 大幅に 減少できることを意味します。ucstrncmp でさえ、２つの文字列で短い方の文字列長の部分を比較するだけで済むようになります(もしその部分が同じであれば短い方の文字列を小さいと評価すればよいので)。

しかし、明らかにもう１つ大きな違いがあります。文字列長が不明の場合は、メモリからロードされた 16 バイトの中に NUL が含まれるかどうかを特殊なシナリオとしてチェックする必要があります。SSE 4.2 の新しい PCMPISTRI と PCMPISTRM 命令は比較の中で NUL チェックをするので、これらは素晴らしいはずです。文字列長が既知の場合ではこれらの命令(PCMPESTRI と PCMPESTRM)では前の SSE のコードと比較して大きな改善は見られませんでした。

前述の点に追加して、既知の文字列長を使用する命令はさらに２個のレジスタを入力用に使用するので、さらにレジスタへの負荷は増大します。

みなさんの助けが必要です

私は十分な時間をこれに費やしたと思っています。(文字列が短い場合の)制約はありますが、それぞれの最適化により少しずつ改善されています。私にはこれ以上の改善をするための知識とツールがありません。この記事を読んでくれたみなさん、このパフォーマンスを改善するための知恵をお貸しください。