背景

32 第3章 改良型Morrisアルゴリズム データ型 フィールド（32ビット）

Tag アドレス/データ CONSデータ 000<----27ビット---->MV シンボル 001<----27ビット---->MV ブロック 010<----27ビット---->MV 長整数 011<----27ビット---->MV 短実数 1x00<---28ビット--->

短整数 1x01<---28ビット--->

文字コード 1x10<---28ビット--->

図3.1: ワードの構成

: in-use : garbage : a-link

marking backward

scanning

forward scanning

&

relocation

O(S) O(A)

scanning direction scanning direction

BP

BP

BP

adjust smooth pointers

adjust reverse pointers

(a) (b) (c)

address : higheraddress : lower

図3.2: Morrisの方式の概略

ポインタを「順方向ポインタ」（forward pointer）と「逆方向ポインタ」（reverse pointer）の2種 類に分類する．順方向ポインタは，配置番地の大小で，そのワードよりも小さいか同じオブジェクト を指しているポインタである．逆方向ポインタは，同じくそのワードよりも大きいワードを指して いるポインタである．2.4.1節にも同じ用語を定義しているが，2.3.3節で述べたように滑り圧縮では ヒープの番地が小さい方（つまり図の上の方）にあるオブジェクトほど確保時間が長いという特性が あるので，この用語の定義は2.4.1節での定義と矛盾しない．そして，「クラスタ」という用語を定義 する．これは，使用中オブジェクト（あるいはワードといっても良い）の連続した塊のことで，図の 斜線部で示す．

それでは従来のMorrisの方式を，図3.2の左側から順を追って説明する．先ず，ごみ集めは，印付 け準備段階と印付け段階で，使用中の全てのオブジェクトの各ワードに印を付ける．その後の状態が 図の(a)である．

次に，ヒープを番地が大きい方から小さい方に向かって，ワード毎にヒープのデータを調べ，順方 向ポインタの値を補正していく．その手順は，2.3.2節で説明した通りである．この時，各クラスタの 最後端の次のワード（図の「BP」で指されたワード）には，そのクラスタの次のクラスタの最前端 の番地を記録しておく．これらを「a-link」と呼ぶ．これにより，次の段階でヒープ全体を走査する 手間を省くことができる．この段階が終ると図の(b)のようになる．

最後に，a-linkを使ってクラスタのみを走査しながら，ヒープを番地が小さい方から大きい方に向 かって，逆方向ポインタの補正を行ないながらオブジェクト（ワード）を番地が小さい方に向かって 詰め合わせる．a-linkを用いる工夫は，Morrisの論文[56]には示されてはいないが，処理系の実現者 たちの間では常識的な技法である．この段階が終ると図の(c)のようになる．

従来のa-linkによって図の(b)の状態から(c)の状態への移行時のヒープ全体の走査は解消されて

いるものの，(a)の状態から(b)の状態への移行時の全体の走査は必要である．つまり，ごみ集めの ためにヒープ全体をアクセスすることになる．

しかし，次に挙げる事項を考えると，(a)の状態から(b)の状態への移行時でも，ヒープ全体の走 査を行なわないで，使用中オブジェクト，つまり図の斜線の部分のメモリだけをアクセスすることで，

作業を完了できることが望ましい．

• 現在の計算機では，ますます主記憶のアクセス時間とキャッシュ記憶のアクセス時間の比が大 きくなりつつある．

• ごみ集め発生の時間間隔を大きくするには，ヒープのサイズを大きくすれば良いことは，自明 である．

• 一括型のごみ集めでは，Aの大きさは実行する応用プログラムの性質のみに依存し，Sの大き さには依存しない．さらに，キャッシュ記憶の容量はますます大きくなりつつあり，使用中のオ ブジェクトの全てがキャッシュ記憶に収まる可能性がある．

Sに比べてAが充分小さい（高々10%）と仮定するなら，ヒープの一部に連続領域（O-表と呼ぶこ とにする）を予約しておき，印付け段階で，印付けしたオブジェクトの全ての最後尾のアドレス（図

3.2のBPの値）をO-表に記録し，O-表の内容に従って，回収段階を実施するという方策を採れば，

ヒープ全体の走査を回避できる．

しかし，滑り圧縮では，Morrisの方法以外の2.3.2節で紹介した方法を用いるにしても，オブジェ クトに配置番地の大きい順や，あるいは小さい順にアクセスして行かねばならない．従来の滑り圧縮 ごみ集めが，ヒープを番地の大きい側から小さい側，あるいはその逆へと走査していたのは，このた めであった．つまり，表は内容（アドレス）の大小に関してソートされていなければならない．この アイディアに基づくごみ集めは，2.3.3節や2.3.4節で紹介した通りである．しかし，Sahlinのごみ集 め[62]を除いて，ソーティングの対象とするデータの件数は，Lである．L¿Sでない限り，ヒープ 全体を走査するのにかかる時間よりも，ソーティングにかかる時間の方が上回ってしまうだろう．そ こで，ソートするデータの件数を減らすことを考える．

34 第3章 改良型Morrisアルゴリズム

図3.3: ヒープ中の使用中オブジェクトとごみ