Gauche:継続フレームの縮小

Gauche:継続フレームの縮小

Shiro(2012/02/21 21:35:46 UTC): 0.9.2現在、継続フレームは6ワード使ってるんだけど、もっと節約できそうな気がしてきたのでメモ。

現在の構造は次のとおり。

  prev      ; 前の継続フレームへのリンク
  env       ; 環境フレーム
  argp      ; 積みかけの引数フレームへのポインタ
  size      ; 積みかけの引数フレームのサイズ
  pc        ; 実行を再開するコード位置
  base      ; 現在実行中のSchemeコード

積みかけの引数、というのは、継続作成時にスタックトップにある、まだ環境フレームに なっていないいくつかのデータ。C言語では継続スタックをポップすれば自動的にそういう データがスタックトップにある状態に戻るのでこれらのデータを保存しとく必要はないけど、 Gauche VMではスタックの内容が移動することがあり、その時そういう積みかけのデータも 一緒に動かさないとならないのだ。

で、ここから1ワードか、もしかすると2ワード削れるかもしれない。

まず積みかけの引数フレームについて。継続フレームを積む直前のスタックが こうだったとすると (スタックは下に伸びる):

          |        |
          |        | ここまで、環境フレームもしくは継続フレーム
     ARGP>|   x    |
          |   y    | 3ワード「裸の」データが積まれた状態
          |   z    | スタックトップ
       SP>|        |

継続フレームを積むとこうなる。 argpに直前のARGPの値が、sizenには直前のSP-ARGPの値が入る。

          |        |
          |        | ここまで、環境フレームもしくは継続フレーム
        *>|   x    |
          |   y    | 3ワード「裸の」データが積まれた状態
          |   z    | スタックトップ
     CONT>|  prev  | 新しい継続フレーム
          |  env   |
          | argp=* |
          | size=3 |
          |  pc    |
          | base   | スタックトップ
 ARGP, SP>|        |

でも、保護される未完成のフレームは常に継続フレームの直前にあるから、 sizeかargpのどちらかだけ保存しとけば情報としては十分だ。 むしろ環境フレームと同様、保護される未完成のフレームまで含めて 継続フレームとして扱えばいい。sizeは継続フレームのサイズ、ということになり、 argpは不要になる。

継続フレームにはもうひとつ、 C関数がトランポリンで別のC関数を呼び出すためのC Continuation Frame というのがあって若干違う形式を取る。

          |        |
     CONT>|  prev  |
          |  env   |
          | argp=0 |  C Continuationであることを示す
          | size=n |  渡すデータの数
          | pc=func|  呼び出すC関数へのポインタ
          | base   |
          |  C0    |  funcに渡すデータ
          |   :    |
          |  Cn-1  |
 ARGP, SP>|        |

でもこれでfuncに渡すデータを継続フレームの前に積むようにすれば 通常の継続フレームと同じ形になる。argpがなくなると C continuationかどうかの区別が困りそうだが、実はC continuation frameのenv情報は冗長なので、envの方にC continuation frameであることを 示す特殊な値を入れておけば良い (C Continuationを作るのはCルーチン(subr)からで、subrが呼ばれている ということはスタックトップには常に継続フレームがある=環境ポインタは既に保存されている、から)。

(C continuation frameでのenv情報を落とすと、Cの継続関数が呼ばれた時点で vm->envが復元されていないことになるから、継続関数からvm->envを参照してる コードがあるとやばい。多分そういうコードは無いと思うが、要確認)。

もひとつ削れないかと思ってるのはbase。これは継続を積む時点で 実行中のScheme手続きの実体(ScmCompiledCode)を指していて、 ScmCompiledCodeはコードベクタ、定数ベクタ、デバッグ情報などを持っている。

baseレジスタの値は、コードの実行そのものに必須ではない。 バックトレースの作成やプロファイリングに使われる。 (Gaucheでは定数はコードベクタに直接埋め込まれてるので、 定数ベクタはコード実行中には参照されない。定数ベクタがある理由は、 コードベクタ自体はGCがポインタを追跡しないメモリとしてアロケートされるんで、 GCから定数を保護するため)。

でも、継続フレームのpcがコードベクタを指してるのだから、 コードベクタにScmCompiledCodeへのバックポインタを持たせとけば、 デバッグ用の情報は辿れるだろう。時間はかかるけど。

問題はGCからの保護で、そのためにはコードベクタをATOMICで アロケートするんじゃなくて、最初のワードだけポインタを辿るような カスタムマーカーをつける必要がある。

時々、pcに、実行中のコードベクタ以外のものを指させることがあるんだけど、 多分必要なコードベクタは既に積まれた継続フレームのpcから指されているはず(要確認)。


Shiro(2012/03/31 13:30:46 UTC): argpの除去と、C continuation frameでデータを 先に積む変更を入れた。ベンチマークでは、再帰ヘビーなマイクロベンチマーク (fibonacciとかackermanとか) で6-8%の改善。普通のプログラムだと1%以下で ノイズに埋もれるくらいになっちゃうけど、悪くはならないんでコミット。

More ...