« 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