2015-08-20

特定オプション指定時にdialyzerのメモリ消費量が異様に大きくなる

Erlang

--get_warningsと-Wrace_conditionsの二つのオプションを合わせて指定すると、何故かメモリ使用量が大きくなってしまう模様。

例えば、以下のコマンド実行時には、メモリ使用量が途中で8GB(RAMサイズ)に達してしまい、PLTを構築することができなかった。
(上のオプションの内の片方だけを指定した場合は数百MB程度の消費量に収まる)

$ touch /tmp/dialyzer.plt
$ dialyzer --build_plt --get_warnings -Wrace_conditions --apps kernel --plt /tmp/dialyzer.plt

OTP17.5およびOTP18.0で現象が発生することを確認。
またstdlibを対象アプリケーションに指定した場合も同様の傾向が見られたので、アプリケーション固有という訳でもなさそう。

dialyzerのバグのような気もするので原因を特定して修正した方が良いのかもしれないが、自分の使用用途では--get_warningsを指定しなくても特に困ることはないので、とりあえずはその方向で回避する。

2015-05-14

優先度付きキュー系モジュールのベンチマーク

algorithm Erlang

『Purely Functional Data Structures』(略:PFDS)で紹介されている優先度付きキュー(+ α)をいくつか実装してみたので、その性能測定メモ。
なおPFDSは(データ構造がヒープ特性を満たしているかどうかに関係なく)優先度付きキュー群をまとめてヒープと呼称しているようなので、以降ではそれに倣うことにする。

測定対象

リポジトリ: heaps-0.0.3

測定対象モジュールは以下の通り:

leftist_heaps:
- PFDSの3.1の実装がベース
- ヒープ特性とLeftist特性を満たす二分木
  - ヒープ特性: 親ノードの値は、常に子ノードの値以下 (値が小さいほど高優先)
  - Leftist特性: 左の子のランクは、常に右の子のランク以上
  - ランクは「右の子を辿り続けて空ノードに至るまでのパスの長さ」
- 要素の挿入とヒープ同士のマージはO(log n)、最小値取り出しはO(1)、の最悪コスト
binomial_heaps:
- PFDSの3.2の実装がベース
- 森
  - ルートの各木はヒープ特性を満たす多分木
- 要素数の数値表現(ビット表現)に対応した構造が常に維持されるのが特徴
- 挿入はO(1)、マージと取り出しはO(log n)、の償却コスト
splay_heaps:
- PFDSの5.4の実装がベース
- 二分探索木
- 各操作実行時に辿った経路のみをバランス(スプレー)し、よくアクセスされる要素ほど木のルート近くに配置されるようにする
- 挿入/取り出しはO(log n)の償却コスト
- マージはO(n)の最悪コスト
pairing_heaps:
- PFDSの5.5の実装がベース
- ヒープ特性を満たす多分木
- 要素の挿入やマージ時には木のバランスを取ることはしない
  - ルート要素と比較して、その親にするか子にするかを決めるだけ
  - 要素取り出し時に直下の子供たちに対してマージを適用して部分バランスを行う
- 挿入/マージ/取り出しはO(log n)の償却コスト
  - 証明はされていないが、挿入とマージはO(1)の償却コストであると推測されているらしい
gb_set_heaps:
- gb_setsを内部で利用しているヒープ
  - gb_setsはErlang/OTPの標準ライブラリに含まれる平衡２分探索木
  - gb_setsは名前の通り集合を表現するものであり、ヒープのような重複を許容するデータ構造には直接転用できない
    - 仕方がないので、各要素をユニークにするためのシーケンス番号を追加で付与するようにした
    - => 本来的には不要なオーバヘッドが増えてしまっているのだけは、計測時に若干留意しておく必要がある
- 挿入/取り出しはO(log n)の最悪コスト
- マージはおそらくO(n)かO(n log n)の最悪コスト (推測であり未確認)
list_heaps:
- ソート済みリストによるヒープ実装
- 挿入とマージはO(n)の最悪コスト
- 取り出しはO(1)の最悪コスト (単にリストの先頭要素を取り出すだけ)

環境

CPU: Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz
OS: Ubuntu-15.04
Erlang/OTP: 17.5; パッケージ(.deb)

測定内容

測定用コード: heaps_bench.erl

以下の操作に掛かる時間を計測する:

要素の挿入:
- ひたすら要素を挿入して、一回辺りの挿入に掛かった平均時間を計測する
- 入力数は4^n (n = 2..7)
- 入力列のパターンは昇順、降順、ランダムの３つ
最小要素の取り出し:
- 全入力要素の挿入後に、ひたすら最小要素の取り出しを行い、一回辺りの取り出しに掛かった平均時間を計測する
- 入力数は4^n (n = 2..7)
- 入力列のパターンは昇順、降順、ランダムの３つ
挿入と取り出しの混合:
- 常時一定数の要素を保持しているヒープに対して、挿入と取り出しを繰り返す　 - セッション群やキャッシュ群の有効期限管理を行う場合等によくあるユースケース
  - スコアは(未来の)UNIXタイムスタンプとしてヒープに挿入し、その時間を実際に過ぎたら、有効期限切れとしてヒープから除去する
- 今回は、具体的には以下のような条件で計測を行う
  - ヒープの要素数は常に4^n (n = 2..7)
  - このヒープに対して「要素取り出し + 優先度が最低の要素の挿入」を一万回繰り返し、一回の処理の平均所要時間を計測する
二つのヒープのマージ:
- 要素数が4^n (n = 2..5)の二つのヒープのマージを千回繰り返し、一回の平均所要時間を計測する
- 各ヒープの要素にはランダムな値が使用される

測定結果

要素の挿入

計測内容(再掲):

ひたすら要素を挿入して、一回辺りの挿入に掛かった平均時間を計測する
入力数は4^n (n = 2..7)
入力列のパターンは昇順、降順、ランダムの３つ

入力が昇順の場合

%% [計測関数]
%% N = 2..7
> heaps_bench:bench_in(lists:seq(1, trunc(math:pow(4, N)))).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.395 μs	0.229 μs	0.125 μs	0.083 μs	0.854 μs	0.270 μs
64	0.422 μs	0.120 μs	0.089 μs	0.073 μs	1.115 μs	0.656 μs
256	0.533 μs	0.121 μs	0.063 μs	0.056 μs	1.467 μs	2.460 μs
1024	0.672 μs	0.115 μs	0.061 μs	0.054 μs	1.995 μs	10.372 μs
4096	0.838 μs	0.147 μs	0.118 μs	0.107 μs	2.823 μs	41.247 μs
16384	1.050 μs	0.130 μs	0.078 μs	0.067 μs	2.846 μs	166.472 μs

