結論
R17.0から導入されたmapsは、現在の実装では要素数が一定数(ex. 1000)を超えると急激に性能が劣化していくようなので注意が必要。
(確認バージョンは R17.0 および R17.1)
性能計測
環境
- CPU: Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz (x8)
- OS: CentOS 6.5
- Erlang: R17.1
測定対象
- maps, dict, gb_trees
- 全てのモジュールはHiPEでコンパイル
- mapsはほとんどがNIFで実装されているようなので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).
測定結果
表の値は、一つの挿入操作に要した平均時間(ナノ秒単位)。
| 要素数 ＼ モジュール | 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 |
要素数が100以下の場合は、HiPEでコンパイルされたdictやgb_treesと同程度の性能が出ているが、1000を超えると要素数にほぼ比例する形で、挿入処理の効率が悪くなってる。
ここまで性能が劣化するのはバグっぽいような気がするので、遠くないリリースで改善されることを期待したいが、現状では要素数が多くなるようなケースではmapsの使用は避けた方が無難そう。
追記: 2014/07/06
mapsの実装コード(例えば下記に引用したmaps:get/2の実装)を見てみると、現状は連想リストが内部データ構造として採用されているらしい。
/* maps:get/2
* return value if key *matches* a key in the map
* exception bad_key if none matches
*/
int erts_maps_get(Eterm key, Eterm map, Eterm *value) {
Eterm *ks,*vs;
map_t *mp;
Uint n,i;
mp = (map_t*)map_val(map);
n = map_get_size(mp);
if (n == 0)
return 0;
ks = map_get_keys(mp);
vs = map_get_values(mp);
if (is_immed(key)) {
for( i = 0; i < n; i++) {
if (ks[i] == key) {
*value = vs[i];
return 1;
}
}
}
for( i = 0; i < n; i++) {
if (EQ(ks[i], key)) {
*value = vs[i];
return 1;
}
}
return 0;
}
mapsが提案されているEEP-43には以下のような文章があったために、勝手にログオーダーな実装になっていることを期待してしまっていたが、そうではなかったらしい。(ここでも shall として言及されているので別に必須とはされていない)
The new data-type shall have semantics, syntax and operations that:
・... 略 ...
・has at most O(log N) time complexity in insert and lookup operations, where N is the number of key-value associations.
Similar data-types exists in other languages, i.e. perl hashes, ruby hashes, python dictionaries, or scala maps.
ただ、EEP-43を見るといくつかの箇所で、mapsは要素数が多くなってもlog(要素数)で操作が行えるものに成り得ることを示唆する文章が見受けられるので、将来的に内部構造が変更される可能性はありそう。
追記: 2014-12-31
『MAPs Now and Then』というビデオでOTP17でのmapsの扱いが詳細に説明されていた。
以下、要約:
- mapsはレコード的な役割とdict(or gb_trees,proplists,etc)的な役割の両方を果たすものとして導入された
- 前者はキーセットが固定かつ少数
- 後者はキーセットが動的かつ多数になり得る
- OTP17では、レコード的な役割としての部分のみが実装された
- 内部表現は線形リストで、要素数が64以下程度の比較的少数のものを想定
- OTP18では、dict的なデータ構造もカバーできるようになる予定
- 要素数が大きくなったら、内部表現がHash-Array-Mapped-Trieに切り替わるようにする(?)
追記: 2015-06-30
OTP18.0では無事性能が改善されていた。
詳細はこちらを参照のこと。