たけまる / ets で bag と set のどちらを使うべきか

_ ets で bag と set のどちらを使うべきか [erlang]

Erlang には ets というハッシュテーブルがあります．これはプロセス間
で状態を共有するときなどに利用します．

一般のハッシュテーブルは，キーに対応する値をひとつしか持てませんが，
ets では複数の値を持たせることができます．そのためには，初期化する
ときに bag という種類のテーブルを指定します．

bag では一つのキーが複数の値を持つことができます．

キー	値
a	1, 2, 3
b	1, ...

実際に動かすときは，こんな感じです．

> T = ets:new(mybag, [bag]).
> ets:insert(T, {a,1}).
> ets:insert(T, {a,2}).
> ets:lookup(T, a).
[{a,1},{a,2}]

ただし，同じ値を複数持つことはできません．つまり，次のようなことは
ありません．

キー	値
a	1, 1, 1
b	1, ...

また，通常の set という種類のテーブルでもリストを使うことによって，
同じことはできます．

キー	値
a	[1, 2, 3]
b	[1, ...]
...

さて，bag と set のどちらを使うべきでしょうか．性能を比較したことが
あったので，その結果を紹介します．

■ 単純な速度比較

実験を行い，bag と set に値を追加する速度を比較しました．

bag の場合は，複数のキー・値ペアを作り，それを追加しました．たとえ
ば，3 つの値を追加するときは，次のようになります．

> ets:insert(T, [{a,1}, {a,2}, {a,3}]).

これに対し，set では複数の値をリストにまとめ，それをキーと対応づけ
て追加しました．

> ets:insert(T, {a, [1,2,3]}).

値の数を変化させながら実験を行いました．表は，1024 試行にかかった
時間です．

値の数	bag [usec]	set [usec]	bag/set
1	2479	2469	1.00
4	6850	3878	1.77
16	28538	8876	3.22
64	185535	24948	7.44
256	1835755	83339	22.0
1024	28822918	459741	62.7

値の数が増えるほど bag が遅くなっています．bag の実装を調べていない
ので，はっきりした理由はわかりませんが，次のようなことが言えそうで
す．bag では，追加しようとしている値がすでに存在するかどうかをチェッ
クします．これにより，値の数が多いほど bag が遅くなっているのでしょ
う．

メモリ使用量は次のようでした．単位は word 数です．

値の数	bag	set	bag/set
1	10552	12600	0.84
4	42039	18744	2.24
16	166711	43320	3.85
64	665143	141624	4.70
256	2659383	534840	4.97
1024	10636471	2107704	5.05

■ 値チェックをしてから追加

では，どういうときに bag を使ったらよいのでしょうか．bag が強みを発
揮する状況を考えてみました．

実際には，すでに存在するキー・値ペアに，さらに値を追加するようなこ
とがあるでしょう．たとえば，次のような表があったとして，

キー	値
a	1, 2

a に 3 を追加して，次のようにします．

キー	値
a	1, 2, 3

このようにして値を追加するとき，bag では単純に追加するだけですが，
set の場合には古い値を取り出して，新しい値を追加したリストを生成し，
追加し直すことになります．つまり，bag と set の操作は，それぞれ次
のようになります．

bag のとき:

> ets:insert(T, {a, 3}).

set のとき:

> V = ets:lookup(T, a).
> ets:insert(T, {a, [3|V]}).

このような条件で実験した結果が次の表になります．

値の数	bag [usec]	set [usec]	bag/set
1	2535	3478	0.73
4	10007	15162	0.66
16	39596	103670	0.38
64	229646	1302852	0.18
256	2068567	18765916	0.11
1024	28103824	336595985	0.083

先ほどと異なり，値の数が増えるほど bag のほうが速くなっています．
set の，値を取り出してから追加するという処理が，かなり重いようです．

メモリ使用量も示しておきます．単位は word 数です．

値の数	bag	set	bag/set
1	10552	17720	0.60
4	42039	33080	1.27
16	166711	94520	1.76
64	665143	340280	1.95
256	2659383	1323320	2.01
1024	10636471	5255480	2.02

メモリ使用量は，どちらの実験でも set のほうが少ないです．ただし，
set のメモリ使用量が先ほどより増えている理由は不明です (上書きされ
たメモリが garbage collection されてないのだと思うけど)．

■ まとめ

というわけで，速度を重視するのであれば，値を追加するときにすでに存
在する値を取得するかどうかで，bag と set の選択が決まりそうです．メ
モリを重視するのであれば，set が有利です．

なお，実際には値の大きさやキーの数によっても結果が変わってくると思
うので，この結果を参考に個々の状況に合わせて調べなおした方が安全で
す．

■ ソースコード

実験に使用したソースコードです．

-module(a).
-compile(export_all).
-define(KEYS, 1024).
-define(VALS, 1).

bag_insert(0) ->
    ok;
bag_insert(K) ->
    V = lists:map(fun(X) -> {K, X} end, lists:seq(1, ?VALS)),
    ets:insert(bag, V),
    bag_insert(K-1).

set_insert(0) ->
    ok;
set_insert(K) ->
    V = lists:map(fun(X) -> X end, lists:seq(1, ?VALS)),
    ets:insert(set, {K, V}),
    set_insert(K-1).

start() ->
    ets:new(bag, [bag, named_table]),
    {Usec, _} = timer:tc(?MODULE, bag_insert, [?KEYS]),
    io:format("bag: ~p [usec]~n", [Usec]),
    io:format("bag: ~p W~n", [ets:info(bag, memory)]),    
	
    ets:new(set, [set, named_table]),
    {Usec1, _} = timer:tc(?MODULE, set_insert, [?KEYS]),
    io:format("set: ~p [usec]~n", [Usec1]),
    io:format("set: ~p W~n", [ets:info(set, memory)]),

    ok.

-module(b).
-compile(export_all).
-define(KEYS, 1024).
-define(VALS, 1).

bag_insert(0) ->
    ok;
bag_insert(K) ->
    lists:foreach(
      fun(X) ->
              ets:insert(bag, {K, X})
      end,
      lists:seq(1, ?VALS)
     ),
    bag_insert(K-1).

set_insert(0) ->
    ok;
set_insert(K) ->
    lists:foreach(
      fun(X) ->
              V = ets:lookup(bag, K),
              ets:insert(set, {K, [X|V]})
      end,
      lists:seq(1, ?VALS)
     ),
    set_insert(K-1).

start() ->
    ets:new(bag, [bag, named_table]),
    {Usec, _} = timer:tc(?MODULE, bag_insert, [?KEYS]),
    io:format("bag: ~p [usec]~n", [Usec]),
    io:format("bag: ~p W~n", [ets:info(bag, memory)]),
	
    ets:new(set, [set, named_table]),
    {Usec1, _} = timer:tc(?MODULE, set_insert, [?KEYS]),
    io:format("set: ~p [usec]~n", [Usec1]),
    io:format("set: ~p W~n", [ets:info(set, memory)]),

    ok.