pairing_heapsが一番高速
paring_heaps、splay_heaps、binomial_heapsは入力数によらずO(1)で挿入可能
leftist_heapsとgb_set_heapsはO(log n)
list_heapsはO(n) (常にリストの末尾への追加となる)

入力が降順の場合

%% [計測関数]
%% N = 2..7
> heaps_bench:bench_in(lists:seq(trunc(math:pow(4, N)), 1, -1)).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.146 μs	0.146 μs	0.063 μs	0.063 μs	0.688 μs	0.063 μs
64	0.161 μs	0.135 μs	0.089 μs	0.063 μs	0.932 μs	0.031 μs
256	0.111 μs	0.126 μs	0.068 μs	0.057 μs	1.297 μs	0.026 μs
1024	0.131 μs	0.119 μs	0.068 μs	0.056 μs	1.737 μs	0.029 μs
4096	0.127 μs	0.119 μs	0.083 μs	0.063 μs	2.493 μs	0.049 μs
16384	0.147 μs	0.166 μs	0.079 μs	0.072 μs	2.574 μs	0.032 μs

list_heapsが一番高速 (常にリストの先頭への追加となる)
- ただしpairing_heapsとsplay_heapsの所要時間も(単なる先頭要素の追加に対して)二倍程度に収まっているので悪くはない
list_heaps、paring_heaps、splay_heaps、binomial_heaps、leftist_heapsは入力数によらずO(1)で挿入可能
gb_set_heapsだけがO(log n)

入力がランダムの場合

%% [計測関数]
%% N = 2..7
> heaps_bench:bench_in([random:uniform() || _ <- lists:seq(1, trunc(math:pow(4, N)))]).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.313 μs	0.125 μs	0.208 μs	0.063 μs	0.604 μs	0.146 μs
64	0.344 μs	0.135 μs	0.344 μs	0.073 μs	0.750 μs	0.401 μs
256	0.367 μs	0.132 μs	0.480 μs	0.053 μs	0.930 μs	1.323 μs
1024	0.493 μs	0.131 μs	0.727 μs	0.058 μs	1.171 μs	5.988 μs
4096	0.528 μs	0.150 μs	1.014 μs	0.060 μs	1.811 μs	24.181 μs
16384	0.724 μs	0.163 μs	1.209 μs	0.078 μs	2.027 μs	93.670 μs

pairing_heapsが一番高速
paring_heaps、binomial_heapsは入力数によらずO(1)で挿入可能
leftist_heaps、splay_heaps、gb_set_heapsはO(log n)
list_heapsはO(n)

実測結果のまとめ (挿入)

注意: 以降に出てくる実測値のオーダーは観測値を眺めての印象に基づくものであり、厳密なものではない

オーダー:

入力パターン	leftist	binomial	splay	pairing	gb_set	list
昇順	1	1	1	1	log n	n
降順	log n	1	1	1	log n	1
ランダム	log n	1	log n	1	log n	n

入力数=1024(4^5)の際の平均所要時間(μs):

入力パターン	leftist	binomial	splay	pairing	gb_set	list
昇順	0.672	0.115	二番:0.061	最速:0.054	1.995	10.372
降順	0.131	0.119	0.068	二番:0.056	1.737	最速:0.029
ランダム	0.493	二番:0.131	0.727	最速:0.058	1.171	5.988

pairing_heapsは優秀。

最小要素の取り出し

計測内容(再掲):

全入力要素の挿入後に、ひたすら最小要素の取り出しを行い、一回辺りの取り出しに掛かった平均時間を計測する
入力数は4^n (n = 2..7)
入力列のパターンは昇順、降順、ランダムの３つ

入力が昇順の場合

%% [計測関数]
%% N = 2..7
> heaps_bench:bench_out(lists:seq(1, trunc(math:pow(4, N)))).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.375 μs	0.167 μs	0.125 μs	0.208 μs	0.250 μs	0.042 μs
64	0.453 μs	0.214 μs	0.156 μs	0.167 μs	0.203 μs	0.063 μs
256	0.599 μs	0.230 μs	0.143 μs	0.164 μs	0.241 μs	0.047 μs
1024	0.842 μs	0.285 μs	0.156 μs	0.179 μs	0.230 μs	0.047 μs
4096	1.243 μs	0.286 μs	0.170 μs	0.316 μs	0.245 μs	0.043 μs
16384	1.428 μs	0.322 μs	0.156 μs	0.183 μs	0.268 μs	0.049 μs

list_heapsは先頭要素を取り出すだけなので速い
binomial_heapsとleftist_heapsはO(log n)。後者の方が劣化が激しい。
gb_set_treesがO(1)に見えるのが意外 (微増はしているけど)

入力が降順の場合

%% [計測関数]
%% N = 2..7
> heaps_bench:bench_out(lists:seq(trunc(math:pow(4, N)), 1, -1)).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.083 μs	0.188 μs	0.083 μs	0.063 μs	0.292 μs	0.042 μs
64	0.078 μs	0.229 μs	0.083 μs	0.052 μs	0.234 μs	0.063 μs
256	0.063 μs	0.230 μs	0.066 μs	0.057 μs	0.270 μs	0.046 μs
1024	0.069 μs	0.276 μs	0.073 μs	0.060 μs	0.249 μs	0.044 μs
4096	0.060 μs	0.297 μs	0.065 μs	0.061 μs	0.275 μs	0.045 μs
16384	0.068 μs	0.404 μs	0.069 μs	0.059 μs	0.287 μs	0.059 μs

一番速いのはやっぱりlist_heaps
ただし降順の場合は、lefist_heaps/splay_heaps/pairing_heaps、の所要時間がだいぶlist_heapsに近づいている
binomial_heapsとgb_set_heapsの傾向は、昇順の場合とほぼ同様

入力がランダムの場合

%% [計測関数]
%% N = 2..7
> heaps_bench:bench_out([random:uniform() || _ <- lists:seq(1, trunc(math:pow(4, N)))]).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.271 μs	0.417 μs	0.208 μs	0.188 μs	0.271 μs	0.042 μs
64	0.427 μs	0.526 μs	0.130 μs	0.313 μs	0.224 μs	0.068 μs
256	0.590 μs	0.779 μs	0.104 μs	0.406 μs	0.236 μs	0.042 μs
1024	0.807 μs	1.027 μs	0.116 μs	0.578 μs	0.310 μs	0.049 μs
4096	1.238 μs	1.643 μs	0.110 μs	0.684 μs	0.304 μs	0.056 μs
16384	1.543 μs	1.637 μs	0.107 μs	0.864 μs	0.326 μs	0.051 μs

lists_heapsが最速なのは変わらず
lefist_heaps, pairing_heaps, gb_set_heapsがO(log n)になり、他の入力順よりも性能が落ちている感がある

実測結果のまとめ (取り出し)

オーダー:

