Kazuho@Cybozu Labs: Range Coder の展開速度を SSE で高速化 (してもらった)ご覧のように、データを出現頻度の降順で並び替えた上で SSE によるシーケンシャルサーチを使うことで、二分検索を使った場合と比べて 56% パフォーマンスが向上しています。また、この手法はデータのアクセスパターンも改善する (二分検索によるランダムアクセス→シーケンシャルアクセス) ので、前段で多数のテーブルの切り替えを行っている場合等にも有効です (キャッシュミスの影響が小さくなるため)。 この最適化を施した Range Coder は CodeRepos においてあります。興味のある方はご覧ください (/lang/cplusplus/range_coder/ - CodeRepos::Share - Trac) 。上のベンチマークは、 $ ./build_table.pl --ordered < ../calgary_corpus/paper1 > table.c && g++ -DR
