SWIG を使ったときの性能(メモ)
Perl, Python, Ruby とバインディングを用意してみたものの,C++ と比べて驚くほど遅くなってしまうことに気づきました.原因としては,メソッドの呼び出しにおけるオブジェクトの相互変換が有力です.
辞書の構築時間や検索時間を計測した結果を表にしてみました.単位は秒です.
- キー集合
- 日本語 Wikipedia のタイトル一覧です.(追記 2011-05-07)検索は入力と同じ順番(ほぼ辞書順)でおこないました.
- I/O
- ファイルからキーを読み込んで配列にするのに要した時間です.
- 連想配列
- Agent
- marisa::Agent を介するインタフェースと介さないインタフェースを用意して比較しました.
内容 | Ruby | Python | Perl | C++ |
---|---|---|---|---|
I/O | 1.915 | 0.898 | 1.527 | 1.110 |
連想配列の構築 | 2.424 | 1.035 | 1.975 | 1.727 |
連想配列の参照 | 1.210 | 0.591 | 0.674 | 0.470 |
Keyset の構築 | 1.261 | 2.222 | 1.059 | 0.104 |
Trie の構築 | 3.024 | 3.031 | 3.046 | 3.130 |
Agent ありの Lookup | 4.586 | 6.146 | 5.359 | 1.957 |
Agent なしの Lookup | 3.391 | 4.990 | 3.387 | - |
Agent ありの Reverse Lookup | 5.263 | 6.579 | 4.814 | 1.981 |
Agent なしの Reverse Lookup | 4.631 | 5.811 | 3.832 | - |
Common Prefix Search | 7.510 | 12.858 | 9.923 | 2.031 |
Preditive Search | 9.785 | 15.449 | 13.412 | 4.495 |
当然のことながら,速度面の比較では,組み込みの連想配列には遠く及びません.もっとも差の小さい Ruby で約 3 倍,もっとも差の大きい Python で 10 倍近くの検索時間になっています.辞書引きがボトルネックになるようなアプリケーションには向きません.
その代わり,メモリ消費は控えめに見積もっても 1/5 以下になります.大規模な辞書をオンメモリで扱いたいときには有力な候補になると思います.
(追記 2011-05-07)Keyset の構築は Key を一つずつ登録するため,メソッドの呼び出しにかかるコストが目立っています.一方,一度の呼び出しで片付く Trie の構築については,C++ とそれ以外で有意な差はありません.
(追記 2011-05-07)肝心の検索時間については,少し残念な結果となっています.Lookup で 1.5 倍以上,Reverse Lookup で 2 倍以上(Agent なしとの比較)というのも十分に痛いところですが,繰り返しによって検索を進める Common Prefix Search については,軽く 3 倍以上と差が顕著になっています.Predictive Search については,Common Prefix Search と比べた場合,元から重いこともあり, 差が小さくなっています.
(追記 2011-05-07)簡単にまとめるとすれば,SWIG を使う場合,粒度が小さいとオーバーヘッドが大きくなって残念な結果になってしまうので,できれば大きめの粒度にしましょうというところでしょうか.また,メソッドの呼び出し・返り値・引数の数によってオーバーヘッドが増えるので,インタフェースが存外に重要になります.後,Perl については,返り値に自前の型を使うと極端に遅くなることがありました.これは落とし穴かもしれません.
(追記 2011-05-11)SWIG のバージョンを 1.3.40 から 2.0.3 に変更しても,処理時間にはほとんど変化がありませんでした.
# 今回の実験に使った実装については,数日中にアップロードする予定です.
(追記 2011-05-18)当初の予定より遅くなってしまいましたが,実装を Subversion のリポジトリにコミットしました.bindings/ の中にあります.
- Project URL: http://code.google.com/p/marisa-trie/