入力パターン	leftist	binomial	splay	pairing	gb_set	list
昇順	log n	log n	1	1	1	1
降順	1	log n	1	1	1	1
ランダム	log n	log n	1	log n	log n	1

入力数=1024(4^5)の際の平均所要時間(μs):

入力パターン	leftist	binomial	splay	pairing	gb_set	list
昇順	0.842	0.285	二番:0.156	0.179	0.230	最速:0.047
降順	0.069	0.276	0.073	二番:0.060	0.249	最速:0.044
ランダム	0.807	1.027	二番:0.116	0.578	0.310	最速:0.049

当然list_heapsが一番速い (全てのケースでリストの先頭要素を取り出すだけ)
二番目はsplay_heaps、三番目はpairing_heapsかgb_set_heapsのどちらか、といったところ

挿入と取り出しの混合

計測内容(再掲):

常時一定数の要素を保持しているヒープに対して、挿入と取り出しを繰り返す
- セッション群やキャッシュ群の有効期限管理を行う場合等によくあるユースケース
- スコアは(未来の)UNIXタイムスタンプとしてヒープに挿入し、その時間を実際に過ぎたら、有効期限切れとしてヒープから除去する
今回は、具体的には以下のような条件で計測を行う
- ヒープの要素数は常に4^n (n = 2..7)
- このヒープに対して「要素取り出し + 優先度が最低の要素の挿入」を一万回繰り返し、一回の処理の平均所要時間を計測する

%% [計測関数]
%% X = 2..7
> N = trunc(math:pow(4, X)),
> Input = [{in, I} || I <- lists:seq(1, N)] ++ [case I rem 2 of 0 -> out; 1 -> {in, I} end || I <- lists:seq(N+1, 10000+N+1)],
> heaps_bench:bench_in_out(Input).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.316 μs	0.258 μs	0.145 μs	0.130 μs	0.514 μs	0.209 μs
64	0.492 μs	0.292 μs	0.153 μs	0.142 μs	0.746 μs	0.646 μs
256	0.706 μs	0.314 μs	0.163 μs	0.150 μs	1.037 μs	2.436 μs
1024	0.861 μs	0.355 μs	0.165 μs	0.151 μs	1.339 μs	9.645 μs
4096	1.093 μs	0.369 μs	0.165 μs	0.167 μs	1.816 μs	39.733 μs
16384	1.093 μs	0.275 μs	0.155 μs	0.151 μs	2.460 μs	170.720 μs
	O(log n)	O(1)	O(1)	O(1)	O(log n)	O(n)

paring_heaps、splay_heaps、binomial_heapsの３つが、ヒープ内の要素数に影響を受けずにO(1)で各操作が行えていた
特にpairing_heapsとsplay_heapsの性能は良好

二つのヒープのマージ

計測内容(再掲):

要素数が4^n (n = 2..5)の二つのヒープのマージを千回繰り返し、一回の平均所要時間を計測する
各ヒープの要素にはランダムな値が使用される

