以前の記事では「OTP17系ではmapsの内部実装に単純な連想リスト(配列)が使われており要素数に対して性能がスケールしない」といったことを書いた。
先日に出たOTP18.0のリリースノートには「要素数が多いmapsにはHAMT(Hash Array Mapped Trieの略: もの凄く雑に言うなら永続化に対応したハッシュテーブル的な性質を備えたデータ構造)を使うようにした」的なことが書かれており、大幅な性能改善が期待できるので、あらためて処理時間を計測してみた。
(内容的にほぼ前回のコピペ)
測定環境
前回とは測定環境は異なる:
- CPU: Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz (x4)
- OS: Ubuntu-15.04
- Erlang: OTP18.0 (deb)
測定対象
前回と同様:
- maps, dict, gb_trees
- 全てのモジュールはHiPEでコンパイル
測定方法
これも前回と同様:
- 入力値は、0から要素数未満の数値をランダムに並べたもの
- 入力値を順に挿入していき、全要素を挿入するまでに掛かった時間を計測
- 全要素の処理に掛かった時間を要素数で割って、一要素の挿入に掛かった平均時間を算出
- この一要素あたりの平均処理時間が、今回の測定結果となる
- なお挿入以外の処理(ex. 削除、検索)は今回の対象外とするが挿入と同様の処理傾向を示している
-module(bench).
-export([bench/0]).
-spec bench() -> [Result] when
Result :: {module(), ElementSize::pos_integer(), InsertAverageNanoSeconds::non_neg_integer()}.
bench() ->
ElementSizeList = [1, 10, 100, 1000, 10000, 100000],
InputList = [shuffle(lists:seq(0, Size - 1)) || Size <- ElementSizeList],
ModuleList = [dict, gb_trees, maps],
lists:sort(
[do_bench(Module, Input) || Module <- ModuleList,
Input <- InputList]).
-spec do_bench(module(), [non_neg_integer()]) -> Result when
Result :: {module(), ElementSize::pos_integer(), InsertAverageNanoSeconds::non_neg_integer()}.
do_bench(Module, Input) ->
ElementSize = length(Input),
LoopCount = 100000 div ElementSize, % 一回のベンチマーク中の挿入操作の回数を等しくさせるために、ループ数で調整する
Empty = make_empty(Module),
Fun = get_insert_fun(Module),
{TotalMicroSeconds, _} =
timer:tc(fun () -> bench_loop(LoopCount, Empty, Fun, Input) end),
AverageNanoSeconds = round((TotalMicroSeconds * 1000) / 100000),
{Module, ElementSize, AverageNanoSeconds}.
-spec make_empty(module()) -> term().
make_empty(dict) -> dict:new();
make_empty(gb_trees) -> gb_trees:empty();
make_empty(maps) -> maps:new().
-spec get_insert_fun(module()) -> fun ((term(), term(), term()) -> term()).
get_insert_fun(dict) -> fun dict:store/3;
get_insert_fun(gb_trees) -> fun gb_trees:enter/3;
get_insert_fun(maps) -> fun maps:put/3.
-spec shuffle(list()) -> list().
shuffle(List) ->
[X||{_,X} <- lists:keysort(1, [{random:uniform(), N} || N <- List])].
-spec bench_loop(non_neg_integer(), term(), function(), [non_neg_integer()]) -> ok.
bench_loop(0, _, _, _) -> ok;
bench_loop(LoopCount, Empty, Fun, Input) ->
_ = lists:foldl(fun (N, Acc) -> Fun(N, N, Acc) end, Empty, Input),
bench_loop(LoopCount - 1, Empty, Fun, Input).
測定結果
OTP18.0
表の値は、一つの挿入操作に要した平均時間(ナノ秒単位)。
| 要素数 ＼ モジュール | dict | gb_trees | maps |
|---|---|---|---|
| 1 | 307 | 104 | 74 |
| 10 | 221 | 114 | 61 |
| 100 | 283 | 173 | 122 |
| 1000 | 415 | 331 | 144 |
| 10000 | 582 | 555 | 212 |
| 100000 | 2093 | 1129 | 492 |
全てのケースでmapsが一番良い結果となっている。
OTP17.1
参考までに前回の測定結果も載せておく。
| 要素数 ＼ モジュール | dict | gb_trees | maps |
|---|---|---|---|
| 1 | 355 | 165 | 192 |
| 10 | 260 | 126 | 162 |
| 100 | 321 | 216 | 375 |
| 1000 | 461 | 344 | 2444 |
| 10000 | 763 | 564 | 26274 |
| 100000 | 2076 | 1255 | 323424 |
前回と今回とでは測定環境が異なるので個々の数値自体の比較にはあまり意味はないが、OTP18になってmapsの(要素数に対する)性能が明らかに向上していることは見てとれる。
感想
mapsは組み込み型ということもありパターンマッチが利用できるので、もともと他の類似データ構造(e.g. dict、連想リスト)に比べて利便性が高かった。
%% mapsを使った分岐の例: 複数キーを使った条件判定が簡単
case Map of
#{hoge := 10} -> ok;
#{fuga := 20} -> ng
end.
%% 同様の処理の連想リストでの実装例
case {proplists:get_value(hoge, List), proplists:get_value(fuga, List)} of
{10, _} -> ok;
{_, 20} -> ng
end.
OTP17で懸念であった性能面が改善されたのであれば、もう辞書的なデータ構造に関しては基本的にmaps一択で良いような気がする。
(用途に合わない場合だけ他のデータ構造を選択する)
追記: 2015-06-30
ちなみにOTP18.0のREADMEには、mapsに関して「Memory consumption size is probalistic but lesser than gb_trees or dict for instance」といった記述があり、メモリ消費量の点でもmapsの方が優れているようである。
(mapsと連想リストとの比較であれば、後者の方が構造が単純な分、メモリ消費量が少ない可能性はあると思うが)