ErlangとCRC32 (つづき)
先日のErlangと配列の続きです。
あらすじ: zlib:crc32と、自前で実装したCRC32の性能を比較しました。自前で実装したCRC32は内部のテーブルの持ちかたをいろいろ変えて性能の違いを計ってみました。当たり前ですがzlibのものが一番早かったです。
今回はそんなに関係ないあらすじ: 一口にCRC32といってもいろんなバリエーションがあるので、IEEE 802.3 のものでなかったらzlib:crc32は使えないから嫌だなあと思い、もし自分で実装するとなるとErlangで配列に相当するデータ構造が必要だよね、でもいくつか思いつく手段のうちどれをとればいいのだろう？と疑問に思いました。(あらすじに続く)
Voluntasさんから、erlang:crc32/1 を使えばというコメントをいただきました。ありがとうございます。
(また、Voluntasさんには、Efficiency Guideの日本語版も紹介いただきました。ありがとうございます。OTP Design Principles と System Principles もあって感激です。)
さて、CRC32がBIFにあったなんて...盲点でした。盲点がでかすぎる気がしますね。恥ずかしいです。
あらためて計測しなおしてみました。まずMac:
- Erlang R14B03 (erts-5.8.4) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]
- Mac OS X Server 10.6.8
- Processor 2.53GHz Intel Core 2 Duo
- Memory 4GB 1067MHz DDR3
| loop | tuple | binary2 | dict | process_dictionary | ets | zlib | erlang_crc |
| 1 | 5734 | 7671 | 13954 | 5658 | 12408 | 430 | 429 |
| 2 | 5763 | 7673 | 14028 | 5624 | 12488 | 457 | 453 |
| 3 | 5726 | 7616 | 13994 | 5612 | 12368 | 428 | 429 |
| 4 | 5762 | 7682 | 14031 | 5673 | 12432 | 427 | 428 |
| 5 | 5755 | 7594 | 14014 | 5691 | 12567 | 430 | 429 |
次にWindows:
- Windows 7
- Processor 2.13GHz Intel Core 2 Duo
- Memory 2GB
| loop | tuple | binary2 | dict | process_dictionary | ets | zlib | erlang_crc |
| 1 | 7691 | 10685 | 22681 | 7969 | 16769 | 483 | 46 |
| 2 | 7471 | 10514 | 22744 | 8034 | 19671 | 529 | 46 |
| 3 | 8439 | 13368 | 23447 | 8316 | 17050 | 483 | 61 |
| 4 | 7643 | 10561 | 22697 | 8033 | 16988 | 483 | 61 |
| 5 | 7783 | 10576 | 22963 | 8220 | 16898 | 483 | 46 |
最後のerlang_crcというのがerlang:crc32を使ったときの結果です。前回と同様、10万回ずつ試しています。前回との違いは、
- 試行を5回(つまり10万回を5回)に減らしました(前回は10回でした)
- 前回没にしたbinary2を採用しています(くわしくは前回の記事を御覧下さい)
といったところです。Windows版のerlang_crcが目の覚めるようなスピードで動いていますね... ertsのソースを軽く見た限りではMacとWindowsでそんなに劇的に変わる気配は感じられなかったので、もう少し読んでみる必要がありそうです。
ソースを再度載せます。erlang_crc を追加したのと、あとははてなダイヤリーに載せやすいように整形する関数(pp/1)を用意したくらいしか違いはありません。
-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, [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. 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).
