#そのコード、ベンチマークにいいかも。公開できるなら RT: @quasicrane gauche util.match を使ったプログラムのコンパイルがあまりに遅いのでマクロ展開してみたら凄まじい行数に展開されている 少しエレガントさを減らしてあんまり巨大にならないように最適化しないと駄目か
#shiro さん、拾っていただき多謝です。ちょっと整理してgithubにのせます。わたしの使い方が間違ってなければいいのですが。gauche vm を secd マシン風に書きたくて書いていたコードです。
#@quasicrane util.matchは重複したテストをなるべく避けるコードを出すのですが、案外その重複チェックがパターンサイズに対してO(n^2)だったりしないかな、と疑ってます。
#しかしmatchのコード自体がmatchによって展開された後のコードなので該当箇所を探すのが面倒…
#もし上の予想が当たってて、チェックをhashtableか何かで置き換えられれば劇的に速くなるんではなかろうか、というのが希望
#関数inかな、重複チェックしてるのは。結構クレバーなことをやってるのでそう単純には置き換えられないか…
#http://bit.ly/9cwCIU に載せました secd という手続きの match が問題の部分です vector のマッチとキーワードとのマッチが入っています #あれ、パターン自体ha
#はたいしたことないなあ。
#ああ、説明を書いていませんでしたが (secd '(+ 3 4)) というようにs-式を渡すとコンパイルしてパターンマッチしながら実行するのです コメントアウトしている部分はまだ gauche vm が分かっていないので書けていない部分です
#でも今のコードでも展開が遅いんですよね?
#あ、ちょっとまてよ。matchの展開自体が遅いのか、展開後のコードが走るのが遅いのか、自分は前者だと思ってたんだけどもしかして後者?
#前者の、match の展開自体が遅い、です。
#了解。
#ふむ。うちの環境だと展開だけで1.3秒かかる。確かに遅い。
#コメントアウトしている :BNGT, :CLOSURE, :PRE-CALL を加えると劇的に遅くなり、手元では２０秒以上掛かりました パターンマッチ自体はご指摘どおり単純ですし、展開系もキーワードとの比較になっているようなのですが
#なりますね。O(n^2)どころかどっかでexponentialになってるっぽいなあ
#節を三つ加えただけでgenの呼ばれる回数が28倍になってる。
#@quasicrane わかりました。このパッチを試してみてください。
#--- libsrc/util/match.scm (revision 7148)
+++ libsrc/util/match.scm (working copy)
@@ -670,12 +670,17 @@
(else (loop (cdr b) (cons (car b) new-b) e))))))
(define (gen x sf plist erract length>= eta)
+
+ (define (gen-rec plist memo)
+
(if (null? plist)
(erract x)
(let* ((v '())
(val (lambda (x) (cdr (assq x v))))
(fail (lambda (sf)
- (gen x sf (cdr plist) erract length>= eta)))
+ (or (hash-table-get memo (cdr plist) #f)
+ (rlet1 code (gen-rec (cdr plist) memo)
+ (hash-table-put! memo (cdr plist) code)))))
(success (lambda (sf)
(set-car! (cddddr (car plist)) #t)
(let* ((code (cadr (car plist)))
@@ -913,6 +918,8 @@
(newline)
(error #f "THIS NEVER HAPPENS")))))))
+ (gen-rec plist (make-hash-table 'eq?)))
+
(define (emit tst sf kf ks)
(cond
((in tst sf) (ks sf))#(パッチの大きさを減らすためインデントをわざと揃えていません)
#パッチありがとうございます、今から試します。
#パッチ確認しました。マクロ展開が１秒程度に相当速くなりました、コンパイルは数秒掛かりますが展開系が大きいのでこれは問題ないと思います。素早い対応ありがとうございました。これでsecdマシンを作れそうです
#むう、まだ1秒かかりますか。もうちょい詰められそうだな。
#exponentialになってるところがもう一ヶ所あった。
#なるほど、展開は速くなったけどコンパイルに時間がかかるのは、結局ツリーの大きさが変わらないからか。(genでメモワイズしたのでgenが返すやつはDAGになってるけど、Gaucheのコンパイラはソースに部分共有があることは想定してない)
#失敗時に樹状に分岐するんだけど、そのほとんどは同じ処理をしてるはず。lambdaでまとめられればずっとコンパクトになるはずなんだが…
#@quasicrane とりあえずquasicraneさんのコードで、ベクタ中で rest ... を使ってるところを _ ... に置き換えてみてください。restをその後で使ってなくても、util.matchは律儀にベクタの残り要素をリストにかき集めてrestに渡すコードを生成します。
#_ ... にすれば残り要素を無視して良いことがmatchにもわかるので、劇的に速くなります。
#_ ... 試してみてます。手元で、キーワードをあきらめ普通のシンボルにすると
#ああ切れてしまいました。キーワードをあきらめて普通のシンボルにするとなぜかコンパイルも速いようです。match.scm ちゃんと読めていないのですがキーワードとシンボルで少し扱いが違うのでしょうか。
#はて、キーワードは単なるリテラル比較になるのでquoteしたシンボルと変わらないと思うのですが。
#変わらないはずですか。すみませんもうちょっと確認してからレポートしてみます。（キーワードを使っている理由はほとんど何も無いです。CLで使っていたというだけ）
#うーむ、gitを使い慣れるとsubversionでのブランチ管理はなにかと面倒だなあ。
#最近、GaucheやKahuaをいじるのは、もっぱらgit svnで取って来たリポジトリです。手許でいろいろやれてメインストリームとのマージも簡単で便利です。
Gauche > Archives > 2010/05/30