x86/x64最適化勉強会5 レポート

こんにちはサイボウズ・ラボの光成です。

今回は3月30日に開催された「x86/x64最適化勉強会5」の模様についてお伝えします。

x86/x64最適化勉強会会場

プログラム開発においては、開発の段階において早すぎる最適化は悪、本当に必要になってから最小限だけ行いなさいと言われています。 また今どきのコンパイラは優秀なので、下手な小細工はせずにコンパイラに任せておくのがよいとも言われています。

もちろん一般的にはそれは正しいのですが、普段動画や音声を利用するときに使われているコーデック、ネット上での決済時に利用される暗号ライブラリなどは、人の手によるアセンブリ言語で開発されていることが多いのもまた事実です。

私が主催しているこの勉強会はそういう下回りのライブラリを開発するときに必要な技術や情報の交換のために行っています。 ustreamで過去の会の動画も含めてみることができます。

以下、やや細かい内容を含みますが、今回の発表について簡単に解説します。

LLVM セッション

最初のセッションではプログラム開発基盤として注目されているLLVM関係のものにしました。 LLVMはC++11準拠度の高いC/C++コンパイラClangのバックエンドとしても利用されています。

最初は私が「LLVM入門」という題で発表しました(動画1)。 LLVMはCPUや環境に依存しない仮想マシン上をターゲットにしているのですが、 その仮想マシン上のLLVM IRアセンブラを使って簡単な関数を作る方法について説明しました。

llvm入門 from MITSUNARI Shigeo

調べてみるとLLVMは非常によくできたフレームワークではありますが、現状の仕様ではx86/x64でのcarry命令を扱いにくいことが分かりました。 そのためそれらを多用するプログラムでは高速なコードは書きづらいように思いました。

@maropuさんの発表は「LLVMで遊ぶ（整数圧縮とかx86向けの自動化とか）」でした(動画2)。 整数圧縮は2005年以降、学会などで活発に新しいアルゴリズムや実装が提案されているそうです。 maropuさんは自作の整数圧縮ライブラリvpackerでclangを使って自動ベクトル化に関する実験をしました。 自動ベクトル化するためのオプションや注意点などが紹介されました。残念ながら今のところgcc-4.8の自動ベクトル化には劣るようで、今後の期待だそうです。

LLVMで遊ぶ（整数圧縮とか、x86向けの自動ベクトル化とか） from Takeshi Yamamuro

@kazegusuriさんの発表は「人間でもわかるLLVMバックエンド入門」でした(動画3)。 kazegusuriさんは『きつねさんでもわかるLLVM』（柏木餅子 風薬）の著者の一人です。 LLVM IRから実際のターゲットCPUのコードへと変換、最適化されるまでの処理の流れを説明されました。 LLVMに手を入れたいときや、最適化処理がどうなっているのか調べたいときにこのような全体像を把握できる資料はとても役に立つと思います。

x86/x64系 セッション

次のセッションはx86/x64系の話でした。

青木和麻呂さんは暗号の研究者で、Camelliaを設計したり768ビットの素因数分解で世界記録を出したこともある方です。 今回の発表は「AES-NI@Sandy Bridge」でした(動画4)。

共通鍵暗号の一つであるAES暗号は広く使われているため高速な処理が望まれます。 x86/x64ではNehalemやSandy Bridge以降のCPUでAESを処理するための専用命令（AES-NI）が搭載されています。 普通に実装すると11個の命令を並べるしかないのですが、AES-NIを詳しく調査して、 どのような順序で他の命令を入れると最高性能を出せるかというお話をされました。 OpenSSLの実装よりも高速なものをえられたが、理論限界値には達成しない理由について考察されていてかなり濃い内容だと思います。

w_oさんの発表は「ハードウェアプリフェッチ」でした(動画5)。ハードウェアプリフェッチとはload命令などの履歴を調べて自動的に次に読むべき値を事前にフェッチする機能のことです。 さまざまなコードでベンチマークすることでその機能の効果を確認されていました。 Intelはよくあるパターンにおいて高速化されるような機能を入れているそうです。手動でのプリフェッチ命令の挿入で効果が出た経験があまりないのですが、ハードウェアに任せておけばよいのかなと思いました。

@s5yataさんの発表は「Remove Branches in BitVector Select Operations（marisa 0.2.2）」でした(動画6)。 s5yataさんはmarisa-trieという全文検索などを想定したメモリ効率のよい検索ライブラリの作者です。 今回はそのライブラリの中の基本関数であるselectの実装手法の紹介をしていただきました。 SSSE3で導入されたpshufbを使ったテーブル引きのアイデアなどすばらしかったです。

ARM セッション

今回の勉強会では実験的にx86/x64以外の話として最近スマートフォンなどで利用されているARMについてのセッションを入れてみました。

@takehiro_tさんの発表は「x86アセンブラはわかっている人がARMを学びだすとはまりがちなところ」でした(動画7)。 一言「ARM」と言ったときに何を指すのかという基本的な話から、フラグの扱い、ARMの特徴である条件付き実行が今では基本的に推奨されない、 即値に関する細かい制約など多岐にわたったディープな話でした。 そろそろARMの勉強しようと思っていたのでとてもよいナビゲーションになりました。

@naturyさんの発表は「ARM NEON」でした(動画8)。NEONを使う場合、実機でしか試せないので開発効率が悪く、自前のエミュレーション関数を用意したそうです。 複数の型に対応するために、大量の似た関数を作成しなければなりません。 普通ならスクリプト言語で自動生成か、C++のtemplateを使うかするところですが、naturyさんはBoost.Preprocessorを試してみたというところで会場にどよめきが起こりました。

クロージングセッション

最後はx86/x64向けにまた私が「フラグを愛でる」という発表をしました(動画9)。

フラグを愛でる from MITSUNARI Shigeo

Westmereまではフラグレジスタの依存関係によるパーシャルレジスタストールは非常に重いという制約がありました。暗号などで使われる多倍長整数演算加算を実装するときにフラグを退避するのではなくjrcxzという命令を使うことで速くなる例を示しました。またSandy Bridgeからはその制約が緩くなってよりシンプルで速いコードがかけるようになっていることも紹介しました。

なお5月下旬に発売予定のHaswellからはより高速にするためにフラグを変更しない命令群が追加されています。 ちなみにスライド内（20ページ）で紹介した1024ビットの加算コードは、たとえば「インテル®マイクロアーキテクチャーSandy Bridge向けワークロードの最適化」（53ページ）の例よりも速く動作するようです。

おわりに

今回もいろいろなお話が聞けてとても充実していました。 次回の開催日などはまだ決まっていませんが、『私も話したい!』という方がいらっしゃいましたら、ぜひとも私のtwitterアカウント@herumiまで表明してくださるとありがたいです。 よろしくお願いします。

最後になりましたが、毎回会場提供、無線LAN利用、およびustreamの中継をしてくださっている（株）AXELL社のご好意に感謝いたします。