Erlangと配列 (つづき)

前回のつづきです。Erlangには配列がないものだと思い込んでいたのでこのようなエントリを書いたのですが、ふとReference Manualを見るとarrayという単語が...

以前書いたCRC32のルーチンに追加して再度計測してみました。

loop array tuple binary2 dict process_dictionary ets
1 9759 6035 7784 14556 5618 12727
2 10187 6050 8105 14794 5578 12338
3 9478 5823 7805 14912 5831 12796
4 9880 5985 8079 14972 5799 12796
5 10064 6001 7851 14754 5586 12465

あれ？あんまり早くないですね... 続いてWindows環境:

loop array tuple binary2 dict process_dictionary ets
1 16988 7720 10621 23196 8485 18048
2 17424 7689 10888 23227 8002 17783
3 17581 7768 11371 23010 8001 18127
4 17362 7877 10966 23134 8065 18502
5 17237 7551 10919 23291 8127 18298

やっぱり早くないです。というよりtupleの倍以上かかってますね。この結果だけを見るとtupleの方がいいなあと思えてきます。

コードは以下の通りです。一部コードを追加しただけなので構造に変化はありません。また、arrayに与えるフラグ(fixed)の有無は性能にはほとんど影響しないようでした。

-module(crc).
-compile(export_all).

-define(POLY_IEEE802_3, 16#EDB88320).

times(0, _, Res) ->
    lists:reverse(Res);
times(N, F, Res) when N > 0 ->
    times(N - 1, F, [F(N) | Res]).

pp(L) ->    
    io:format(
      ["|" ++
           [io_lib:format("~p|", [XX]) || XX <- X]
       ++ "\n" || X <- L]).

bench_all(Loop, Times) ->
    bench_tests(Loop, Times, [array, tuple, binary2, dict, process_dictionary, ets, zlib,erlang_crc]).

bench_tests(Loop, Times, Tests) ->
    Data = lists:seq(0,255),
    Bin = list_to_binary(Data),
    times(Loop,
	  fun(N) ->
		  lists:reverse(
		    lists:foldl(
		      fun(Type, List) ->
			      [ bench(Times, Type, Bin) div 1000 | List]
		      end, [(Loop - N + 1)], Tests))
	  end, [[loop|Tests]]).

bench(Times, Type, Bin) when Type =:= zlib orelse Type =:= erlang_crc ->
    Expected = crc(tuple, binary_to_list(Bin)),
    BBench = now(),
    do_bench(Times, Type, void, Bin, Expected),
    EBench = now(),
    timer:now_diff(EBench, BBench);
bench(Times, Type, Bin) when is_binary(Bin) -> 
    bench(Times, Type, binary_to_list(Bin));
bench(Times, Type, List) when is_list(List) ->
    Expected = crc(tuple, List),
    Table = make_table(Type, ?POLY_IEEE802_3),
    BBench = now(),
    do_bench(Times, Type, Table, List, Expected),
    EBench = now(),
    timer:now_diff(EBench, BBench).

do_bench(0, _Type, _Table, _List, _Expected) -> ok;
do_bench(Times, Type, Table, List, Expected) ->
    Expected = do_crc(Type, List, Table),
    do_bench(Times - 1, Type, Table, List, Expected).

calc_table(Poly, I) ->
    lists:foldl(
      fun(_J, U) ->
	      case (U band 1) of
		  1 ->
		      (U bsr 1) bxor Poly;
		  0 ->
		      U bsr 1
	      end
      end, I, lists:seq(0,7)).
calc_index(Res, B) ->
    (B bxor (Res band 16#ff)).
calc_crc1(Res, TableValue) ->
    (Res bsr 8) bxor TableValue.

crc(zlib, Bin) when is_binary(Bin) ->
    do_crc(zlib, Bin, void);
crc(Type, Bin) ->
    crc(Type, Bin, ?POLY_IEEE802_3).

crc(Type, Bin, Poly) when is_binary(Bin) ->
    List = binary_to_list(Bin),
    crc(Type, List, Poly);    
crc(Type, List, Poly) when is_list(List) ->
    Table = make_table(Type, Poly),
    do_crc(Type, List, Table).


make_table(tuple, Poly) ->
    lists:foldl(
      fun(I, Tuple) ->
	      erlang:append_element(Tuple, calc_table(Poly, I))
      end, {}, lists:seq(0, 255));
make_table(binary, Poly) ->
    lists:foldl(
      fun(I, Binary) ->
	      <<Binary/binary, (calc_table(Poly, I)):32>>
      end, <<>>, lists:seq(0, 255));
make_table(binary2, Poly) ->
    make_table(binary, Poly);
make_table(dict, Poly) ->
    lists:foldl(
      fun(I, Dict) ->
	      dict:store(I, calc_table(Poly, I), Dict)
      end, dict:new(), lists:seq(0, 255));
make_table(process_dictionary, Poly) ->
    lists:foldl(
      fun(I, _) ->
	      put(I, calc_table(Poly, I))
      end, void, lists:seq(0, 255));
make_table(ets, Poly) ->
    Table = ets:new(crc, [set]),
    lists:foreach(
      fun(I) ->
	      ets:insert(Table, {I, calc_table(Poly, I)})
      end, lists:seq(0, 255)),
    Table;
make_table(array, Poly) ->
    lists:foldl(
      fun(I, Array) ->
	      array:set(I, calc_table(Poly, I), Array)
      end, array:new(256, [{fixed,true}]), lists:seq(0, 255)).

do_crc(tuple, List, Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    Index = calc_index(Res, B),
		    calc_crc1(Res, element(Index + 1, Table))
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff;
do_crc(binary, List, Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    Index = calc_index(Res, B),
		    <<TableValue:32>> = binary:part(Table, Index * 4, 4),
		    calc_crc1(Res, TableValue)
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff;
do_crc(binary2, List, Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    Index = calc_index(Res, B) * 4,
		    <<_:Index/binary, TableValue:32, _/binary>> = Table,
		    calc_crc1(Res, TableValue)
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff;
do_crc(dict, List, Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    {ok, TableValue} = dict:find(calc_index(Res, B), Table),
		    calc_crc1(Res,  TableValue)
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff;
do_crc(process_dictionary, List, _Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    TableValue = get(calc_index(Res, B)),
		    calc_crc1(Res, TableValue)
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff;
do_crc(ets, List, Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    Index = calc_index(Res, B),
		    [{Index, TableValue}] = ets:lookup(Table, Index),
		    calc_crc1(Res, TableValue)
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff;
do_crc(zlib, Bin, _Table) ->
    Z = zlib:open(),
    Res = zlib:crc32(Z, Bin),
    zlib:close(Z),
    Res;
do_crc(erlang_crc, Bin, _Table) ->
    erlang:crc32(Bin);
do_crc(array, List, Table) ->
    CRC = lists:foldl(
	    fun(B, Res) ->
		    Index = calc_index(Res, B),
		    calc_crc1(Res, array:get(Index, Table))
	    end, 16#ffffffff, List),
    (bnot CRC) band 16#ffffffff.