%% [計測関数]
%% X = 2..5
> HeapSize = lists:seq(1, trunc(math:pow(4, X)),
> heaps_bench:bench_merge(
    [begin
         {[random:uniform() || _ <- HeapSize], [random:uniform() || _ <- HeapSize]}
     end || _ <- lists:seq(1, 1000)]).

結果:

入力数	leftist	binomial	splay	pairing	gb_set	list
16	0.478 μs	0.141 μs	3.765 μs	0.102 μs	4.575 μs	1.174 μs
64	0.825 μs	0.197 μs	15.291 μs	0.114 μs	16.559 μs	5.072 μs
256	0.960 μs	0.196 μs	65.527 μs	0.114 μs	69.478 μs	28.971 μs
1024	1.279 μs	0.159 μs	261.275 μs	0.110 μs	264.889 μs	78.302 μs
	O(log n)	O(1)	O(n)	O(1)	O(n)	O(n)

pairing_heapsとbinomial_heapsはO(1)でマージできている
leftist_heapsはO(log n)だが、これも十分高速
残りはO(n)であり、マージが重要な用途での使用は現実的ではなさそうな感じ

感想

今回計測したほぼ全てのケースで良好な結果が出ているので、基本的にはpairing_heapsを使っておけば問題はなさそう。
ただしsplay_heapsとの差は(マージの場合を除けば)結構軽微なので、実装や利用途によってはsplay_heapsの方が良い可能性もあるかもしれない。

2014-11-27

ErlangでUNIXドメインソケットのクライアント接続を行なう簡単な方法

Erlang Linux

Erlang(OTP-17.3)では標準でUNIX ドメインソケットをサポートされておらず、ちゃんと使おうとすると外部ライブラリが必要だったり、自前でポートドライバを書く必要があったりして、結構面倒。

ただ、特に性能等を気にせず簡単に使いたいだけなら、ncコマンド(netcat)がクライアント機能を持っているので、単にそれをラップすれば良い。

ncコマンドでのUNIX ドメインソケット使用方法

-Uオプションを付けることで、UNIX ドメインソケットが扱えるようになる。

サーバ:

# ※ 一つ以上のクライアントは接続不可
$ nc -U -l /tmp/hoge.socket

クライアント:

$ nc -U /tmp/hoge.socket

サーバとクライアントの通信は標準入出力経由で行なう。　

# サーバに"Hello World\n"とデータを送る
$ echo "Hello World\n" | nc -U /tmp/hoge.socket

Erlangから使う方法

erlang:open_port/2でncコマンドを呼び出すだけ。

-module(unix_socket).

-export([connect/1, send/2, close/1]).

%% @doc UNIXドメインソケット用のクライアント接続関数
-spec connect(string()) -> {ok, port()} | {error, Reason::term()}.
connect(UnixDomainSocketPath) ->
    %% open_port/2を使って、ncコマンドを呼び出す
    Command = "/bin/nc",
    Port = erlang:open_port({spawn_executable, Command},
                            [{args, ["-U", UnixDomainSocketPath]},
                             stderr_to_stdout, binary, exit_status]),
    receive
        %% 50ms以内にコマンドが停止したら、connect失敗扱いにする
        {Port, {exit_status, Status}} ->
            receive
                {Port, {data, ExitReason}} ->
                    {error, {abort, Command, [{status, Status}, {reason, ExitReason}]}}
            after 0 ->
                    {error, {abort, Command, [{status, Status}]}}
            end
    after 50 ->
            %% 接続成功
            {ok, Port}
    end.

-spec send(port(), iodata()) -> ok | {error, Reason::term()}.
send(Port, Data) ->
    try
        _ = erlang:port_command(Port, Data),
        ok
    catch
        error:Reason ->
            {error, Reason}
    end.

-spec close(port()) -> ok.
close(Port) ->
    erlang:port_close(Port).

使用例:

%% 事前に別のシェルで`nc -U -l /tmp/hoge.socket`が実行されているものとする

%% 接続失敗: 存在しないパスを指定
> unix_socket:connect("/tmp/fuga.socket").
{error,{abort,"/bin/nc",
              [{status,1},
               {reason,<<"nc: unix connect failed: No such file or directory\n">>}]}}

%% 接続成功
> {ok, S} = unix_socket:connect("/tmp/hoge.socket").
{ok,#Port<0.23824>}

%% データ送信
> unix_socket:send(S, <<"Hello\n">>). % サーバ側の端末に"Hello\n"と表示される
ok

%% データ受信:
%%   サーバ側の端末で"World\n"という文字列が入力されたものとする
> flush().
Shell got {#Port<0.23824>,{data,<<"World\n">>}}
ok

%% 切断
> unix_socket:close(S).
ok

デバッグ用途等であれば使えなくはない、程度のメモ書き。

2014-07-04

マップ系モジュールのベンチマーク

Erlang

最近、かなり以前に作成したErlangのハッシュマップ的なライブラリ(hashtrie)のrebar対応等を行う機会があったので、ついでにErlangでマップ的な処理を行うために使えるデータ構造(モジュール)群の性能測定をしてみた。

対象モジュール

dict
gb_trees
array ※ キーが非負の整数値の場合のみ
hashtrie-v0.1.3
splay_tree-v0.2.3

※ orddictは明らかに他に比べて遅いと思われたので対象外とした(別に含めても良かったかもしれない)
※ etsは破壊的な操作が含まれることにより、他のモジュールとの測定コードの共通化が面倒だったので対象外

なおR17.0から導入されたmapsの性能特徴に関してはQiitaの記事を参照のこと。

計測環境

CPU: Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz (x8)
OS: CentOS 6.5
Erlang: R17.1(rpm)

計測方法

ベンチマークコード: https://github.com/sile/hashtrie/blob/v0.1.3/src/hashtrie_bench.erl
- 計測対象の操作は挿入(store)、検索(find)、削除(erase) の三つ
  - 今回は簡単のために、検索および削除は、全て成功するキーで行っている (失敗探索等はない)
- キーの型は整数値と文字列(正確にはバイナリ) の二つ
  - 整数値の範囲は 0 から最大要素数までの連続する値
  - 文字列の場合は最大百バイトまでのランダムなバイト列
- 要素数は 1、10、100、1000、10000、100000 の六通り
  - 要素数が 1 の場合は百万回ループ、100の場合は一万回ループ、といったように操作の適用回数の合計が百万回になるようにして計測を行った
  - 最終的な計測値は、操作一回辺りの平均所要時間
- 入力要素の並び順はランダムと昇順のニパターン
全てのモジュールでHiPEコンパイルのON/OFFの両方で測定

計測結果

以下、縦軸は要素数で、横軸はモジュール名、セルの値は一操作辺りの平均所要時間(ナノ秒単位)。
※ 丸括弧内の数値はモジュールをHiPEでコンパイルした場合の各種操作の平均所要時間

ランダムに並んだ要素の挿入 (random-store)

キーが整数値

	array (hipe)	dict (hipe)	gb_trees (hipe)	hashtrie (hipe)	splay_tree (hipe)
1	319 (204)	820 (349)	262 (168)	347 (219)	168 (150)
10	197 (135)	678 (316)	532 (144)	325 (189)	624 (150)
100	356 (208)	995 (378)	925 (205)	572 (337)	1526 (296)
1000	434 (279)	1347 (546)	1515 (542)	594 (310)	2517 (618)
10000	535 (370)	1570 (767)	1795 (641)	681 (365)	3633 (970)
100000	719 (508)	2577 (1760)	2568 (1031)	952 (634)	4751 (1377)

array が全体的に性能が良くて、次に安定しているのは　hashtrie といった感じ。
要素数が少ない内なら gb_trees や splay_tree も結構良い値が出ている(HiPE版なら)。

後は、HiPEを適用した場合の効果が思ったよりも大きかった。

キーが文字列

キーが文字列の場合は array は対象外 (以下同)

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	820 (367)	241 (155)	372 (246)	166 (146)
10	795 (357)	708 (388)	377 (234)	742 (266)
100	1202 (489)	1250 (822)	694 (462)	1890 (721)
1000	1659 (776)	2193 (1406)	717 (394)	3158 (1353)
10000	1975 (1123)	3206 (2232)	865 (531)	4656 (2101)
100000	6035 (5211)	4716 (3601)	1401 (1091)	6923 (3847)

キーが整数値の場合に比べて、全体的にオーバヘッドが増えているように見えるが、傾向自体はそんなに変わらなそうな印象。
array がない分 hashtrie が優秀に見える。

昇順に並んだ要素の挿入 (sequential-store)

キーが整数値

	array (hipe)	dict (hipe)	gb_trees (hipe)	hashtrie (hipe)	splay_tree (hipe)
1	320 (204)	823 (352)	262 (169)	349 (219)	172 (154)
10	186 (138)	701 (316)	864 (257)	320 (188)	292 (120)
100	336 (191)	985 (368)	1942 (536)	572 (323)	295 (113)
1000	421 (252)	1336 (527)	3318 (1127)	594 (310)	328 (140)
10000	487 (296)	1508 (721)	4499 (1422)	681 (366)	335 (146)
100000	571 (352)	2603 (1802)	6058 (2106)	976 (669)	351 (160)

入力要素群がソートされている場合の挿入速度は splay_tree が圧倒的に早かった。 (スプレー木の特性上、この場合、単なるリストの先頭への要素追加とほぼ等しい処理となる。当然作成される木はバランスしていない)

array、hashtrie、dict は、入力のソートの有無は、あまり速度に影響がない模様。

gb_treesの場合は、入力がソートされている方が却って悪い結果となっていた。

キーが文字列

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	813 (368)	241 (155)	380 (246)	166 (145)
10	801 (361)	1182 (677)	376 (229)	351 (180)
100	1146 (493)	2869 (1786)	691 (441)	384 (189)
1000	1630 (765)	4887 (3156)	720 (416)	390 (210)
10000	1985 (1134)	6885 (4493)	865 (532)	405 (219)
100000	5978 (5260)	9577 (6535)	1359 (1042)	533 (368)

要素をランダムに検索 (random-find)

キーが整数値

	array (hipe)	dict (hipe)	gb_trees (hipe)	hashtrie (hipe)	splay_tree (hipe)
1	199 (149)	429 (227)	190 (153)	279 (163)	232 (144)
10	119 (89)	327 (163)	156 (96)	180 (108)	886 (166)
100	155 (124)	403 (197)	225 (111)	224 (111)	1866 (334)
1000	210 (159)	403 (200)	307 (168)	275 (146)	2916 (749)
10000	263 (200)	402 (219)	403 (238)	303 (172)	4061 (1156)
100000	320 (256)	459 (293)	540 (355)	356 (234)	5388 (1764)

ランダム検索は splay_tree だけが明らかに遅いのを除けば、それ以外のデータ構造間では、処理時間にそこまで大きな違いはなかった。
ただ、今回も array と hashtrie が他よりも性能が良い傾向があった。(gb_trees も入力サイズが小さいなら結構優秀)

splay_tree に関しては、データ構造の性質上、検索時等にも(部分的な)バランシングが行われるため、完全に読み込みのみの他のデータ構造に比べて性能が落ちるのは仕方がないが、最初に一回大規模な入力をもとにマップを作成して、後はひたすら検索のみ、といった用途には向かなさそう。
(とはいえ、検索されるキーが明らかに偏っている場合には、その限りではないが)

同じキーに対する検索と更新(or 削除)がセットになっているような処理の場合は、最初の検索時のバランシング(スプレー操作)により、後続の更新操作のコストが軽減されるので、必ずしも検索操作単体が遅いことが、実際のユースケースでの性能劣化にはつながらないようにも思うが、今回の計測では、そういった複雑な条件は全く考慮していないので、詳細は不明。

キーが文字列

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	435 (246)	176 (159)	308 (186)	231 (157)
10	403 (237)	215 (200)	240 (162)	1129 (362)
100	490 (280)	384 (356)	290 (170)	2289 (888)
1000	480 (285)	603 (554)	366 (213)	3631 (1540)
10000	509 (329)	895 (827)	407 (261)	5156 (2375)
100000	590 (421)	1257 (1201)	493 (368)	7961 (4355)

要素をシーケンシャルに検索 (sequential-find)

キーが整数値

	array (hipe)	dict (hipe)	gb_trees (hipe)	hashtrie (hipe)	splay_tree (hipe)
1	199 (149)	436 (232)	190 (154)	279 (164)	235 (147)
10	119 (89)	328 (163)	157 (97)	179 (109)	523 (127)
100	153 (124)	400 (195)	217 (110)	224 (112)	707 (145)
1000	211 (159)	393 (187)	290 (147)	271 (143)	753 (175)
10000	264 (199)	386 (201)	362 (179)	299 (167)	782 (202)
100000	317 (239)	453 (293)	453 (221)	360 (242)	808 (224)

splay_tree だけが（アクセスの局所性があがったことにより)処理速度が大幅に向上しているが、それ以外はランダムの場合とで大きな違いは見られない。
(あえて云えば gb_trees の性能は若干向上している)

キーが文字列

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	435 (246)	177 (159)	305 (186)	229 (157)
10	406 (246)	216 (201)	240 (163)	575 (222)
100	491 (279)	380 (354)	289 (170)	826 (323)
1000	477 (284)	575 (531)	365 (212)	895 (369)
10000	504 (323)	773 (707)	400 (256)	919 (388)
100000	569 (416)	995 (916)	491 (364)	1142 (554)

ランダム順での要素の削除 (random-erase)

キーが整数値

arrayモジュールには要素の削除がないので対象外 (以下同)

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	880 (338)	315 (151)	496 (198)	201 (133)
10	918 (311)	376 (105)	391 (157)	610 (165)
100	922 (357)	633 (148)	488 (208)	1464 (315)
1000	1086 (406)	917 (310)	509 (229)	2386 (617)
10000	1183 (524)	1206 (487)	607 (299)	3445 (910)
100000	2416 (1730)	1646 (838)	843 (533)	4659 (1418)

ランダム削除もだいたい他の操作と似たような傾向で hashtrie が全体的に速く、 gb_treesは要素数が比較的少ない場合に優秀、splay_treeは(局所がない)ランダムアクセスに弱い、という結果になっている。

キーが文字列

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	857 (327)	297 (174)	521 (226)	199 (145)
10	843 (333)	433 (238)	444 (207)	640 (218)
100	1103 (462)	928 (589)	586 (287)	1740 (648)
1000	1213 (509)	1449 (996)	606 (323)	2907 (1190)
10000	1470 (781)	2107 (1577)	736 (425)	4359 (1914)
100000	6095 (5450)	3229 (2714)	1217 (955)	6697 (3575)

シーケンシャルに要素を削除 (sequential-erase)

キーが整数値

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	880 (339)	315 (152)	498 (197)	203 (134)
10	917 (312)	324 (106)	379 (154)	305 (96)
100	838 (313)	400 (121)	487 (212)	414 (102)
1000	960 (348)	497 (157)	511 (230)	440 (120)
10000	1036 (449)	582 (173)	614 (303)	429 (110)
100000	2262 (1622)	676 (216)	912 (605)	446 (129)

これも他の操作と同様に、入力データがシーケンシャルに並んでいる場合は、splay_treeの処理速度が大幅に向上している。
(gb_trees もランダム削除の場合に比べて良い結果となっている)

キーが文字列

	dict(hipe)	gb_trees(hipe)	hashtrie(hipe)	splay_tree(hipe)
1	852 (322)	297 (173)	513 (233)	199 (147)
10	827 (323)	388 (212)	444 (208)	292 (120)
100	941 (433)	552 (334)	582 (303)	451 (162)
1000	1082 (472)	729 (474)	617 (329)	484 (178)
10000	1344 (752)	947 (641)	779 (464)	489 (196)
100000	5477 (4781)	1237 (915)	1171 (867)	562 (307)

感想

とりあえず今回測ってみた範囲内での感想:

arrayは、キーが整数値の場合は結構使えそう
- 思っていたよりも良い結果が出ていたので、目的があえば積極的に使っていっても良さそう
- ただし、入力の範囲が極端に疎だったり、値の上限が極端に大きい場合などは、性能が劣化する可能性もありそうなので注意が必要かもしれない
dictは、可もなく不可もない感じ
- 他のデータ構造に比べて極端に性能が劣るケースはなかった(若干削除が苦手？)が、その反対もなかった
- あえて使いどころを探すなら、大規模(数万件以上)なデータから一番初めに一回だけオブジェクトを作成して、後はひたすら検索のみ、というケースで有効かもしれない
gb_treesは、標準で提供されているマップ系のモジュールの中で一番使いやすそう
- 入力データサイズが小さい場合は、全般的に高速 (空オブジェクトの生成コストも低い)
- 入力データの並び順に依存して、結構処理性能に差がでたりはするが、それでも全般的にdictよりは速いことが多かった
- gb_trees:take_smallest/1 等を使えば、優先順位付キュー的な用途にも利用可能
  - ただし、最後の使用途の場合は splay_tree の方が良い選択である可能性がある
hashtrieは、安定して良い性能が出ていた
- 若干、数値が良すぎるような気がしないでもないので気になる (バグがないか)
- 削除時のテーブルのリサイズ(縮小)に未対応なので、一時的でもサイズが大きくなってしまうと、それを回収する方法がない
- とはいえ dict や gb_trees の大体として実験的に使っていっても良いかもしれない
splay_treeは、明らかに性能傾向が偏っている
- 汎用的なマップとして使用するには、ランダムアクセスに弱いのが厳しい
- 入力データが明らかに偏っていると分かっている場合にはかなり有効
  - 入力データサイズが小さい場合も効率的
- タイムスタンプのように常に上昇していく値をキーとした優先順位付きキューへの転用などには結構向いているかもしれない
  - 挿入時は木の末尾に、取り出し時は木の先頭に、アクセスが偏るため
- 用途が嵌れば便利に使えるので、個人的には結構お気に入り
データ構造の実装モジュールにHiPEは有効
- HiPEにするだけでコンスタントに数割程度(大きい時には数倍)は性能が向上していた

2012-01-03

erl-creole: ユニコード文字列とマルチバイト列の変換ライブラリ

Erlang library

少し必要になったのでErlangでユニコード文字列と各種エンコーディングのマルチバイト列(バイナリ)の相互変換を行うモジュールを作成した。
github: erl-creole-0.0.1

現状、対応しているエンコーディングは以下の通り*1:

UTF-8, Shift_JIS, CP932, EUC-JP, eucJP-ms, JIS(ISO-2022-JP), ISO-2022-JP-1

使用例

%% 入力文字列
> S = "Unicode (ユニコード) とは、世界中の多くのコンピュータ上の文字列を一貫した方法で符号化し、表現し、扱うためのコンピュータ業界の標準である。".

%% EUC-JPに変換
> creole:from_string(S, eucjp).
<<"Unicode (\&#230;\&#203;\&#179;&#161;&#188;\&#201;) &#164;&#200;&#164;&#207;&#161;¢&#192;&#164;&#179;釗&#195;&#230;&#164;&#206;&#194;&#191;&#164;&#175;&#164;&#206;\&#179;\&#243;\&#212;\&#229;&#161;&#188;\&#191;&#190;&#229;&#164;&#206;&#202;&#184;&#187;&#250;&#206;&#243;&#164;&#242;°&#236;´&#211;&#164;&#183;&#164;&#191;&#202;&#253;&#203;&#161;&#164;&#199;&#201;&#228;&#185;&#230;&#178;&#189;&#164;&#183;&#161;¢&#201;&#189;&#184;&#189;&#164;&#183;&#161;¢°&#183;&#164;釗&#164;&#191;&#164;&#225;&#164;&#206;\&#179;\&#243;\&#212;\&#229;&#161;"...>>

%% JIS(ISO-2022-JP)に変換
> Bin = creole:from_string(S, jis).
<<"Unicode (\e$B%f%K%3!<%I\e(B) \e$B$H$O!\"@$3&Cf$NB?$/$N%3%s%T%e!<%?>e$NJ8;zNs$r0l4S$7$?J}K!$GId9f2=$7!\"I=8=$7!\"07$&$?$a$N"...>>

%% バイト列からユニコード文字列に変換
> creole:to_string(Bin, jis).
[85,110,105,99,111,100,101,32,40,12518,12491,12467,12540,
 12489,41,32,12392,12399,12289,19990,30028,20013,12398,22810,
 12367,12398,12467,12531,12500|...]

> io:format("~ts~n", [creole:to_string(Bin, jis)]).
Unicode (ユニコード) とは、世界中の多くのコンピュータ上の文字列を一貫した方法で符号化し、表現し、扱うためのコンピュータ業界の標準である。
ok

%% 変換不能なバイト列がある場合は、デフォルトでは "?" が代わりに使用される
> io:format("~ts~n", [creole:to_string(<<"Unicode (\e$B%~^s^sjaf*(asf7aK%3!<%I">>, jis)]).
Unicode (??潁潁裃罟?癈羞疔コード
ok

%% "?"の代わりに"_"を使用
> io:format("~ts~n", [creole:to_string(<<"Unicode (\e$B%~^s^sjaf*(asf7aK%3!<%I">>, jis, creole:replace($_))]).
Unicode (__潁潁裃罟_癈羞疔コード
ok

*1:ユニコードと他のエンコーディングのコードポイントの対応は主に http://source.icu-project.org/repos/icu/data/trunk/charset/data/ucm/ を参考にさせてもらった。

2010-12-17

coverモジュールとsmerlモジュールを併用するためのパッチ

Erlang

Erlang。
デフォルトでは、coverモジュールとsmerlモジュールの併用が不可能(おそらく)なので、その問題を解消するためのパッチを作成。

cover:
- コードカバレッジ計測用モジュール
smerl:
- 「Simple Metaporgramming for Erlang」の略
- Erlangでメタプログラミングを行うためのモジュール
- erlweb配布パッケージに含まれる

使用したバージョンはErlangがR14B01、erlwebが0.7.1。

問題点

末尾のパッチが対象としている問題:

cover:compile関数を使ってカバレッジ測定用にコンパイルしたモジュールに対して、smerlを用いた関数の追加等の操作ができない。

普通にErlangを使っている分には、あまり関係ないかもしれない。
今回は、Erlang製のO/Rマッパー(?)であるerlydbを使用しているソースに対してカバレッジ計測を行うという要件があり、erlydbが内部的にsmerlを利用していたために上記問題が発生した。

以下、修正の概要:

coverモジュール:
- cover:compiled関数でカバレッジ測定用にコンパイルされたモジュールのbeamデータを取得するためのインターフェースを追加
  - smerlはローカルからbeamファイル(or erlファイル)を読み込む代りに、coverサーバからbeamデータを取得するようにする
- カバレッジ測定用コードを挿入したモジュールをコンパイルする際に、コンパイルオプションとしてdebug_infoを渡すように変更
  - smerlに必要な情報をbeamデータから読み込むためには、デバッグ情報付きでコンパイルされている必要があるため
  - beamにデバッグ情報が付与されていないと、smerlはモジュールのソースファイル(もちろんこれにはカバレッジ用のコードは挿入されていない)を直接使用してしまう
smerlモジュール:
- カバレッジ測定用にコンパイルされたモジュールに対応する処理を追加
  - 具体的には、モジュールがカバレッジ用にコンパイルされている場合、code:which関数はcover_compiledアトムを返すので、その対応の追加
    - beamデータ取得の際にcode:which関数がcover_compiledアトムを返したら、coverサーバに問い合わせるようにする
    - smerlが修正してコンパイルしたモジュールに対するcode:which関数呼び出しがcover_comiledアトムを返すようにタグを設定する

この修正がベストかどうかは分からないけど、応急処置の一つとしてメモしておく。

パッチ

パッチ適用方法。

# cover.erl
$ cd ${解凍ディレクトリ}/otp_src_R14B01/lib/tools/src/
$ patch cover.erl < cover.patch

# smerl.erl
$ cd ${解凍ディレクトリ}/erlyweb-0.7.1/src/smerl/
$ patch smerl.erl < smerl.patch

cover.patch:

*** cover.erl	2010-12-17 01:41:28.972951213 +0900
--- cover.erl.patched	2010-12-17 01:03:41.042983354 +0900
***************
*** 65,70 ****
--- 65,71 ----
  	 modules/0, imported/0, imported_modules/0, which_nodes/0, is_compiled/1,
  	 reset/1, reset/0,
  	 stop/0, stop/1]).
+ -export([get_compiled_beam/1]).
  -export([remote_start/1]).
  %-export([bump/5]).
  -export([transform/4]). % for test purposes
***************
*** 150,155 ****
--- 151,163 ----
  start(Nodes) ->
      call({start_nodes,remove_myself(Nodes,[])}).
  
+ %% get_compiled_beam(Module) -> Result
+ %%   Module = atom()
+ %%   Result = {ok,binary()} | {error, Reason}
+ %%     Reason = term()
+ get_compiled_beam(Module) ->
+     call({get_compiled_beam, Module}).
+ 
  %% compile(ModFile) ->
  %% compile(ModFile, Options) ->
  %% compile_module(ModFile) -> Result
***************
*** 548,554 ****
  				 compiled = Compiled},
  	    reply(From, {ok,StartedNodes}),
  	    main_process_loop(State1);
! 
  	{From, {compile, File, Options}} ->
  	    case do_compile(File, Options) of
  		{ok, Module} ->
--- 556,569 ----
  				 compiled = Compiled},
  	    reply(From, {ok,StartedNodes}),
  	    main_process_loop(State1);
