QStrings と Unicode — QString::fromUtf8 の最適化

この記事は Qt Blog の "QStrings and Unicode — optimising QString::fromUtf8" を翻訳したものです。
執筆: Thiago Macieira 2011年3月25日

Other blogs in this series:
このシリーズのブログ記事

前々回 は Latin 1(ISO-8859-1)から QString の UTF-16 への変換の問題に挑戦しました。C++ のソースコードで使用されるほとんどの文字リテラルは ASCII の範囲内で、これは Latin 1 のサブセットであり UTF-16 に簡単に変換できることを意味します。このため、この処理のパフォーマンスはとても重要です。

しかし、2011 年にもなってなぜ ASCII に限定する必要があるのか私は疑問に思いました。つまり、英語で翻訳前のメッセージを書く場合であってもマイクロ(μ)や度(°)、コピーライト(©)、さらにはユーロ記号(€)などの ASCII の範囲外の文字を必要とすることがあるでしょう。特に、最後のユーロ記号は意図的に例示しました。それはその他の文字とは違って Latin 1 にさえ含まれていないからです。ユーロ記号を表示するためには別の文字コードを使用する必要があります。これに加えて、2011 年現在、テキストをやり取りする際のデファクトスタンダードとなるエンコードは UTF-8 です。

私は自分に問いかけました。QString で使われるデフォルトのコーデックを Latin 1 から UTF-8 に変えたらどうだろうと。ここで頭をよぎったことは UTF-8 からの変換は Latin 1 に比べて非常に複雑なので、パフォーマンスの低下が起きるかもしれないということでした。私と Benjamin が行った全ての SIMD による変換の改善には勝てないでしょう。

これまで fromLatin1 の処理の最適化には十分に時間を費やしてきたので、ここからは UTF-8 の方を見てみることにしました。まず始めに QString::fromUtf8 で気づいたことは、QTextCodec で使用しているコードと同じコードを実行しているということでした。このため、QTextCodec を併用しなければ出来ないことがいくつかありますが、これに含まれる UTF-8 BOM の確認や、最初にステートをリストアし最後にセーブしているコード、また、不正な変換結果を U+FFFD の代わりに NUL で置換する等のオプションなどにより、この変換が遅くなる可能性があります。

まず始めに私が行ったのは、ステートレス化です。これはコードを削除することで行いました。結果は以下のグラフになりますが、悪い方向の結果も出ています。このため、fromLatin1 の経験を生かしてこのコードを書き換えることにしました。

ASCII 向けのコードを最適化するチャンスもありました。もしこれが QString のデフォルトのデフォルトのコーデックになった場合には、ほとんどの UTF-8 の文字列を構成する要素は ASCII になることが予想されます。このため、これも最適化すべき対象になります。以下のグラフは fromLatin1 の変換のベンチマークに使用したのと同じデータ(前々回の記事の最高の成果!)を使用し、UTF-8 の変換が Latin 1 と比べてどのくらい遅くなるのかを確認してみました。

汎用の C++ コードを書いた後は、それを SIMD 命令で最適化する次のステップに進みました。fromLatin1 のコードをコピーし、変換されるバイトでそれぞれのバイトセットの最上位のビットの有無を確認する必要がありました。SSE2 には SSE レジスタのそれぞれのバイトの最上位のビットを通常の CPU レジスタに保存する命令があるため簡単でした。以下にそのアルゴリズムを記述します。

  1. メモリから 16 バイトをロード
  2. 各バイトの最上位ビットがセットされているかを確認
  3. 何かセットされていればどのバイトかを特定する

どのビットがセットされているかを特定するのは簡単で "Bit Scan Forward" 命令が使用できます。ビットスキャンの結果はロードしたデータの中の最初の非 ASCII バイトになります。これにより、SSE2 のループを ASCII 向けと共通のままに保つことができ、non-ASCII を探索するための "move mask + bit scan" の命令を間に挟むだけで済みます。

もう1つ私が行ったことは、非 ASCII 文字が見つかった場所においても(ASCII 文字と同様に)16 バイトに変換されたデータを(アンパックした後)セーブすることです。これは一時的に無効な変換を保持していることを意味しますが、少なくともバイト列内の ASCII 部分は正しくメモリに保存されます。

それから、同じことを ARM の Neon に対しても行いました。この際2つの問題がありました。1つ目は、これの解決は簡単でしたが、ARM には(最下位からセットされているビットを検索する) "Bit Scan Forward" がないことです。しかし “Count Leading Zeros” 命令で最上位のビットがセットされているかを検索できます。レジスタのビット順を反転させる命令と併用することでこの問題が解決できました。

一番の問題は Neon には SSE2 の "move mask" に対応する、最上位のビットをロード済みのレジスタに展開する命令がないことです。これに相当するアルゴリズムがないかをインターネットで検索したところ、1つの AND 命令と3つの並列の追加処理で行うものを見つけました。しかし、パフォーマンスはそれほど良くはありませんでした…。代わりに VTEST 命令でビットがセットされている一番上の位置を探し、double-word の Neon レジスタを2つの ARM の 32 ビットのレジスタに振り分けることで解決しました。この後に上位ビットがセットされた場所を探索し UTF-8 に変換する通常のコードが続きます。

結果のグラフがこちらです。

グラフ

前回同様、最初のグループが各ハードウェアでの基準値で、これを 100% とします。次のグループは Qt 4.7 のコードからステート関連のコードを削除したものです。前述の通り若干遅い結果になっています。

3番目のグループは UTF-8 の変換をクロスプラットフォームで動作する純粋な C++ で書き換えたもので、ASCII に対する最適化を含みます。ARM ではそれほど改善されていません(5% 以下です)が、Atom では以前に比べ 50% 以上速くなっています[*]。4番目のグループは SIMD で最適化したコードで、前回のブログの教訓を全て生かした UTF-8 版のコードです。5番目も同じですが、不正な UTF-8 の入力チェックを省いたものです。

最初に書きましたが、そもそもの疑問はデフォルトのコーデックを Latin 1 から UTF-8 に変えた場合の影響がどのくらいになるかということでした。そして、その答えは最後の3つのグループになります。これらは fromLatin1 関数を同じデータでベンチマークをとったものの、基準値に対する値です。UTF-8 での現在のベストはLatin 1 のベストに対して 30 〜 50% 遅い結果になりました。

言い方を変えると、デフォルトは変えませんし、QLatin1String クラスをパフォーマンスに影響するコードのために残します。Qt の全ての場所が既にそうなってますし…。

[*] 50% 速いというのは、33.3% 少ない時間がかかるという意味です。くれぐれもお忘れなく。


Blog Topics:

Comments