Gauche:CompactingPair

Pairの2ワード化

(2004/12/17 20:07:37 PST)

0.8.3までのGaucheは、富豪的にPairに4ワードも使っていた。 富豪的プログラミング指向というわけじゃなく、まず動かすためにKISS原則 に従ったためだ。0.8.3までのアーキテクチャではヒープアロケート されたオブジェクトは必ず第一ワードがそのオブジェクトのクラスへの ポインタになっているので、単純だしデバッガでも追いやすい。

しかしアプリケーションも徐々に増えつつあるし、サーバ側で使う 場合はメモリ使用量は無視できないファクタだし、 もったいないお化けも出てきそうだからここらでPairを2ワードに することにした。

構造

Pairを2ワードにするということは、carとcdrで一杯になる。

          +-----------------+
          |       car       |
          +-----------------+
          |       cdr       |
          +-----------------+

タグが置けないが、これはPair以外のヒープアロケーテッドな オブジェクトの最初のワードに「carには決して出現しない値」を 置くことで区別できる。

具体的には、これまで先頭ワードをクラスオブジェクトへのポインタに していたものを、「((ScmByte*)クラスオブジェクトへのポインタ)＋3」にする。

          +-----------------+
          |   class ptr   11|
          +-----------------+
          |      slot       |
          :                 :

下位2bitが11であるSchemeオブジェクトは存在しないので区別がつく。

(そう、このために当初から下位2bit=11を予約していたのだった。 今回手をつけるまですっかり忘れておった。 なおこの手法は Scheme->C という処理系で使われていたものだったと思う。)

この変更によるペナルティは、型タグチェックのSCM_PAIRPマクロにおいて マスキング演算が一つ余分に入ること。(SCM_XTYPEPの方は、比較する クラスがstaticな場合はコンパイル時に+3を計算しておけるのでペナルティ無し、 変数の場合は+3のペナルティが入る)。

Boehm GCでALL_INTERIOR_POINTERSを定義しているので、 +3されたクラスオブジェクトへのポインタもそのクラスオブジェクトへの 参照と認識され、他のどこからも参照されていなくてもクラスオブジェクトが GCされてしまうことはない。

なお、ソースコード情報等を保存しておくために、0.8.3までの GaucheではPairにattributesというalistを付加できるようになっている。 が、これは全てのPairに必要なわけではない(readした際のリストの先頭とか、 コンパイル中に作られるリスト等)。 そこで、そういう付加情報が必要な場合だけExtendedPairというのを アロケートして使うことにする。

          +-----------------+
          |       car       |
          +-----------------+
          |       cdr       |
          +-----------------+
          |    attributes   |
          +-----------------+

ExtendedPairはタグによる型チェックの際にはPairと区別がつかない (従って、SCM_PAIRPで余分なチェックは必要ない)。 attributesをアクセスするAPIは、渡されたオブジェクトのサイズを 調べてそれがExtendedPairかどうかを判断する。 これはBoehm GCにオブジェクトのサイズを問い合わせるAPIがあるので可能。 ただ、そうそう軽い処理でもない(Boehm GC内部でアドレス→オブジェクトサイズ のマップを管理しているテーブルにアクセスする)ので、 気軽に使うべきものでもない。ソースコード情報へのアクセスは プログラムロード時とエラー/デバッグ時のみなので、オーバヘッドは 許容できるだろう。

(なお、attributesを別テーブルで管理する案も検討したが、 GC回りが面倒になりそうだったのでやめた。)

実装過程

こういうベーシックなところの変更はおっかないので、 常に動作する状態を保ちながら徐々にやるのが良い。 今回はこんな感じでやった。各ステップの後で動作確認や ベンチマークを取りながら作業を進めた。

• ヒープアロケーテッドオブジェクトの第一ワードをクラスへの ポインタからクラスタグ(ポインタ+3)へ変更。
• ScmPairの定義を変更、SCM_PAIRP, SCM_XTYPEPおよびlist.cの Scm_Cons回りを変更。
• ScmExtendedPairを作成。Pair attributeへアクセスしている 箇所を探して、必要な場所でScm_ConsをScm_ExtendedConsに。

影響

マクロで行儀良くアクセスしている拡張コードなら、 変更無しでリコンパイルすれば動くはず。

性能評価

ヒープサイズが10%-25%減少。 総アロケーションバイト数は10%-50%減少。

昔調べた時は、総アロケーションバイト数のうちPairが75%を占めていた。 この比率のままなら、総アロケーションバイト数で37%程度の減少が見込める。 実際にはアプリ毎にパターンが違い、50%減少は人為的に大量にリスト作成 をするようなもの。逆に文字列を読み込んで順次処理するようなものだと10%程度の 減少に留まるようである。また、Pairは一時的データ構造として多用される ことを考えると、ヒープサイズの減少は総アロケーションほど大きくはないのは 仕方ない。

総アロケーションが減っているのでGC時間も減ることが期待されるが、 一方でタグチェックのペナルティもある。いくつかベンチを試してみた ところ、実行時間としてはあまり変化が無いようだ。 5%程遅くなるものもあれば、逆に速くなるものもある。

まあ、満足できる結果なので、0.8.4に入れよう。