[ruby-dev:545] Re: optimize (Re: Assigne to special variable)

えぐち です。

----------
> 件名 : [ruby-dev:537] Re: optimize (Re: Assigne to special variable)
> 
> まつもと ゆきひろです
> 
> In message "[ruby-dev:536] optimize (Re: Assigne to special variable)"
>     on 97/09/26, "EGUCHI Osamu" <[e-mail]> writes:
> 
> |えぐち です。
> 
> うーん，えぐちさんってすごい人かも．

とーりすがりのものです。

> |elisp のバイトコードコンパイラなんか、結構すごい最適化を
> |かけますよね、elisp に限らず common-lisp 以降の lisp の
> |実装は特にチューニングに関しては激しいものがあります。
> 
> elispの最適化は調べてません．そんな最適化してました？
> Lispに関しては古典的な知識しか無いんです．

私も Lisp でがしがし書ける人でないのであれですが、
COMMON LISP THE LANGAGE (2nd Ed.)なんかを読むと
言語設計の段階で強烈に最適化を意識して舞うよね。

まつもとさんって、 hogehoge_p() とかするから lisper かと
思ってました 。で ruby は CLOS の影響かと、、

> |と言うことで、いわゆるピープホールオプティマイズと
> |ランタイムエンジン部分のチューニングが ruby では効果的では？
> 
> 全てがメソッドで組込みの演算がほとんどないことと，メソッドが
> 自由に再定義されうる(副作用を持つものに差し替えられているか
> も)ので，ピープホールオプティマイズは望み薄です．評価順序の
> 差し替えや部分式の括り出しすらできないので．
> 
> やっぱり高速化には実行系に手を入れるしかないでしょうね．

 obj = obj + m  --> obj += m

もピープホールの一種じゃないかな、これだけでもエバるときに
若干手数が減ると思うです？
ただ、 
	obj = m + obj --> obj += m
の様な「交換則」はレシーバの変更なのでヤバヤバですネ。

また、メソッドのテールリカージョンは可能だとおもいます。

> |>   * メソッドキャッシュの改善(eval.c)
> |
> |中規模なアプリケーションでなら、0x200 エントリのメソッドキャッシュ
> |でも（gcov で見ると）かなりヒットしているように思えます。
> |むしろエントリーを増やすより、再定義などでクリアされるない様に
> |したいところですが、メソッドとオブジェクトの結合が動的なので
> |ほとんど不可能に近いですね。
> 
> 同じ場所で呼ばれるメソッドは大抵同じなので，構文木そのものに
> キャッシュとして埋め込むという手法が昔の Smalltalk の実装に
> ありました．ただ，これも結局はキャッシュの有効判定のコストな
> どがあるので，どれだけ効果が上がるかは自信がないです．昔，
> rubyがまだ小さかったころ似たようなことを試した時にはそれほど
> 劇的には改善しませんでしたが．

もともとキャッシュしなくても hash(Hashにあらず) を
クラスのメソッドの探索に使っているので、以上にクラス階層が
深くならない限りミスキャッシュのランタイムコストは、これ以上
気にしないでいいと思います。
キャッシュエントリの衝突も十分押さえられ手いる様です。
典型的な ruby のアプリがわからないんで、あれなんですけど、、

> |>   * 構文木の再設計(parse.y,node.h,eval.c)
> |
> |これはたとえば、
> |	obj += INTEGER
> |を現在は
> |	OP_ASGN と INTEGER
> |に分解してるのを
> |	OP_ASIGN_INTEGER 
> |と新しく定義した複合的な単一ノードにして、eval() のトラバースを
> |少なくするといった NODE 定義の拡張でしょうか？
> 
> いや，もっと大胆なことを考えています．今のrubyは部分式の評価
> をrb_eval()の再帰呼出で行っていますが，これを非再帰化すると
> 言うものです．ただ，そのためにソフトウェアスタックを使う必要
> が出たりするとかえって遅くなるかも．まだ実装にかかれる程考え
> がまとまっていません．

＃JavaVM に食べさせようとしてませんか？ (^^)

  例外からの復帰がスタックと整合するか問題ですね。
  ソフトスタックもThread毎に必要でしょうし、
  イテレータもスタックに絡まってきそうですね。

この辺の問題が、 setjmp() で一挙に解決してるんで
「絶妙」だと思ったわけです。（あの volatile は尋常ぢゃない）

> |魅力的ですが、 gc.c も NODE の解釈をしているのが大変そうですね。
> 
> gc.cのNODEの解釈は高速化のためだけですし，知らないノードに対
> してもなんとか動くようになっていますので，心配はいりません，
> 多分．

GC が全部の NODE を知ってる（様にみえた）のでてっきり
新しい NODE タイプをつくるとそのままではこけると思ってました。
なるほど、 default: でサルベージュしてますね。
結局 looks_pointerp() してメンバのマークを力ずくでやってるんですね。

逆に言うと、ここの default: に来る NODE をなくすとよいと、、
（多分今は殆ど来ないと思う）

> |> などが考えられます．rubyでは大量にsetjmpを呼んでいるのが明ら
> |> かですから，とくに最後のものをいつか実現しようと考えています．
> |
> |setjmp を使っているところを、他の仕組みで実装すると
> |余計遅くなりそうな気がしませんか？
> 
> たとえば現在のrubyではwhileなどの単純ループやclass/module定
> 義などでもsetjmpを使っています．この辺はパーザとの連係で減ら
> せるのではないかと考えています．そのためにはrb_evalの非再帰
> 化が必要そうですけど．

ですね、このあいだの _setjmp() への変更で、なぜにあんなに
スピードが変わるかわかったような気がします。
x86 や sparc は setjmp() で数十バイトしか退去しませんが
mips や amd29000 のようなレジスタマシンだと１Ｋバイト
前後の退去が起こるので、setjmp() の多様はつらいかもしれません。

時流としては、シリコンでのレジスタは増やしてもインストラクションは
比較的少ない（と行っても３２本ぐらい）のレジスタにしてそれを
レジスタリネーミングで投機実行の先行実行にあてがうのがメインストリートに
なってきたので setjmp() のコストが爆発することはないでしょう。
（でも VLIW が流行ったらまずいかも）


> |私が Thread 関係のコードに恐れをなしている事が一番の理由なんですが、
> |(GC と Thread は私の理解を超えてます :-p)
> 
> いやあ，実は私もです．スレッドなんか良く動いてるなあと自分で
> も思うんですけど．

ruby のスレッドって１０ｍｓでスケジューラ呼んでますよネ
これにプライオリティエンコード付けるとメモリ保護無しですが、
いっぱしのマルチタスク環境になりますね。

＃その前に非同期ＩＯを実装しないと、、

> |それから、/RE/ のコンパイルの部分を新しい librx に差し替えると
> |速くなるかもしれないです。
> |、、今の GPL な regex をスクラッチから書き直すって ToDo
にあったやうな、、
> 
> rubyの正規表現は遅いですからねえ．librxってperl(4|5)相当の機
> 能を持たせられましたっけ？

\W とか \b とかですね、当然...ないです。
やっぱスクラッチから書くしかないかなぁぁ、、
flex で書いても人手より速くないですよね、、

正規表現ってあれで独立した言語みたいなものだから手強いです。

  えぐち