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%以下でノイズに埋もれるくらいになっちゃうけど、悪くはならないんでコミット。