rowlVM/GC ブロック・ページの管理(再考) - ブートストラッピングでコンパイラを作る日記

今朝書いたのは綺麗ではなかったので考えなおします。多分車輪の再発明だと思いますが。
ポイントはページ⇔ページデスクリプタ間のアドレス変換のシンプル化です。
ページデスクリプタ・ページの配置を以下のようにします。

|<---------------------- 1 Mbyte -------------------------------->|
|空白|pd0|pd1|....|pdN-1|(長さ0以上の空白)|page0|page1|....|pageN-1|

そして

|(先頭)...|pd0|pd1|....|pdN-1|

の部分と

|(先頭)... |page0|page1|....|pageN-1|

の部分が相似になるようにします。こうするとアドレス変換が相似比の乗除算(+ベースアドレスのマスク処理など)のみとなります。
乗除算はシフトでやりたいので相似比は2べきになるようにします。

$B=\mbox{size of a block in bytes}$
$N=\mbox{number of pages}$
$s_d=\mbox{size of a page descriptor in bytes}$
$s_p=\mbox{size of a page in bytes}$
$o_d=\mbox{offset of the first page descriptor}$
$o_p=\mbox{offset of the first page}$
とすると、条件は
$o_d:s_d N=o_p:s_p N$
$o_p \ge o_d + s_d N$
$o_p + s_p N = B$
でこれを解くと
$N \le \frac{s_p - s_d}{s_p^2}B$
となります。ここで等号が成立するように各値を選ぶと
$o_d = \frac{s_d^2}{s_p^2}B$
$o_p = \frac{s_d}{s_p}B$
となります。また相似比( $\frac{s_p}{s_d}$ )も2冪にしたいので $s_d$ も2冪にします。
計算すると上の方の図の(長さ0以上の空白)の部分は長さ0になって消えます。

メモリ使用効率(オブジェクトの為に使用されるメモリの割合)は
$\frac{s_p-s_d}{s_p}$
になります。すなわち $\frac{s_d}{s_p}$ の値がページ管理のメモリオーバヘッドです。
B=1MBは固定にして、何パターンか計算すると以下のようになります。

デスクリプタサイズ( $s_d$ )	ページサイズ( $s_p$ )	ページ数( $N$ )	総ページサイズ	利用効率
4	256	4032	1008KB	98.4%
8	256	3968	992KB	96.9%
16	256	3840	960KB	93.8%
4	512	2032	1016KB	99.2%
8	512	2016	1008KB	98.4%
16	512	1984	992KB	96.9%
4	1024	1020	1020KB	99.6%
8	1024	1016	1016KB	99.2%
16	1024	1008	1008KB	98.4%
4	2048	511	1022KB	99.8%
8	2048	510	1020KB	99.6%
16	2048	508	1016KB	99.2%
16	4096	255	1029KB	99.6%

ほかに考慮すべき点は

ページサイズを小さくすると
- ページアロケーション回数が増える。
- フラグメンテーションが増える。
ページサイズを大きくすると
- Mostly Copying GCではrootオブジェクトの属するページを丸ごと生きている事にする為、解放されないオブジェクトが増える。

という点でしょうか。
ここら辺の対策はそのうち考えることにしてとりあえず、(8,512)を採用して実装することにします。