Kyoto.lisp Hackathon #1 に参加してきた。 KyotoでLisperが10人以上集ったのだけど、他の大きなイベントとぶつかっていたわりにはよく集ったのかも。

私は、前からやってみようと考えていたRuby 2.0(Trunk)のlazyをNendoで簡単に使えるようにする拡張にトライした。

解決したいこと

大きなテキストファイルを処理する際、メモリを節約するために逐次処理を意識した汚いコーディングに書き直すことがある。 これをなんとか、手続き型スタイルに書き直さずに関数型スタイルのまま、内部ではメモリ効率の良い処理をしてくれないか。 そんな都合の良い方法が見つかったのでトライしてみた。 遅延評価されたEmumerableを使えば思ったような効果が期待できると考えた。

Hackathon後、家に帰ってからコードを整理していくつかの勘違いも正すことができたので、ここに実験結果を書いておく。 後日、大袈裟な解決方法だと気がついてボツにしたコードも掲載し解説する予定。

実験対象のプログラム

約100MByteのテキストファイルを読み込んで加工・出力する、いわゆるフィルタプログラムで実験した。 書き捨てプログラムでは一番よく出てくるパターンだ。

効果

既存の仕組みだと、全ての入力行をプロセスにいったん蓄積するので、プロセスのピークメモリが大きい。

eagar.nndが、(f.readlines)した一番メモリを使う例。 generator.nndが、(f.lines)でジェネレータスタイルで書いた例。 lazy.nndが、Ruby 2.0のlazyを使った例。1.9.3ではLazyの機能が無いので自動的にフォールバックして遅延評価なしで動いている。

コード解説

* eager.nnd

example #1 eager filter — Gist 赤色の部分は入力ファイルの全ての行をメモリ中に保持する。 全ての行を “<” “>” で囲んだ中間データもメモリ中に保持するので、入力行の２倍のメモリを消費する。

* generator.nnd

example #2 filter with generator — Gist 青色の部分(入力ストリーム)をジェネレータにして、入力行を全て読み込まないようにする。 但し中間データは入力行数分のメモリを消費する。

* lazy.nnd

example #3 lazy filter — Gist 入力ストリームをlazy指定するとlazyが伝搬する。緑色の部分はlazyなvectorとなっている。 このプログラムでは、どんなに入力テキストデータが巨大になってもメモリは60MByte程度しか消費しない。 しかも、関数型プログラミングスタイル(高階関数のチェーンによる宣言的プログラミング)が維持できている。

今後の予定

実験がうまくいったので、lazy-vectorという関数はそのままリリースする予定。(Nendo 0.6.5) ただし、srfi-1のtakeなどの多くの関数がlazy-vectorをサポートしないとNendoの処理系全体での旨味が出し切れないので順次対応していく。Nendo 0.6.6以降かな…

学び

やっぱりブログ記事で文章化しないと、成果はまとまらないことを実感した。 今後はHackathon中もブログ(またはDokyumentoj)を書きながら頭を整理して作業しようと思う。