ハフマンデコードの改良

C++ Hamigaki LHA

真面目にハフマンツリーを作成するようにしました。
huffman.hppの差分
ツリーの作成に時間がかかりそうで避けていたのですが、参照回数の方が圧倒的に多いため、かなり速くなりました。
この状態でgprofの結果はこうです。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 22.95     19.61    19.61                             _Unwind_SjLj_Register
 11.88     29.76    10.15                             _Unwind_SjLj_Unregister

トップ2は例外アンワインド情報の登録/解除です。
この呼び出しを減らすためには、

  • デストラクタを持つ自動変数を減らす
  • 例外処理を含む関数の呼び出しループ回数を減らす

が、有効なはずです。
なので、boost::variantを共用体に、sliding_window_decompressをMutli-Character Filterに変更してみました。
sliding_window.hppの差分
lzhuff.hppの差分
gprofはこうです。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 17.50     11.04    11.04                             _Unwind_SjLj_Register
 11.27     18.15     7.11                             _Unwind_SjLj_Unregister

そこそこ減りましたが、まだ例外処理が三割も食っています。
VC++8でのタイムはこうなっています。

ツール 時間
UNLHA32.DLL 5秒
lzh_file_source(昨日のバージョン) 33秒
lzh_file_source(ハフマンツリー版) 9秒
lzh_file_source(Mutli-Character版) 7.5秒

単純に例外処理の分だけ負けている感じです。
あと、1秒は詰めたいなぁ。