!         {From, {get_compiled_beam, Module}} ->
!             case ets:lookup(?BINARY_TABLE,Module) of 
!                 [{Module,Beam}] ->
!                     reply(From, {ok, Beam});
!                 _ ->
!                     reply(From, {error, not_cover_compiled})
!             end,
!             main_process_loop(State);
  	{From, {compile, File, Options}} ->
  	    case do_compile(File, Options) of
  		{ok, Module} ->
***************
*** 1253,1259 ****
  	    %% Compile and load the result
  	    %% It's necessary to check the result of loading since it may
  	    %% fail, for example if Module resides in a sticky directory
! 	    {ok, Module, Binary} = compile:forms(Forms, []),
  	    case code:load_binary(Module, ?TAG, Binary) of
  		{module, Module} ->
  		    
--- 1268,1274 ----
  	    %% Compile and load the result
  	    %% It's necessary to check the result of loading since it may
  	    %% fail, for example if Module resides in a sticky directory
! 	    {ok, Module, Binary} = compile:forms(Forms, [debug_info]), 
  	    case code:load_binary(Module, ?TAG, Binary) of
  		{module, Module} ->

smerl.patch:

*** smerl.erl	2010-12-17 01:42:04.302955178 +0900
--- smerl.erl.patched	2010-12-17 01:42:20.942951890 +0900
***************
*** 166,171 ****
--- 166,179 ----
  			_Other ->
  			    {error, {invalid_module, ModuleName}}
  		    end;
