Help us understand the problem. What is going on with this article?

OTP18.0のmapsの簡易速度計測

More than 5 years have passed since last update.

以前の記事では「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でコンパイル

測定方法

これも前回と同様:

  1. 入力値は、0から要素数未満の数値をランダムに並べたもの
  2. 入力値を順に挿入していき、全要素を挿入するまでに掛かった時間を計測
  3. 全要素の処理に掛かった時間を要素数で割って、一要素の挿入に掛かった平均時間を算出
    • この一要素あたりの平均処理時間が、今回の測定結果となる
    • なお挿入以外の処理(ex. 削除、検索)は今回の対象外とするが挿入と同様の処理傾向を示している
bench.erl
-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と連想リストとの比較であれば、後者の方が構造が単純な分、メモリ消費量が少ない可能性はあると思うが)

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした