ささだです。

　色々スタックフレームのデザインを考えてたんですが、結局オリ
ジナリティのないデザインになりそうです。とりあえず、まとめて
みました。

----------------------------------------------------------------------
・スタックフレーム概観

  method frame:

  VALUE a1, a2, ... , aM;
  VALUE l1, l2, ... , lN

  struct method_frame:        <- lfp <- dfp
    VALUE block;          // lfp[0]
  
  struct control_frame:       <- cfp
    VALUE magic; // MAGIC_METHOD
    VALUE self;           // cfp[0]
    VALUE iseq;           // cfp[1]
    struct continuation_frame:
      VALUE pc;           // cfp[2]
      VALUE lfp;          // cfp[3]
      VALUE dfp;          // cfp[4]
      VALUE cfp;          // cfp[5]
  

  block frame:

  VALUE a1, a2, ... , aM;
  VALUE l1, l2, ... , lN; // zero clear
                          // block local variables will be vanished at Ruby 2.0

  struct block_frame:         <- dfp
    VALUE prev_dfp;       // dfp[0]

  struct control_frame:       <- cfp
    VALUE magic; // MAGIC_BLOCK
    VALUE self;           // cfp[0]
    VALUE iseq;           // cfp[1]
    struct continuation_frame:
      VALUE pc;           // cfp[2]
      VALUE lfp;          // cfp[3]
      VALUE dfp;          // cfp[4]
      VALUE cfp;          // cfp[5]


  class frame:

  VALUE a1, a2, ... , aM;
  VALUE l1, l2, ... , lN; // zero clear

  struct class_frame:         <- lfp, dfp
    VALUE dummy;          // lfp[0]
  
  struct control_frame:       <- cfp
    VALUE magic; // MAGIC_CLASS
    VALUE self;           // cfp[0]
    VALUE iseq;           // cfp[1]
    struct continuation_frame:
      VALUE pc;           // cfp[2]
      VALUE lfp;          // cfp[3]
      VALUE dfp;          // cfp[4]
      VALUE cfp;          // cfp[5]


  Proc オブジェクト

  struct ProcObject:  // native type object?
    VALUE *self_ptr;
    VALUE *env_ptr;
    VALUE iseqobj;

  Block オブジェクト

  struct BlockObject: // native type object?
    VALUE *self_ptr;
    VALUE *env_ptr;
    VALUE iseqobj;


  VALUE magic には、それぞれ、フレームを示す id が入っています。
現状はデバッグ用にこれを含ませていますが（フレーム構造が壊れた
ら、すぐにわかる）、リリース時にはなくそうかと考えています。


----------------------------------------------------------------------
・今までとの違い

- cfp を新設しました

　control frame pointer の略です。

　dfp が cfp の代わりをしていたんですが、dfp がヒープをさす
ようになると、どうしてもこれが必要になるようでした。

・self をフレームごとに持つことにしました

　instance_eval などでは self がブロックの持ち主と変わってし
まいますが、これを実現するためにはどうしてもこうしなければな
らないと考えました。

　最初は instance_eval などの実行時、self へアクセスする命令
を全て動的に変更するような仕組みを考えていたのですが、どうに
もなかなか実現しそうにないのでこのようにしました。


----------------------------------------------------------------------
・議論

- すべてのブロック付きメソッド呼び出しでは Proc オブジェクト
　を生成する？

　現状では、まだしないで済むようにしています。そのために、
Proc と Block では同じようなデータ構造にして、yield 側ではそ
の差異を無視できるようにできないか考え中です。

　そのため Block オブジェクトは、必ず生成する必要があるよう
になってしまいそうです。でも、ruby object space から取るだけ
なので、まだマシかな〜。でも GC しないと駄目なので、やっぱり
嫌だな〜。

　Block オブジェクトはスレッドローカルであればいいので、スレッ
ドローカルストレージを用意して、そいつから使いまわすようにすれ
ばいいかも。うーん、駄目かも。

　まだ、条件分岐で処理を yield 時に切り替えるって夢も捨ててない
ので、作ってから考えてみます。


- Proc からの大域ジャンプの制限

　return とか break とかその辺ですけれど（orphan などではこれ
らジャンプを禁止するという制限）、スタック巻き戻しを行うとき
に、必ず Proc が持つ環境に mark をするようにします。

  具体的には、  dfp[1] = Qundef;  とする予定です。dfp[1] が
Qundef ならば、そのフレームを一度 return した後だということが
わかり、break や return を行っていいものかどうかを確認するこ
とが出来ます。

（・・・akr さんじゃないですけど、call/cc したらどうなるんだ、
これ・・・。何を保存して何を保存しちゃいけないんだろう）

　Proc オブジェクトにするときには、この領域にダミー領域を用意
しておきます。

