RustでMD5ハッシュを計算する

別に難しくはないけど、いざ使いたいという時に方法を忘れてしまっており、何度か調べ直しているのでメモに残しておく。

以下のようにrust-cryptoを使えば実現可能。

サンプルプロジェクトの準備:

$ rustc -V
rustc 1.9.0 (e4e8b6668 2016-05-18)

$ cargo new md5 --bin
$ cd md5
$ echo 'rust-crypto = "*"' >> Cargo.toml
$ vim src/main.rs  # 以下を参照

使用例:

extern crate crypto;

use crypto::digest::Digest;
use crypto::md5::Md5;

fn main() {
    let mut md5 = Md5::new();
    md5.input(b"hoge");
    println!("hoge: {}", md5.result_str());
}

実行結果:

$ cargo run
     Running `target/debug/hoge`
hoge: ea703e7aa1efda0064eaa507d9e8ab7e

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グラムコーパスを使わせて貰った
• 内部的には、以下の二つの処理が行われているので、そのそれぞれに要した時間を計測した:
  1. 入力を読み込み、メモリ上に二分木トライ(DAWG)の構築
  2. その二分木を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 [email protected]: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 [email protected]: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))

Emacsのファイル保存時に自動的にrustfmtが適用されるようにする

コードフォーマッタによる整形がファイル保存時に自動で行われるようにするための手順メモ。

まずはrustfmtをインストール:

# バージョン
$ rustc -V
rustc 1.5.0 (3d7cd77e4 2015-12-04)

# インストール
$ cargo install rustfmt
$ export PATH=$PATH:$HOME/.cargo/bin

# 動かしてみる
$ echo 'fn hoge () -> u32 { 1+1 }' | rustfmt
fn hoge() -> u32 {
    1 + 1
}

次はemacs-rustfmtの手順に従ってrustfmt.elã‚’Emacsにインストールする:

(require 'package)
(add-to-list 'package-archives
             '("melpa" . "https://melpa.org/packages/") t)
(package-initialize)

;; => M-x package-list-packages 
;; => `rustfmt`を選択 => `i` => `x`

最後は.emacsに以下の行を追加:

(add-hook 'rust-mode-hook #'rustfmt-enable-on-save)

完了。

現在時刻をUNIXタイムスタンプ形式で取得する

chronoというライブラリを使えば出来そう。

$ cargo new sample --bin
$ cd sample
$ echo -e '\n[dependencies]\nchrono="*"\n' >> Cargo.toml

main.rsを修正:

// src/main.rs
extern crate chrono;

use chrono::offset::local::Local;
use chrono::duration::Duration;

fn main() {
    // 現在時刻
    println!("Now: {}", Local::now().timestamp());

    // ついでに五分後を表示
    println!("After 5 minutes: {}", (Local::now() + Duration::minutes(5)).timestamp()); 
}

実行:

$ cargo run
Now: 1447247053
After 5 minutes: 1447247353

loglevelとseverityの使い分けメモ

自分用のログレベル関連の用語整理メモ。 loglevel、severity、severity level、をどう使い分けるか。 ここに書いてあることが一般的に正しい使い分けかどうかは不明。

severity は、その名の通りログメッセージの深刻度を表す。 その数値表現が severity level で、深刻度が高いほど値は小さくなる。

例:

severity level	severity
0	fatal
1	alert
2	warning
3	info
4	debug

loglevel は、実際に出力されるログメッセージを指定するための閾値であり、指定されたレベル以下のメッセージが出力されることになる（レベルが上がるほど出力範囲が増える)。

               | 4:debug   |
loglevel=3 --> | 3:info    |
   ↑           | 2:warning |
ここが出力対象   | 1:alert   |
   ↓           | 0:fatal   |

つまり severity は個々のメッセージに紐付くもので、loglevelはそれらの出力を担当するロガーに指定するもの。

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

--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を指定しなくても特に困ることはないので、とりあえずはその方向で回避する。

ç´ æ•°åˆ—ç”Ÿæˆ

素数列の実装方法を考えてみたのでメモ。

基本的にはエラトステネスの篩と同じようなことを行っているはずだが、一度に保持する篩の範囲が(おそらく)必要最小限となっている。
(一つの既知の素数につき、ハッシュテーブル内の一つの枠しか消費しない)

// file: prime.rs
//
// $ rustc --version
// rustc 1.0.0 (a59de37e9 2015-05-13) (built 2015-05-14)

use std::collections::HashMap;

pub struct Prime {
    curr: u64, // 現在の数値 (素数とは限らない)
    sieve: HashMap<u64, u64>, // 合成数 => 素数: サイズは`curr未満の素数の数`に常に等しい
}

impl Prime {
    pub fn is_prime(&mut self, n: u64) -> bool {
        match self.sieve.remove(&n) { // 一度探索した数はsieveから除去する(容量節約)
            None        => {self.mark_composite(2, n);               true},  // ç´ æ•°
            Some(prime) => {self.mark_composite(n/prime + 1, prime); false}, // 合成数
        }
    }
    fn mark_composite(&mut self, times: u64, prime: u64) {
        (times..).find(|i| !self.sieve.contains_key(&(i*prime)) ) // 未登録の合成数を探す
                 .and_then(|i| self.sieve.insert(i*prime, prime) );
    }
}

impl Iterator for Prime {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        let prime = (self.curr..).find(|n| self.is_prime(*n) ).unwrap(); // curr以降の最小の素数を検索
        self.curr = prime + 1;
        Some(prime)
    }
}

pub fn primes() -> Prime {
    Prime{curr: 2, sieve: HashMap::new()}
}

fn main() {
    use std::env;
    let n: usize = env::args().nth(1).unwrap().parse().unwrap();
    println!("{}-th prime: {}", n, primes().nth(n-1).unwrap());
}

実行例:

# CPU: Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz

# コンパイル
$ rustc -O hoge.rs

# 100万番の素数の検索
$ time ./hoge 1000000
1000000-th prime: 15485863

real    0m10.086s  # 約10秒掛かった
user    0m10.060s
sys 0m0.028s