+                 cover_compiled ->
+                     {ok, BeamBinary} = cover:get_compiled_beam(ModuleName),
+ 		    case get_forms(ModuleName, BeamBinary) of
+ 			{ok, Forms} ->
+ 			    mod_for_forms(Forms);
+ 			_Other ->
+ 			    {error, {invalid_module, ModuleName}}
+ 		    end;
  		_Err ->
  		    {error, {invalid_module, ModuleName}}
  	    end
***************
*** 594,603 ****
  		end,
  	    case Res of
  		ok ->
  		    code:purge(Module),
! 		    case code:load_binary(
! 			   Module,
! 			   atom_to_list(Module) ++ ".erl", Bin) of
  			{module, _Module} ->
  			    ok;
  			Err ->
--- 602,613 ----
  		end,
  	    case Res of
  		ok ->
+                     Tag = case code:which(Module) of
+                               cover_compiled -> cover_compiled;
+                               _ -> atom_to_list(Module) ++ ".erl"
+                           end,
  		    code:purge(Module),
! 		    case code:load_binary(Module, Tag, Bin) of
  			{module, _Module} ->
  			    ok;
  			Err ->

2010-10-24

erlterm: Erlang項とCommon Lispオブジェクトの相互変換

common lisp Erlang library

Erlang -- External Term Formatを参考にして、Erlangの項(のバイナリ表現)とCommon Lispのオブジェクトを相互変換するライブラリを作成。
・erlterm-0.0.1
ポートを用いた外部接続での利用を想定。
細かい作り込みや最適化はまだまだだけど、一応一通りの変換は行える。※ 未対応箇所に関しては、erltermのREADMEを参照

