RustとSBCLでのDAWG構築性能の比較メモ
Rustの勉強を兼ねて、cl-dawgというDAWGのCommon Lisp実装を移植して、rust-dawgというライブラリを作ってみた。
(DAWGは末尾部分を共有可能にしたトライの亜種。上記ライブラリでは、そのトライ木をDoubleArray形式で表現している。DAWGやDoubleArrayの構築方法自体に関しては、過去に何度か記事を書いているのでここでは省略する)
両者の性能比較を軽く行ったので、ここにその結果メモを残しておく。
環境
- CPU: Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz (論理四コア)
- メモリ: 8GB
- OS: Ubuntu-15.04 (64bit)
- rust-dawg: v0.1.0
- cl-dawg: v0.3.1
- Rust: rustc-1.5.0
- Common Lisp: SBCL-1.2.14
測定
内容
- DAWGインデックスファイルの構築性能を比較
- 実行時間とメモリ消費量
- 入力は4500万個程度の文字Nグラム
- http://s-yata.jp/corpus/nwc2010/ngrams/ にある出現頻度が1000以上のNグラムコーパスを使わせて貰った
- 内部的には、以下の二つの処理が行われているので、そのそれぞれに要した時間を計測した:
- 入力を読み込み、メモリ上に二分木トライ(DAWG)の構築
- その二分木をDoubleArray形式に変換しつつ、ファイルに書き出し
- なお上記の
1
に関してはrust-dawgとcl-dawgでほぼ同様のコードとなっているが、2
に関してはrust-dawgの実装中に、実行速度的により効率的(と思われる)な方法を思いついて実装してしまったのでrust版の方が有利な計測となってしまっている可能性が高い- メモリ消費量には影響がない
準備とコマンド実行
入力ファイルの準備
# Nグラムコーパスの取得 $ wget -xnH -i http://dist.s-yata.jp/corpus/nwc2010/ngrams/char/over99/filelist $ xz -d corpus/nwc2010/ngrams/char/over999/*/*.xz $ head -5 corpus/nwc2010/ngrams/char/over999/2gms/2gm-0000 " " 123067 " # 2867 " $ 1047 " % 2055 " & 3128 # 文字列部分のみを抜き出してソートする $ cut -f 1 corpus/nwc2010/ngrams/char/over999/*gms/* | sed -e 's/ //g' > words.tmp $ LC_ALL=c sort words.tmp -o words $ wc -l words 44280717 words # 約4500万ワード $ du -h words 652M words
rust-dawgのビルドと実行
# ビルド $ git clone git@github.com:sile/rust-dawg.git $ cd rust-dawg $ patch -p1 < rust-dawg.patch # 計測コードを埋め込むためのパッチを当てる $ cargo build --release # 実行 $ /usr/bin/time -v target/release/dawg_build rust-dawg.idx < words Building binary-tree trie ... done: elapsed=49999 ms Building double-array trie ... done: elapsed=11402 ms DONE Command being timed: "target/release/dawg_build rust-dawg.idx" User time (seconds): 60.90 System time (seconds): 0.53 Percent of CPU this job got: 100% Elapsed (wall clock) time (h:mm:ss or m:ss): 1:01.40 Average shared text size (kbytes): 0 Average unshared data size (kbytes): 0 Average stack size (kbytes): 0 Average total size (kbytes): 0 Maximum resident set size (kbytes): 1921288 Average resident set size (kbytes): 0 Major (requiring I/O) page faults: 0 Minor (reclaiming a frame) page faults: 3195 Voluntary context switches: 1 Involuntary context switches: 84 Swaps: 0 File system inputs: 0 File system outputs: 409824 Socket messages sent: 0 Socket messages received: 0 Signals delivered: 0 Page size (bytes): 4096 Exit status: 0 $ du -h rust-dawg.idx 201M rust-dawg.idx
cl-dawgのビルドと実行
# ビルド $ git clone git@github.com:sile/cl-dawg.git $ cd cl-dawg $ patch -p1 < cl-dawg.patch # 計測コードを埋め込むためのパッチを当てる $ sbcl --noinform --dynamic-space-size 7500 ;; dawgパッケージをビルド * (require :asdf) * (setf asdf:*central-registry* (list (directory ".") (directory "lib/dict-0.2.0/"))) * (asdf:load-system :dict-0.2.0) * (asdf:load-system :dawg) ;; 実行可能ファイルを作成 * (defun main () (let ((input-file (second sb-ext:*posix-argv*)) (output-file (third sb-ext:*posix-argv*))) (time (dawg:build :input input-file :output output-file)))) * (sb-ext:save-lisp-and-die "dawg-build" :toplevel #'main :executable 't :save-runtime-options t) # 実行 $ /usr/bin/time -v ./dawg-build words cl-dawg.idx :BUILD-BINARY-TREE-TRIE Evaluation took: 37.298 seconds of real time 37.304000 seconds of total run time (35.300000 user, 2.004000 system) [ Run times consist of 12.180 seconds GC time, and 25.124 seconds non-GC time. ] 100.02% CPU 96,735,665,025 processor cycles 12 page faults 11,938,296,176 bytes consed :BUILD-DOUBLE-ARRAY-TRIE Evaluation took: 33.487 seconds of real time 33.496000 seconds of total run time (32.436000 user, 1.060000 system) [ Run times consist of 6.484 seconds GC time, and 27.012 seconds non-GC time. ] 100.03% CPU 86,850,782,635 processor cycles 2 page faults 10,786,507,072 bytes consed Command being timed: "./dawg-build words cl-dawg.idx" User time (seconds): 67.74 System time (seconds): 3.09 Percent of CPU this job got: 100% Elapsed (wall clock) time (h:mm:ss or m:ss): 1:10.82 Average shared text size (kbytes): 0 Average unshared data size (kbytes): 0 Average stack size (kbytes): 0 Average total size (kbytes): 0 Maximum resident set size (kbytes): 4622404 Average resident set size (kbytes): 0 Major (requiring I/O) page faults: 25 Minor (reclaiming a frame) page faults: 1190638 Voluntary context switches: 30 Involuntary context switches: 595 Swaps: 0 File system inputs: 4896 File system outputs: 820952 Socket messages sent: 0 Socket messages received: 0 Signals delivered: 0 Page size (bytes): 4096 Exit status: 0 $ du -h cl-dawg.idx 201M cl-dawg.idx
結果(まとめ)
上の結果を表形式にまとめたもの。
所要時間
二分木構築 | DoubleArray構築 | 合計 | |
---|---|---|---|
rust-dawg | 49.99s | 11.40s | 61.40s |
cl-dawg | 37.30s (非GC: 25.12s) | 33.49s (非GC: 27.01s) | 70.80s (非GC: 52.13s) |
二分木構築に要した時間はcl-dawgの方が、DoubleArray構築に要した時間はrust-dawgの方が、短くなっている。
後者の影響が大きく合計時間もrust-dawgの方が短くなっているが、上で書いたようにDoubleArray構築部分はRust版の方が有利な実装になっているので、
その辺りの条件を合わせれば、おそらく合計でもcl版の方が速い結果となると思う。
また、もしGCに要した時間を除外したとすればcl-dawg(SBCL)の方がだいぶ良好な結果となっている。
メモリ消費量
最大メモリ消費量 | |
---|---|
rust-dawg | 1.921GB |
cl-dawg | 4.622GB |
メモリ消費量に関しては、(GC無し言語とGC有り言語の比較なので当然と言えば当然だが)Rust版の方が半分以下の消費量となっている。
感想
rust-dawgのメモリ消費量に関しては期待通り。
二分木構築部分の処理時間は、cl-dawg(SBCL)の「非GC部分の時間+α」くらいに収まってくれるかと予想していたが、意外と振るわない結果となった。
「SBCLはかなり高速な処理系 and CL版はかなり最適化されている and Rust初心者」とcl-dawg版に有利な条件も多々あるけど、
Rustは「静的型付け and GC不要」な分だけ実行時のコストを安く出来ても良いはずなのに、とは思う。
(ただし、GC不要と言いつつrust-dawg内では(GCの一種と見做せなくもない)RCモジュールは多用されている)
特に直近でやる予定はないけど、気が向いたら何が原因で速度差が生じているのかの特定を行ってみたいかもしれない。
(ex. RCを生ポインタに置き換えたらどうなるか、とか、Optionをやめて番兵値でundefinedを表現してみる、とか、内部で多用しているハッシュマップの実装を変えたらどうなるか、とか、そもそもコンパイラの最適化が不十分、とか)
測定用に当てたパッチ
rust-dawg.patch
diff --git a/Cargo.toml b/Cargo.toml index a1daa96..f829e37 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -7,2 +7,3 @@ [dependencies] bit-vec = "*" byteorder = "*" +time = "*" diff --git a/src/bin/dawg_build.rs b/src/bin/dawg_build.rs index 7677951..880fd5f 100644 --- a/src/bin/dawg_build.rs +++ b/src/bin/dawg_build.rs @@ -4,6 +4,7 @@ // see the LICENSE file at the top-level directory. extern crate dawg; +extern crate time; use std::env; use std::process; @@ -12,6 +13,11 @@ use std::io::BufRead; use dawg::binary_tree::Builder as BinaryTreeBuilder; use dawg::double_array::Builder as DoubleArrayBuilder; +fn now_ms() -> u64 { + let t = time::now().to_timespec(); + (t.sec as u64 * 1000 + t.nsec as u64 / 1000 / 1000) +} + fn main() { let args: Vec<_> = env::args().collect(); if args.len() != 2 { @@ -21,17 +27,25 @@ fn main() { let stdin = io::stdin(); let output_file = &args[1]; + + print!("Building binary-tree trie ... "); + let start = now_ms(); let trie = BinaryTreeBuilder::new() .build(stdin.lock().lines()) .unwrap_or_else(|e| { println!("[ERROR] Can't build DAWG: reason={}", e); process::exit(1); }); + println!("done: elapsed={} ms", now_ms() - start); + + print!("Building double-array trie ... "); + let start = now_ms(); let trie = DoubleArrayBuilder::new().build(trie); if let Err(e) = trie.save(output_file) { println!("[ERROR] Can't save dawg index: path={}, reason={}", output_file, e); process::exit(1); } + println!("done: elapsed={} ms", now_ms() - start); println!("DONE"); }
cl-dawg.patch
diff --git a/dawg.lisp b/dawg.lisp index aa5ea40..095dcbd 100644 --- a/dawg.lisp +++ b/dawg.lisp @@ -61,11 +61,14 @@ (declare ((or string pathname list) input) ((or string pathname) output) ((member :native :little :big) byte-order)) - (let ((trie (if (listp input) + (let ((trie (time (progn (print :build-binary-tree-trie) (if (listp input) (dawg.bintrie-builder:build-from-list input :show-progress show-progress) (dawg.bintrie-builder:build-from-file input :show-progress show-progress)))) + )) + (time (progn (print :build-double-array-trie) (dawg.double-array-builder:build-from-bintrie trie :output-file output :byte-order byte-order :show-progress show-progress)) + )) t) (defun load (index-path &key (byte-order :native))