yumのパッケージ(rpm)をダウンロードする方法
yumdownloaderというコマンドを使えば、インストールは行わずにパッケージのrpmだけを取得できる模様。
# yumdownloaderのインストール $ sudo yum install yum-utils # vimのrpmを取得 $ yumdownloader vim Loaded plugins: fastestmirror Loading mirror speeds from cached hostfile * base: ftp.jaist.ac.jp * extras: ftp.jaist.ac.jp * updates: ftp.jaist.ac.jp vim-enhanced-7.4.160-1.el7.x86_64.rpm # gccおよびその依存パッケージのrpmを取得 $ yumdownloader --resolve gcc Loaded plugins: fastestmirror Loading mirror speeds from cached hostfile * base: ftp.jaist.ac.jp * extras: ftp.jaist.ac.jp * updates: ftp.jaist.ac.jp --> Running transaction check ---> Package gcc.x86_64 0:4.8.3-9.el7 will be installed --> Processing Dependency: cpp = 4.8.3-9.el7 for package: gcc-4.8.3-9.el7.x86_64 --> Processing Dependency: glibc-devel >= 2.2.90-12 for package: gcc-4.8.3-9.el7.x86_64 --> Processing Dependency: libmpfr.so.4()(64bit) for package: gcc-4.8.3-9.el7.x86_64 --> Processing Dependency: libmpc.so.3()(64bit) for package: gcc-4.8.3-9.el7.x86_64 --> Running transaction check ---> Package cpp.x86_64 0:4.8.3-9.el7 will be installed ---> Package glibc-devel.x86_64 0:2.17-78.el7 will be installed --> Processing Dependency: glibc-headers = 2.17-78.el7 for package: glibc-devel-2.17-78.el7.x86_64 --> Processing Dependency: glibc-headers for package: glibc-devel-2.17-78.el7.x86_64 ---> Package libmpc.x86_64 0:1.0.1-3.el7 will be installed ---> Package mpfr.x86_64 0:3.1.1-4.el7 will be installed --> Running transaction check ---> Package glibc-headers.x86_64 0:2.17-78.el7 will be installed --> Processing Dependency: kernel-headers >= 2.2.1 for package: glibc-headers-2.17-78.el7.x86_64 --> Processing Dependency: kernel-headers for package: glibc-headers-2.17-78.el7.x86_64 --> Running transaction check ---> Package kernel-headers.x86_64 0:3.10.0-229.4.2.el7 will be installed --> Finished Dependency Resolution (1/7): glibc-headers-2.17-78.el7.x86_64.rpm | 656 kB 00:00:01 (2/7): libmpc-1.0.1-3.el7.x86_64.rpm | 51 kB 00:00:00 (3/7): mpfr-3.1.1-4.el7.x86_64.rpm | 203 kB 00:00:00 (4/7): kernel-headers-3.10.0-229.4.2.el7.x86_64.rpm | 2.3 MB 00:00:02 (5/7): cpp-4.8.3-9.el7.x86_64.rpm | 5.9 MB 00:00:04 (6/7): glibc-devel-2.17-78.el7.x86_64.rpm | 1.0 MB 00:00:05 (7/7): gcc-4.8.3-9.el7.x86_64.rpm $ ls -l *.rpm -rw-r--r-- 1 root root 6223284 Mar 14 07:43 cpp-4.8.3-9.el7.x86_64.rpm -rw-r--r-- 1 root root 16887940 Mar 14 07:49 gcc-4.8.3-9.el7.x86_64.rpm -rw-r--r-- 1 root root 1093332 Mar 14 07:50 glibc-devel-2.17-78.el7.x86_64.rpm -rw-r--r-- 1 root root 671684 Mar 14 07:50 glibc-headers-2.17-78.el7.x86_64.rpm -rw-r--r-- 1 root root 2392088 May 13 16:25 kernel-headers-3.10.0-229.4.2.el7.x86_64.rpm -rw-r--r-- 1 root root 51732 Jul 4 2014 libmpc-1.0.1-3.el7.x86_64.rpm -rw-r--r-- 1 root root 208316 Jul 4 2014 mpfr-3.1.1-4.el7.x86_64.rpm -rw-r--r-- 1 root root 1084932 Jul 4 2014 vim-enhanced-7.4.160-1.el7.x86_64.rpm
依存パッケージも含めてまとめてrpmを取得できるのは、ネットワークが繋がらない環境でインストールを行いたい場合等に便利そう。
優先度付きキュー系モジュールのベンチマーク
『Purely Functional Data Structures』(略:PFDS)で紹介されている優先度付きキュー(+ α)をいくつか実装してみたので、その性能測定メモ。
なおPFDSは(データ構造がヒープ特性を満たしているかどうかに関係なく)優先度付きキュー群をまとめてヒープと呼称しているようなので、以降ではそれに倣うことにする。
測定対象
測定対象モジュールは以下の通り:
- leftist_heaps:
- PFDSの3.1の実装がベース
- ヒープ特性とLeftist特性を満たす二分木
- ヒープ特性: 親ノードの値は、常に子ノードの値以下 (値が小さいほど高優先)
- Leftist特性: 左の子のランクは、常に右の子のランク以上
- ランクは「右の子を辿り続けて空ノードに至るまでのパスの長さ」
- 要素の挿入とヒープ同士のマージは
O(log n)
、最小値取り出しはO(1)
、の最悪コスト
- binomial_heaps:
- splay_heaps:
- PFDSの5.4の実装がベース
- 二分探索木
- 各操作実行時に辿った経路のみをバランス(スプレー)し、よくアクセスされる要素ほど木のルート近くに配置されるようにする
- 挿入/取り出しは
O(log n)
の償却コスト - マージは
O(n)
の最悪コスト
- pairing_heaps:
- gb_set_heaps:
- 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)
- 入力列のパターンは
昇順、降順、ランダム
の3つ
- 最小要素の取り出し:
- 全入力要素の挿入後に、ひたすら最小要素の取り出しを行い、一回辺りの取り出しに掛かった平均時間を計測する
- 入力数は
4^n (n = 2..7)
- 入力列のパターンは
昇順、降順、ランダム
の3つ
- 挿入と取り出しの混合:
- 二つのヒープのマージ:
- 要素数が
4^n (n = 2..5)
の二つのヒープのマージを千回繰り返し、一回の平均所要時間を計測する - 各ヒープの要素にはランダムな値が使用される
- 要素数が
測定結果
要素の挿入
計測内容(再掲):
- ひたすら要素を挿入して、一回辺りの挿入に掛かった平均時間を計測する
- 入力数は
4^n (n = 2..7)
- 入力列のパターンは
昇順、降順、ランダム
の3つ
入力が昇順の場合
%% [計測関数] %% 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)
- 入力列のパターンは
昇順、降順、ランダム
の3つ
入力が昇順の場合
%% [計測関数] %% 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のどちらか、といったところ
挿入と取り出しの混合
計測内容(再掲):
- 常時一定数の要素を保持しているヒープに対して、挿入と取り出しを繰り返す
- 今回は、具体的には以下のような条件で計測を行う
- ヒープの要素数は常に
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の3つが、ヒープ内の要素数に影響を受けずに
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の方が良い可能性もあるかもしれない。
ErlangでUNIXドメインソケットのクライアント接続を行なう簡単な方法
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
デバッグ用途等であれば使えなくはない、程度のメモ書き。
マップ系モジュールのベンチマーク
最近、かなり以前に作成したErlangのハッシュマップ的なライブラリ(hashtrie)のrebar対応等を行う機会があったので、ついでにErlangでマップ的な処理を行うために使えるデータ構造(モジュール)群の性能測定をしてみた。
対象モジュール
- dict
- gb_trees
- array ※ キーが非負の整数値の場合のみ
- hashtrie-v0.1.3
- splay_tree-v0.2.3
※ orddictは明らかに他に比べて遅いと思われたので対象外とした(別に含めても良かったかもしれない)
※ etsは破壊的な操作が含まれることにより、他のモジュールとの測定コードの共通化が面倒だったので対象外
なおR17.0から導入されたmapsの性能特徴に関してはQiitaの記事を参照のこと。
計測環境
計測方法
- ベンチマークコード: 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の場合は一万回ループ、といったように操作の適用回数の合計が百万回になるようにして計測を行った
- 最終的な計測値は、操作一回辺りの平均所要時間
- 入力要素の並び順は ランダム と 昇順 のニパターン
- 計測対象の操作は 挿入(store)、検索(find)、削除(erase) の三つ
- 全てのモジュールで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にするだけでコンスタントに数割程度(大きい時には数倍)は性能が向上していた
マルチプロセスで使用可能なロックフリーキュー
タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。
作成物
- ロックフリーなFIFOキュー
- 再入可能 かつ SIGKILLに対して安全*1
- C++
- 共有メモリ(mmap)を使用
- マルチプロセス(and マルチスレッド)間の通信に使用可能
- gcc(ver4.1以上)*2 かつ POSIX準拠環境*3でのみ使用可能
単機能な割に、内部では「まず(割合)汎用的な可変長ブロックメモリアロケータを作って、その上に固定長ブロックアロケータ、さらにその上にFIFOキューを実装」と地味に凝ったことをしている。
使用例
fork()と併用した例。
/** * 親子プロセスで共有するFIFOキューを作成し、子から親へメッセージを送信するサンプルプログラム * * ファイル名: msgque-sample.cc * コンパイル: g++ -o msgque-sample msgque-sample.cc */ #include <imque/queue.hh> // インクルードパスを通しておく #include <unistd.h> // fork, getpid #include <sys/types.h> #include <stdio.h> // sprintf #include <string.h> // strlen #include <iostream> #include <string> #define CHILD_COUNT 10 // 子プロセスの数 #define QUEUE_ENTRY_COUNT 32 // キューの最大要素数 #define SHM_SIZE 4096 // キューが使用可能な共有メモリのバイト数 int main(int argc, char** argv) { // 要素数と共有メモリサイズを指定してキューを作成 imque::Queue que(QUEUE_ENTRY_COUNT, SHM_SIZE); if(! que) { return 1; } for(int i=0; i < CHILD_COUNT; i++) { if(fork() == 0) { // 子プロセスの処理 char buf[1024]; sprintf(buf, "Hello: %d", getpid()); // enqueue que.enq(buf, strlen(buf)); return 0; } } // 親プロセスの処理 for(int i=0; i < CHILD_COUNT; i++) { std::string buf; // dequeue while(que.deq(buf) == false); // キューが空の間はビジーループ std::cout << "[receive] " << buf << std::endl; } return 0; }
実行結果:
$ ./msgque-sample [receive] Hello: 12736 [receive] Hello: 12737 [receive] Hello: 12738 [receive] Hello: 12740 [receive] Hello: 12739 [receive] Hello: 12742 [receive] Hello: 12744 [receive] Hello: 12743 [receive] Hello: 12745 [receive] Hello: 12741
気が向けば、内部で使用しているメモリアロケータのコードなども載せていくかもしれない。
ソート済みのリストに対する破壊的マージソートの改良
以前に載せたマージソート(をベースとしたもの)をSBCL(1.0.58)にコミットしてくれたPaul Khuongさんが、こんな記事を書いていて、なるほどなー、と思ったので、表題に関係する部分を参考にさせて貰って変更前後での比較を行ったメモ。
オリジナルのマージソート
まず、SBCL(1.0.58)のリストに対する破壊的マージソートの実装*1:
;; 二つのソート済みリストのマージ関数 (declaim (inline merge-lists*)) (defun merge-lists* (head list1 list2 test key &aux (tail head)) (declare (type cons head list1 list2) (type function test key) (optimize speed)) (macrolet ((merge-one (l1 l2) `(progn (setf (cdr tail) ,l1 tail ,l1) (let ((rest (cdr ,l1))) (cond (rest (setf ,l1 rest)) (t (setf (cdr ,l1) ,l2) (return (cdr head)))))))) (loop (if (funcall test (funcall key (car list2)) ; this way, equivalent (funcall key (car list1))) ; values are first popped (merge-one list2 list1) ; from list1 (merge-one list1 list2))))) ;; 実行 (merge-lists* '(:head) '(1 3 5) '(2 4 6) #'< #'identity)) => (1 2 3 4 5 6)
;; リストのマージソート関数 (declaim (inline stable-sort-list)) (defun stable-sort-list (list test key &aux (head (cons :head list))) (declare (type list list) (type function test key) (dynamic-extent head)) (labels ((recur (list size) (declare (optimize speed) (type cons list) (type (and fixnum unsigned-byte) size)) (if (= 1 size) (values list (shiftf (cdr list) nil)) (let ((half (ash size -1))) (multiple-value-bind (list1 rest) (recur list half) (multiple-value-bind (list2 rest) (recur rest (- size half)) (values (merge-lists* head list1 list2 test key) rest))))))) (when list (values (recur list (length list)))))) ;; 実行 (stable-sort-list '(8 73 2 40 0 3) #'< #'identity) => (0 2 3 8 40 73)
何種類かデータを用意して実行時間を計測:
;;; 計測用データ ;; 1] 400万要素のソート済みリスト (defparameter *sorted-list* (loop FOR i FROM 0 BELOW 4000000 COLLECT i)) ;; 2] 400万要素の逆順ソート済みリスト (defparameter *reverse-sorted-list* (reverse *sorted-list*)) ;; 3] 400万要素のほぼソート済みリスト1 ※ 千要素に一つがランダムな値 (defparameter *nearly-sorted-list1* (loop FOR i FROM 0 BELOW 4000000 COLLECT (if (zerop (random 1000)) (random 4000000) i))) ;; 4] 400万要素のほぼソート済みリスト2 ※ 複数のソート済みリストが連結 (defparameter *nearly-sorted-list2* (loop REPEAT 4 APPEND (loop FOR i FROM 0 BELOW 1000000 COLLECT i))) ;; 5] 400万要素のランダムなリスト (defparameter *random-list* (loop REPEAT 4000000 COLLECT (random most-positive-fixnum))) ;;; 計測用マクロ (defmacro sort-time (sort-fn-name list) `(let ((list~ (copy-list ,list))) (declare (optimize (speed 3) (safety 0))) (time (progn (,sort-fn-name list~ #'< #'identity) t)))) ;;; 計測 ;; 1] ソート済みリスト (sort-time stable-sort-list *sorted-list*) Evaluation took: 0.254 seconds of real time ; 0.254秒 0.252017 seconds of total run time (0.248016 user, 0.004001 system) 99.21% CPU 508,247,464 processor cycles 0 bytes consed => T ;; 2] 逆順ソート済みリスト (sort-time stable-sort-list *reverse-sorted-list*) Evaluation took: 0.235 seconds of real time ; 0.235秒 0.232015 seconds of total run time (0.232015 user, 0.000000 system) 98.72% CPU 468,869,834 processor cycles 0 bytes consed => T ;; 3] ほぼソート済みリスト1 ※ 千要素に一つがランダムな値 (sort-time stable-sort-list *nearly-sorted-list1*) Evaluation took: 0.348 seconds of real time ; 0.348秒 0.348023 seconds of total run time (0.344022 user, 0.004001 system) 100.00% CPU 694,968,622 processor cycles 0 bytes consed => T ;; 4] ほぼソート済みリスト2 ※ 複数のソート済みリストが連結 (sort-time stable-sort-list *nearly-sorted-list2*) Evaluation took: 0.271 seconds of real time ; 0.271秒 0.272017 seconds of total run time (0.272017 user, 0.000000 system) 100.37% CPU 538,952,732 processor cycles 0 bytes consed => T ;; 5] ランダムリスト (sort-time stable-sort-list *random-list*) Evaluation took: 2.171 seconds of real time ; 2.171秒 2.168135 seconds of total run time (2.160135 user, 0.008000 system) 99.86% CPU 4,332,215,938 processor cycles 0 bytes consed => T
ソート済みのリストに対する改良を加えたマージソート
変更後のマージソート関数: ※ 変更内容はコメントを参照
;; 改良版マージソート関数 ;; - fast-merge-lists*関数が追加されたこと以外は、もともとの関数とほとんど同様 ;; - fast-merge-lists*関数は要素の範囲が重複しない二つのリストをO(1)でマージ可能 (declaim (inline stable-sort-list2)) (defun stable-sort-list2 (list test key &aux (head (cons :head list))) (declare (type list list) (type function test key) (dynamic-extent head)) ;; マージ対象の二つのリスト内の片方が、もう片方に完全に先行している場合は、 ;; 各要素の比較などは省略して、末尾のcdrの更新のみを行う。 (labels ((fast-merge-lists* (try-fast-merge? list1 tail1 list2 tail2 rest) (when try-fast-merge? ;; list1がlist2に完全に先行: (list1 .. tail1) <= (list2 .. tail2) (cond ((not (funcall test (funcall key (car list2)) (funcall key (car tail1)))) (setf (cdr tail1) list2) (return-from fast-merge-lists* (values list1 tail2 rest))) ;; list2がlist1に完全に先行: (list2 .. tail2) < (list1 .. tail1) ((funcall test (funcall key (car tail2)) (funcall key (car list1))) (setf (cdr tail2) list1) (return-from fast-merge-lists* (values list2 tail1 rest))))) ;; その他: 通常のマージ (values (merge-lists* head list1 list2 test key) (if (null (cdr tail1)) tail1 tail2) rest)) ;; トップダウンマージリスト関数: リストの末尾を管理するようになったのとfast-merge-lists*関数を使うようになったこと以外は変更なし (recur (list size) (declare (optimize speed) (type cons list) (type (and fixnum unsigned-byte) size)) (if (= 1 size) (values list list (shiftf (cdr list) nil)) (let ((half (ash size -1))) (multiple-value-bind (list1 tail1 rest) (recur list half) (multiple-value-bind (list2 tail2 rest) (recur rest (- size half)) (fast-merge-lists* (>= size 8) ; オーバヘッドを少なくするために、一定サイズ以上のリストに対してのみ適用を試みる list1 tail1 list2 tail2 rest))))))) (when list (values (recur list (length list)))))) ;; 実行 (stable-sort-list2 '(8 73 2 40 0 3) #'< #'identity) => (0 2 3 8 40 73)
処理時間計測:
;; 1] ソート済みリスト (sort-time stable-sort-list2 *sorted-list*) Evaluation took: 0.086 seconds of real time ; 0.086秒 (変更前: 0.254秒) 0.088005 seconds of total run time (0.088005 user, 0.000000 system) 102.33% CPU 171,845,432 processor cycles 0 bytes consed => T ;; 2] 逆順ソート済みリスト (sort-time stable-sort-list2 *reverse-sorted-list*) Evaluation took: 0.087 seconds of real time ; 0.0.87秒 (変更前: 0.235秒) 0.088006 seconds of total run time (0.088006 user, 0.000000 system) 101.15% CPU 173,196,084 processor cycles 0 bytes consed => T ;; 3] ほぼソート済みリスト1 ※ 千要素に一つがランダムな値 (sort-time stable-sort-list2 *nearly-sorted-list1*) Evaluation took: 0.293 seconds of real time ; 0.293秒 (変更前: 0.348秒) 0.292019 seconds of total run time (0.292019 user, 0.000000 system) 99.66% CPU 585,393,530 processor cycles 0 bytes consed => T ;; 4] ほぼソート済みリスト2 ※ 複数のソート済みリストが連結 (sort-time stable-sort-list2 *nearly-sorted-list2*) Evaluation took: 0.122 seconds of real time ; 0.122秒 (変更前: 0.271秒) 0.120007 seconds of total run time (0.116007 user, 0.004000 system) 98.36% CPU 242,403,024 processor cycles 0 bytes consed => T ;; 5] ランダムリスト (sort-time stable-sort-list2 *random-list*) Evaluation took: 2.193 seconds of real time ; 2.193秒 (変更前: 2.171秒) 2.192138 seconds of total run time (2.164136 user, 0.028002 system) 99.95% CPU 4,376,336,316 processor cycles 0 bytes consed => T
完全にランダムなリストに対するソートは心なしか改良版の方が(ごく若干)遅くなっているように思うが、入力リストにソート済みの部分が多ければ多いほど、確実に改良版の方が速くなっている。
確かに、二つのリストをマージする場合、それぞれの領域が独立しているなら、片方の先頭要素ともう片方の末尾要素を比較するだけで、リスト全体を完全に順序づけ可能なんだけど、自分が実装方法を考えている時には、そのことに思い至らなかった。
なるほどなー。
Lock-Free Queue
compare-and-swap操作を用いたロックフリーなキューの実装。
SBCLでのみ動作*1。
(defpackage lock-free-queue (:use :common-lisp) (:export queue make enq deq empty-p element-count to-list)) (in-package :lock-free-queue) ;; compare-and-swap: 成功した場合はTを、失敗した場合はNILを返す (defmacro compare-and-swap (place old new) `(eq (sb-ext:compare-and-swap ,place ,old ,new) ,old)) ;; キュー構造体 (defstruct queue (head nil :type list) (tail nil :type list)) ;; リストへ変換/空判定/要素数取得 (defun to-list (que) (copy-seq (cdr (queue-head que)))) (defun empty-p (que) (endp (cdr (queue-head que)))) (defun element-count (que) (length (cdr (queue-head que)))) (defmethod print-object ((o queue) stream) (print-unreadable-object (o stream :type t) (format stream "~s ~s" :count (element-count o)))) ;; キューを生成 (defun make (&optional initial-contents) (let ((contents (cons :initial-head initial-contents))) (make-queue :head contents :tail (last contents)))) ;; キューの末尾に要素を追加する ;; => queue (defun enq (x que) (loop WITH new-elem = (list x) FOR tail = (queue-tail que) DO (cond ((cdr tail) (compare-and-swap (queue-tail que) tail (cdr tail))) ; tailの位置を調整 ((compare-and-swap (cdr tail) nil new-elem) (return que))))) ; 追加成功 ;; キューの先頭から要素を取り出す ;; => (or (values 先頭要素 T) ; キューに要素がある場合 ;; (values NIL NIL)) ; キューが空の場合 (defun deq (que) (let* ((head (queue-head que)) (next (cdr head))) (cond ((null next) (values nil nil)) ; 空 ((compare-and-swap (queue-head que) head next) (values (car next) t)) ; 取得成功 (t (deq que))))) ; 他スレッドと競合(リトライ)
実行例:
;; シングルスレッドでの例 (defparameter *que* (lock-free-queue:make)) => *QUE* (lock-free-queue:enq 1 *que*) => #<LOCK-FREE-QUEUE:QUEUE :COUNT 1> (lock-free-queue:enq 2 *que*) => #<LOCK-FREE-QUEUE:QUEUE :COUNT 2> (lock-free-queue:to-list *que*) => (1 2) (lock-free-queue:deq *que*) => 1 T (lock-free-queue:deq *que*) => 2 T (lock-free-queue:deq *que*) => NIL NIL ;; マルチスレッドでの例 (let ((data (loop FOR i FROM 0 BELOW 10000 COLLECT i)) (que (lock-free-queue:make)) (thread-num 500)) ;; enqueuers (loop REPEAT thread-num DO (sb-thread:make-thread (lambda () (dolist (e data) (lock-free-queue:enq e que))))) ;; dequeuer (list (length (loop REPEAT (* thread-num (length data)) COLLECT (loop (multiple-value-bind (val ok?) (lock-free-queue:deq que) (when ok? (return val)))))) que)) => 5000000 #<LOCK-FREE-QUEUE:QUEUE :COUNT 0>
*1:sb-ext:compare-and-swapを置き換えれば他の処理系でも動作可能