使用例

軽く使用例を。
使える関数はerlterm:decode-termとerlterm:encode-termの二つ。

;;;; Common Lisp側# Erlangから送られてきたリストを反転して送り返す
;;;; ファイル名: reverse.lisp
;;;;
;;;; 処理系: sbcl-1.0.40  
;;;;         ※ 標準入出力に対してバイナリ操作が行えるのは(おそらく)SBCLの拡張
(require :asdf)
(require :erlterm)

(handler-case
  (loop 
    (let ((list (erlterm:decode-term *standard-input* :packet 2)))     ; 受信
      (erlterm:encode-term (reverse list) *standard-output* :packet 2) ; 返信
      (force-output *out*)))
  (end-of-file ()
    'done))

%%%% Erlang側# ポート関連の操作をラップ
%%%% ファイル名: port_rpc.erl
-module(port_rpc).
-export([open/1,close/1,call/2]).

%% 接続
open(Command) ->
    open_port({spawn, Command}, [{packet, 2},binary]).
    
%% クローズ
close(Port) ->
    Port ! {self(), close}.

%% リクエスト送信
call(Port, Message) ->
    Port ! {self(), {command, term_to_binary(Message)}},  % バイナリに変換して送信
    receive 
        {Port, {data, Data}} -> binary_to_term(Data)      % レスポンスをバイナリから復元
    end.

%%%% Erlangシェル
%% コンパイル & ロード　
> c(port_rpc).
 => {ok,port_rpc}

%% lispプロセスを開く
> Port = port_rpc:open("sbcl --script reverse.lisp").
 => #Port<0.1723>

%% 送信するデータ
> List = [first, {self(), {1, "middle", 3.2}, make_ref()}, last].
 => [first,{<0.33.0>,{1,"middle",3.2},#Ref<0.0.0.66>},last]

%% リクエスト
> port_rpc:call(Port, List).
 => [last,{<0.33.0>,{1,"middle",3.2},#Ref<0.0.0.66>},first]

%% クローズ
> port_rpc:close(Port).
 => {<0.33.0>,close}

もう一つ。
Erlang項のデコード例。

%%%% Erlang
%% 上の例のリストをバイナリに変換して、ファイルに書き出す
> file:write_file("list.bin", term_to_binary([first, {self(), {1, "middle", 3.2}, make_ref()}, last])).

%% 無名関数をバイナリに変換して、ファイルに書き出す
> file:write_file("fun.bin", term_to_binary(fun (X) -> X*X*X end)).

;;;; Common Lisp
(require :erlterm)

;; Erlangのリストのバイナリデータを読み込む
(with-open-file (in "list.bin" :element-type '(unsigned-byte 8))
  (erlterm:decode-term in))
-->
(:FIRST
 #(#S(ERLTERM::PID :NODE :NONODE@NOHOST :ID 33 :SERIAL 0 :CREATION 0)
   #(1 "middle" 3.2d0)
   #S(ERLTERM::NEW-REFERENCE :NODE :NONODE@NOHOST :CREATION 0 :ID #(94 0 0)))
 :LAST)

;; Erlang無名関数のバイナリデータを読み込む
(with-open-file (in "fun.bin" :element-type '(unsigned-byte 8))
  (erlterm:decode-term in))
-->
#S(ERLTERM::NEW-FUN
   :SIZE 722
   :ARITY 1
   :UNIQ 75230672122209326657346363854110770891
   :INDEX 2
   :MODULE :ERL_EVAL
   :OLD-INDEX 6
   :OLD-UNIQ 13229925
   :PID #S(ERLTERM::PID :NODE :NONODE@NOHOST :ID 49 :SERIAL 0 :CREATION 0)
   :FREE-VARS #(NIL
                #(:VALUE
                  #S(ERLTERM::NEW-FUN
                     :SIZE 96
                     :ARITY 2
                     :UNIQ 9719462018325469980632351212009778472
                     :INDEX 7
                     :MODULE :SHELL
                     :OLD-INDEX 7
                     :OLD-UNIQ 115410035
                     :PID #S(ERLTERM::PID
                             :NODE :NONODE@NOHOST
                             :ID 49
                             :SERIAL 0
                             :CREATION 0)
                     :FREE-VARS #(#S(ERLTERM::PID
                                     :NODE :NONODE@NOHOST
                                     :ID 27
                                     :SERIAL 0
                                     :CREATION 0))))
                #(:EVAL
                  #S(ERLTERM::NEW-FUN
                     :SIZE 417
                     :ARITY 3
                     :UNIQ 9719462018325469980632351212009778472
                     :INDEX 14
                     :MODULE :SHELL
                     :OLD-INDEX 24
                     :OLD-UNIQ 81953817
                     :PID #S(ERLTERM::PID
                             :NODE :NONODE@NOHOST
                             :ID 49
                             :SERIAL 0
                             :CREATION 0)
                     :FREE-VARS #(#(:VALUE
                                    #S(ERLTERM::NEW-FUN
                                       :SIZE 96
                                       :ARITY 2
                                       :UNIQ 9719462018325469980632351212009778472
                                       :INDEX 7
                                       :MODULE :SHELL
                                       :OLD-INDEX 7
                                       :OLD-UNIQ 115410035
                                       :PID #S(ERLTERM::PID
                                               :NODE :NONODE@NOHOST
                                               :ID 49
                                               :SERIAL 0
                                               :CREATION 0)
                                       :FREE-VARS #(#S(ERLTERM::PID
                                                       :NODE :NONODE@NOHOST
                                                       :ID 27
                                                       :SERIAL 0
                                                       :CREATION 0))))
                                  8207
                                  #S(ERLTERM::NEW-FUN
                                     :SIZE 208
                                     :ARITY 1
                                     :UNIQ 9719462018325469980632351212009778472
                                     :INDEX 15
                                     :MODULE :SHELL
                                     :OLD-INDEX 14
                                     :OLD-UNIQ 68813366
                                     :PID #S(ERLTERM::PID
                                             :NODE :NONODE@NOHOST
                                             :ID 49
                                             :SERIAL 0
                                             :CREATION 0)
                                     :FREE-VARS #(#(:VALUE
                                                    #S(ERLTERM::NEW-FUN
                                                       :SIZE 96
                                                       :ARITY 2
                                                       :UNIQ 9719462018325469980632351212009778472
                                                       :INDEX 7
                                                       :MODULE :SHELL
                                                       :OLD-INDEX 7
                                                       :OLD-UNIQ 115410035
                                                       :PID #S(ERLTERM::PID
                                                               :NODE :NONODE@NOHOST
                                                               :ID 49
                                                               :SERIAL 0
                                                               :CREATION 0)
                                                       :FREE-VARS #(#S(ERLTERM::PID
                                                                       :NODE :NONODE@NOHOST
                                                                       :ID 27
                                                                       :SERIAL 0
                                                                       :CREATION 0))))
                                                  8207
                                                  #S(ERLTERM::PID
                                                     :NODE :NONODE@NOHOST
                                                     :ID 27
                                                     :SERIAL 0
                                                     :CREATION 0)))
                                  #S(ERLTERM::PID
                                     :NODE :NONODE@NOHOST
                                     :ID 27
                                     :SERIAL 0
                                     :CREATION 0))))
                ;; (X) -> X * X * X
                (#(:CLAUSE 1 (#(:VAR 1 :|x|)) NIL
                   (#(:OP 1 :* #(:OP 1 :* #(:VAR 1 :|x|) #(:VAR 1 :|x|))
                      #(:VAR 1 :|x|)))))))

測定対象

環境

測定内容

測定結果

要素の挿入

入力が昇順の場合

入力が降順の場合

入力がランダムの場合

実測結果のまとめ (挿入)

最小要素の取り出し

入力が昇順の場合

入力が降順の場合

入力がランダムの場合

実測結果のまとめ (取り出し)

挿入と取り出しの混合

二つのヒープのマージ

感想

ncコマンドでのUNIXドメインソケット使用方法

Erlangから使う方法

対象モジュール

計測環境

計測方法

計測結果

ランダムに並んだ要素の挿入 (random-store)

キーが整数値

キーが文字列

昇順に並んだ要素の挿入 (sequential-store)

キーが整数値

キーが文字列

要素をランダムに検索 (random-find)

キーが整数値

キーが文字列

要素をシーケンシャルに検索 (sequential-find)

キーが整数値

キーが文字列

ランダム順での要素の削除 (random-erase)

キーが整数値

キーが文字列

シーケンシャルに要素を削除 (sequential-erase)

キーが整数値

キーが文字列

感想

使用例

問題点

パッチ

使用例

ncコマンドでのUNIX ドメインソケット使用方法