　メソッドから戻るときにもこの動作を行いますが、これを行うと
きには、すでにその領域は不要になっているため、これを行っても
問題はありません。

　しかし、すべてのフレーム巻き戻しの際にこの動作を行うため、
メモリアクセスがそれぞれに一回ずつ増えてしまいます。条件文を
入れるよりましかなー、と思ったのですが、これは実際に作ってみ
て、考えてみます。

　条件文で実行しようとすると、

if( stack_low > dfp || stack_high < dfp ){
  orphan_mark();
}

になりますが、条件文は速度的に嫌だなぁ、とか。

　でも、メモリアクセスだけのほうが遅かったりして。分岐予測に
あたってしまえば、ペナルティないしなぁ。


- lfp の有用性について

　前田さんには散々反対された lfp ですが、私もだんだん要らない
ような気がしてきました。

（lfp は、メソッドローカルフレームを常にさしており、self や
ブロック、メソッドローカル変数へのアクセス手段を提供します）

　lfp を支持する強い理由は lfp[0] で self が参照できたという
ことなのですが、今回毎回スタックフレームに積むことにしたので、
cfp[0] でアクセスすることが可能になりました。

　lfp を用意する他の理由は、メソッドローカル変数へのアクセス
ですが、dfp[0]を previous_env_frame としたとき、

  0 level（そのブロック）のローカル変数 idx

=>    dfp[-idx]

  1 level（一段上のブロック）のローカル変数 idx

=>    ((VALUE *)dfp[0])[-idx]

　のようになります（もちろん、もう一段上は dfp[0][0][-idx]）。

  def m
    i = 0 # 0 level(method local)
    iter{|x|
      i = 1 # 1 level(method local)
      x = 1 # 0 level(block local)
      iter{|y|
        i = 2 # 2 level(method local)
        x = 2 # 1 level(block local)
        y = 2 # 0 level(block local)
      }
    }
  end


　普通の Ruby プログラムは、多分 1 level 上のローカル変数アク
セスが殆どだと思うのですが、その代わり、lfp を用いることで常に
メソッドローカル変数へ lfp[-idx] としてアクセスできます。

　さて、毎フレームごとに lfp を積むのと、すべて dfp だけでやる
の、どっちが速いか。やってみないとわかんないっすかねぇ。

　lfp を設けるのは、yarv の数少ないオリジナリティだとは思うんで、
できれば残したいとは思うのですが。

　あ、そうだ。lfp の大きなののもう一個に、break 先を探すことが
できる、ってのがあります。ネストしたブロックの脱出のとき、正しく
break 先を探すことができます。redo もそう。retry もそう。

　つまり、lfp == dfp になるまで、dfp を巻き戻せばいいんです。

　現状の ruby では、この目的のために、ユニークな何かを積んでる
ような実装になります。これが、本質的に不要になります。これは
シンプルでいいなぁ。


- ブロック付き Proc オブジェクトの call について

　これは今は許さない構造になっています。というか、勘弁してく
ださい orz。

　これを許そうとすると、これも全てのフレームに積むことになる、
ような気がします。それは嫌だなぁ。



----------------------------------------------------------------------
・今後の課題

- とりあえず上記のことを全部実装

　やんないと話にならないですね。

- C -> Ruby call の実装

　やんないと話にならないですね。eval.c 書き換えが必要。

- stack caching の実装

　IA32 だと、やっぱり遅くなるのかなあ。うーん。少なくとも、sp
操作が減るのと、分岐バッファが拡散する（実質命令が増えるため）
ので、遅くなるってことはないと思うんだけれど。

　で、そのためには、これ用のコードの生成系作んないとなぁ。楽し
そうなんだけれど。そもそも、本当に自動でできるのかすげぇ楽しみ
で。vmgen でも、自動で作成はしませんでしたよね？　たしか。

　あれ、してたっけかなぁ。今手元に論文がない。

- プロファイラの開発

　とりあえず、各VM命令の統計情報とか、各レジスタへのアクセス
回数の統計情報とか、そういうの。マシン命令サイクルの統計もで
きるようにしようと思って、全然さぼってますねぇ。

　そういえば、VTune 買ったほうがいい？

- super instructions の自動生成

　統計情報から自動コンフィギュレーションとか考えてたんだけれど、
やっぱりしんどそうだから、手作業でやろうかなぁ。



----------------------------------------------------------------------

　しかし、この変更で、特に cfp を設けたことで、ずいぶんとシン
プルになりました。cfp が増えたことと、self の push が増えるこ
とで、コストは大きくなってるわけですが・・・。

（だから、lfp は削ろうか検討中。でもなぁ。どうしようかなぁ）

-- 
// SASADA Koichi at atdot dot net
//

// で、発表資料はまだ何も手をつけていない orz
// 何喋ろう。


--
ML: yarv-dev quickml.atdot.net
使い方: http://www.atdot.net/~ko1/quickml