« Range Coder の終了処理 | メイン | Pathtraq 最新ランキング ガジェットを公開しました »

2008年02月26日

Range Coder の展開速度を SSE で高速化 (してもらった)

 二分検索 (バイナリサーチ) は、分岐予測が効きにくいため、パイプラインが深い最近の CPU とは相性の悪い処理です。Range Coder の展開処理においても二分検索がボトルネックになるのですが、光成さんに「SSE で高速化できないんですかね」と話したところ、さくっとコードを書いてくれました。ありがとうございます。

 というわけで、まずは Calgary Corpus の paper1 でベンチマーク。

圧縮時間 (ticks)展開時間 (ticks)展開速度 (%)
標準 960 3,939 100%
標準+SSE 1,005 3,039 130%
降順 1,111 4,033 98%
降順+SSE 1,033 2,522 156%

 ご覧のように、データを出現頻度の降順で並び替えた上で SSE によるシーケンシャルサーチを使うことで、二分検索を使った場合と比べて 56% パフォーマンスが向上しています。また、この手法はデータのアクセスパターンも改善する (二分検索によるランダムアクセス→シーケンシャルアクセス) ので、前段で多数のテーブルの切り替えを行っている場合等にも有効です (キャッシュミスの影響が小さくなるため)。

 この最適化を施した Range Coder は CodeRepos においてあります。興味のある方はご覧ください (/lang/cplusplus/range_coder/ - CodeRepos::Share - Trac) 。上のベンチマークは、

$ ./build_table.pl --ordered < ../calgary_corpus/paper1 > table.c && g++ -DRANGE_CODER_USE_SSE -include mach/mach_time.h -Drdtsc=mach_absolute_time -Wall -g -O2 -funroll-loops bench.cpp && do ./a.out < ../calgary_corpus/paper1
等とすることで実行可能です。斜体になっているところがベンチマークを取る際に変更する部分。その他の ifdef 等は適当に切り替えてください。

投稿者 kazuho : 2008年02月26日 16:31 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1785