BASICで実装するヒープ構造を考える

というわけで、プチコン3号の制約に合わせてSchemeヒープの構造を考える。実装はC→BASICと移動させていく積りで、Cでも真面目なScheme処理系として使いたい(yuniライブラリのbootstrapに使う)。プチコン3号上の実装では、動的なメモリ確保は文字列とbytevector(後述)だけで、cellは固定数にしようと考えている(Cでは適当な上限を設定し、オーバーしたら単にreallocする)。

全体の構造

そもそもプチコン3号にはポインタが存在しないため、相当する機構を自前で用意する必要がある。また、配列の型が一定である必要があるため、inexact値(要するにfloat)のために専用の配列(floatcells)を使用する。
全てのSchemeオブジェクト(word)は、即値(immediate)か各種cellsのインデックスで表現される。プチコン3号の整数は1ワード32bitsなので、これを分割して使うことになる。
配列は都合3種類必要になる。

  • cells(1) : pairやvectorSchemeオブジェクト一般(words)を格納するcells。pairは2または3(ヘッダ含)連続領域、vectorはその長さ分+1の連続領域を使用することになる。
  • floatcells(2) : 浮動小数点数を格納するcells。matrix等ゲームで多用される構造のために、浮動小数点数の配列を取れるように考慮する。
  • stringcells(3) : 文字列やbytevectorを格納するcells。bytevectorの実装にも文字列を使う。実際にはポインタを格納していることになるが、プチコン3号ではこれを直接的に表現する方法が無い。

個々のcellの状態は2つのビットマップblockmapとcellmarkで表現される。ビットマップで表現することにより、1要素あたり32個のセルをカバーできることになる。

blockmap mark
-------- ----
       0    0 直前のcellの続き
       0    1 空きcell
       1    0 "White" GCのマークフェーズ完了後削除できる
       1    1 "Black" 到達可能なオブジェクトの先頭cellである

(この表現はLuaJIT GCから取っている。)
プチコンではかなり贅沢にメモリが使用できるため、空間効率よりも時間効率を重視している。このフォーマットであれば大量のオブジェクトの解放を少い演算で処理できる可能性がある(最大1演算で32個)。
難しいのは空きブロックの探索アルゴリズムで、best-fitにすべきかfirst-fitにすべきかが絶妙なところ。

wordの構造

ひとまず、cell内のオフセットは2^26(= 64メガ要素)を最大値として、型やタグに6bitを出すことにした。ちょっと出し過ぎな気もするが。。
pairは通常のpairとshort-pairの2種用意する。short-pairはcdr部がpairであるようなpairで、型データを省略してcell中のオフセットだけを格納する。

76543210 76543210 76543210 76543210
-----------------------------------
0000VVVV VVVVVVVV VVVVVVVV VVVVVVVV - Negative Fixnum(28bits)
0001VVVV VVVVVVVV VVVVVVVV VVVVVVVV - Positive Fixnum(28bits)
001100ZZ VVVVVVVV VVVVVVVV VVVVVVVV - Zone(24bits, 2bits)
G1TTTTCC CCCCCCCC CCCCCCCC CCCCCCCC - Head(1bit, 4bits, 26bits)

プチコンVMインタプリタなので、各コンポーネントへのアクセスに必要な命令数を可能な限り少く抑える必要がある。Fixnumは2^29未満の値であればfixnumと判別でき、0xF0000000を加算すれば直読できる(C実装ではこの動作は未定義なので再考が必要そう)。Fixnum(28bits)はcell offset(26bits)よりも長い。vector等のオフセットがcell offsetに上界されるため、それよりも長い整数が望ましい。
短い整数で表現できるオブジェクト(charやboolean等)を格納するために、fixnumとは別にZoneと呼ぶ整数型が確保されている。Zoneは更に4種類に分割される。Zone0 integerはnilやeof-objectのようなatomに使用する。Zone1 integerはchar(今のところ他の目的に使われることはない)。それ以外のZoneも未使用となる。

   Zone0 Atoms
    1 : True
    2 : False
    3 : Nil
    4 : Undefined
    5 : Unspecified
    6 : eof-object
   Zone1 Char

Cellへのポインタを表わすHeadは(グレービット, タイプ, オフセット)の3コンポーネントで構成される。タイプは4bit分確保しているが既にギリギリになっている。。

Type:                     Target:
 -  1 : Bignum             Length Opaque ...
 -  2 : Flonum             Float*
 -  3 : String             String*
 -  4 : (Ratnum)           ??
 -  5 : (Complex)          ??
 -  6 : Symbol             String*
 -  7 : Short-pair         Cell*  Car
 -  8 : Pair               Length Car    Cdr
 -  9 : Vector             Length Value  ...
 - 10 : Alt-vector         Length Value  ...
 - 11 : Intarray           Length Opaque ...   ;; ポインタ等machine word用。C言語実装のために。FFIにも使う?
 - 12 : Doublearray        Length Float*       ;; これは2要素固定。floatcellへのポインタ。
 - 13 : Bytevector         Length Opaque ...
 - 14 : Bytevector-string  Length String*      ;; 文字列オブジェクトをbytevectorに見せる用。
 - 15 : Closure            Cell*

タイプによってオフセット部が指す内容は静的に決定する。ターゲットがLengthとなっているタイプは可変長オブジェクトで、後続のcellをlengthに亘って使用する。PairにはLengthは要らないがとりあえず。Opaqueはwordフォーマットに従わない整数値に使用する。
short-pairはcdr部がCellを指す場合に使用できる。殆どのケースではpairのcdrはpairなのでshort-pairを採用できる。fixnumやcharがcdrに有る場合は収まらないため、Pairにフォールバックする必要がある。

(1 2 . 3) ;; このオブジェクトはCellを5つ消費する
 => $0 = SHORT-PAIR($2) ;; cdr部のアドレスは$2
    $1    FIXNUM(1)
    $2 = PAIR()         ;; fixnumはHeadオブジェクトのオフセット部には収まらない
    $3    FIXNUM(2)
    $4    FIXNUM(3)

グレービットはインクリメンタルGCの実装のために空けてある。インクリメンタルGCが必要かどうかは微妙だが、後からレイアウトを見直すのも大変なので事前に。。