Erlangとハフマン符号 (3) - no_orz_no

今回は前回の続きと、encodeを並列化する話です。

(前回のあらすじ)decodeを早くしようと、もともと1ビットずつのパターンマッチをしていた部分を、複数ビットを一度にマッチして1バイト分復号できるような無名関数を作って試してみたらオリジナルよりずっと遅かったという結果になりました。(あらすじ終わり)

遅くなった原因は、無名関数を呼んでいるからか、パターンマッチの個数が増えた＋複雑になったからか、いずれかだと考えました。無名関数でなくするために、いったん出力させた関数をソースに埋め込んで実行させるようにしてみました。ファイルが変わるたびに毎回手で入れ替えなければいけないので実用上の意味はありませんが、fun使うものと直接呼ぶものの違いは分かると思います。

decode3({Tree, Bin}) -> decode3(Tree, Bin).
decode3(Tree, Bin) ->
    decode3(Tree, Bin, <<>>).

decode3(_Tree, <<>>, Res) -> Res;
decode3(Tree, Bin, Res) -> 
    {B, Rem} = decode3_core(Bin),
    decode3(Tree, Rem, <<Res/binary, B/binary>>).

decode3_core(<<0:1, Rem/bitstring>>) -> {<<0:8>>, Rem};
decode3_core(<<128,0:2, Rem/bitstring>>) -> {<<253:8>>, Rem};
decode3_core(<<128,1:2, Rem/bitstring>>) -> {<<220:8>>, Rem};
decode3_core(<<128,2:2, Rem/bitstring>>) -> {<<57:8>>, Rem};
decode3_core(<<128,3:2, Rem/bitstring>>) -> {<<61:8>>, Rem};
decode3_core(<<129,0:2, Rem/bitstring>>) -> {<<202:8>>, Rem};
(以下略)

試してみたところ、decode(オリジナル、1ビットずつマッチする)は360000、decode2(前回作成のバージョン)は131566000、そしてdecode3は301000という結果になりました(単位はいずれもμsec、計測対象のファイルはオリジナルのサイズが500KB程度)。やはりfunの呼出しにかかるコストがかなりでかいようです。

次にencodeを高速化できないか考えてみます。すぐに思いつくのは並列化です。1バイトごとに変換できるテーブルを持っていますので、適当に分割して別プロセスでencodeを実行させれば、コアをきちんと全部使ってくれるようになると期待できます。

バイナリサイズが一定サイズを越えていたら2分割する、越えていなければ今まで通りencodeする、という作戦でいきましょう。まず、以前ちょっと試したfutureもどきをひっぱりだして使います...と思ったら行方不明だったので、1から作ってみます。

-module(future).
-export([get/1, execute/1]).

get(Pid) ->
    receive
	{Pid, Res} ->
	    Res
    end.

execute(F) ->
    Pid = self(),
    spawn(fun() -> bg(Pid, F) end).

bg(Pid, F) ->
    Pid ! {self(), F()}.

真面目に使うにはいろいろ問題がありそうな気がしますが、まずこれでよしとします。ではこれを使ってencodeの並列版を書いてみましょう。

prepare_tree(Bin) ->    
    Frq = make_frqtbl(Bin),
    Tree = make_huffman_tree(Frq),
    Sym = get_encodelist(Tree),
    Dic = 
	lists:foldl(
	  fun({X, Bits}, Acc) ->
		  dict:append(X, Bits, Acc)
	  end, dict:new(), Sym),
    {Tree, Dic}.

encode(Bin) ->
    {Tree, Dic} = prepare_tree(Bin),
    {Tree, encode_core(Dic, Bin)}.
encode_core(Dic, Bin) ->
    lists:foldl(
      fun(B, Acc) ->
	      {ok, [D]} = dict:find(B, Dic),
	      <<Acc/bitstring, D/bitstring>>
      end, <<>>, binary_to_list(Bin)).

encode2(Bin) ->
    {Tree, Dic} = prepare_tree(Bin),
    {Tree, encode2_core(Dic, Bin)}.

encode2_core(Dic, Bin) ->
    Size = size(Bin),
    case Size of
	Size when Size < 1024 * 256 ->
	    encode_core(Dic, Bin);
	Size ->
	    Size1 = Size div 2,
	    Size2 = Size - Size1,
	    <<Bin1:Size1/binary, Bin2:Size2/binary>> = Bin,
	    Pid1 = 
		future:execute(
		  fun() -> 
			  encode2_core(Dic, Bin1) 
		  end),
	    Pid2 =
		future:execute(
		  fun() ->
			  encode2_core(Dic, Bin2)
		  end),
	    NewBin1 = future:get(Pid1),
	    NewBin2 = future:get(Pid2),
	    <<NewBin1/bitstring, NewBin2/bitstring>>
    end.

並列になっているのはエンコード部分だけで、前段階のハフマン木作成などは元のままなので、エンコード部分だけをテストできるように関数を分けました。分割単位は256KBとしています。(特に根拠はありません)

では早速計測してみましょう...

6> {ok, Input} = file:read_file("c:/mingw/bin/gdb.exe").
{ok,<<77,90,144,0,3,0,0,0,4,0,0,0,255,255,0,0,184,0,0,0,
      0,0,0,0,64,0,0,...>>}
7> {Tree, Dic} = huffman:prepare_tree(Input).
{{[{[{0,658675},
     {[{[{[{[{131,44283},
(中略)
    2152222}],
  3598848},
 {dict,256,52,64,32,260,156,
       {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
       {{[[0,<<0:2>>],
          [192,<<104:7>>],
(中略)
          [41,<<242,3:2>>]],
         [],[],[],[],[],[],[],[],[],[],...}}}}
8> timer:tc(huffman, encode_core, [Dic, Input]).
{3476000,
 <<81,34,125,83,8,8,128,247,133,0,0,30,192,0,0,0,0,0,0,0,
   0,211,128,235,120,13,52,...>>}
9> timer:tc(huffman, encode2_core, [Dic, Input]).
{1839000,
 <<81,34,125,83,8,8,128,247,133,0,0,30,192,0,0,0,0,0,0,0,
   0,211,128,235,120,13,52,...>>}
10>

自宅のマシンは2コアなのでこの程度ですね。もうちょっとコアの多いマシンで試してみたいところです。

(追記) 8コアのマシンがあったので試してみました。

11> timer:tc(huffman, encode_core, [Dic, Input]).
{20531000,
 <<180,255,126,30,211,237,162,216,204,192,0,0,0,2,202,223,
   225,124,215,106,220,189,97,70,99,55,216,...>>}
12> timer:tc(huffman, encode2_core, [Dic, Input]).
{6860000,
 <<180,255,126,30,211,237,162,216,204,192,0,0,0,2,202,223,
   225,124,215,106,220,189,97,70,99,55,216,...>>}

コアが8つもあるのに3倍程度しか高速化されていませんね。分割サイズは、2〜4KB程度が一番成績がよく、それより大きくても小さくても性能が悪化します(圧縮対象のデータは16MBほどです)。