[ 目次, 前節, 次節, 索引 ]

(accumulate + 0 (filter odd? (enumerate-interval 0 n)))

   対を再利用するには, 割り当てられた対のどれが(その内容が将来の計算に影響しないという意味で)不要かを決める方法がなければならない. この実現法としてここで調べる方法はごみ集め(garbage collection)として知られている. ごみ集めは, Lispの解釈の任意の時点で, 将来の計算に影響し得るオブジェクトは, 現在, 計算機のレジスタにあるポインタから始めて, carとcdrをなんとか続けて到達可能なものだけであるという観測に基づいている.14 こうしてアクセス出来ないメモリーセルは再利用出来る.

   こみ集めの方法はいろいろある. ここで調べる方法はストップアンドコピー(stop and copy)とう. 基本的な考えは, メモリーを半分: 「作業メモリー」と「自由メモリー」にする. consが対を構成する時, これを作業メモリーに割り当てる. 作業メモリーが満杯になった時, 作業メモリーの有用な対を探してそれを自由メモリーの連続する場所へコピーすることでごみ集めを行う. (計算機レジスタから始め, carとcdrポインタを辿ることで有用な対を探す.) ごみはコピーしないので, おそらく新しい対の割当てに使える余分の自由メモリーがあるであろう. その上そこの有用な対はすべてコピーしたので, 作業メモリーのものは, なにもいらない. こうして作業メモリーと自由メモリーを役割を交換すれば, 処理を続行することが出来る; 新しい対は, (昔は自由メモリーであった)新しい作業メモリーに割り当てる. これが満杯になると, (昔は作業メモリーであった)新しい自由メモリーへコピーする.15

ストップアンドコピーごみ集めの実装

   ごみ集めは現在の作業メモリーの自由セルを使い切った時, つまりcons演算がfreeポインタをメモリーベクタの終端を越えて増やそうとした時, 起動される. ごみ集めの処理が完了すると, rootポインタは新しいメモリーを指し, rootからアクセス出来るすべてのオブジェクトは, 新しいメモリーに移され, freeポインタは新しいメモリーで新しい対が割り当てられる場所を指す. その上, 作業メモリーと新しいメモリーの役割を交換し, ---新しい対はfreeの示す場所から始めて, 新しいメモリーに構成され, また(以前の)作業メモリーは, 次のごみ集めで, 新しいメモリーとして使用可能になる. 図5.15は, ごみ集めの直前と直後のメモリーの配置を示す.



図5.15 ごみ集め処理によるメモリーの再構成

ごみ集め処理の状態は, 二つのポインタ: freeとscanを維持して制御する. これらを新しいメモリーの先頭を指すよう初期化する. アルゴリズムはrootの指す対を新しいメモリーの最初に移動することで始る. 対がコピーされ, root ポインタは, 新しい場所を指すようにされ, freeポインタは増やされる. 更にこの対の古い場所に, この内容は移したということを示す印をつける. この印つけは次のようにする: carの場所には, これは既に移動したオブジェクトであることを示す, 特別のタグを置く. (そういうオブジェクトは伝統的に 失恋対(broken heart)という.)17 cdrの場所には, そのオブジェクトが移された場所を指す 移転先アドレス(forwarding address)を置く.

   rootを移動した後, ごみ集めは基本サイクルに入る. アルゴリズムの各ステップで, (最初移したrootを指している)scanポインタは, 新しいメモリーに移されたが, そのcarとcdrはまだ古いメモリーにあるオブジェクトを参照している対を指す. これらのオブジェクトはそれぞれ移され, scanポインタは増やされる. オブジェクト(例えばわれわれが走査している対のcarポインタの指すオブジェクト)を移すには, そのオブジェクトが既に移されたかどうかを調べる. (オブジェクトのcarの場所に失恋タグがあるので分る.) オブジェクトがまだ移されていなければ, それをfreeの指す場所へコピーし, freeを更新し, オブジェクトの古い場所を失意に設定し, そのオブジェクトへのポインタ(今の例では, 走査している対のcarポインタ)を新しい場所を指すよう更新する. オブジェクトが既に移されていれば, (失恋対のcdrの場所で見つかる) 移転先のアドレスが, 走査中の対のポインタに置き換る. 最終的にすべてのアクセス出来るオブジェクトは移され走査される. その地点でscanポインタは, freeポインタに追いつき, 処理は終了する.

   ストップアンドコピーアルゴリズムをレジスタ計算機の命令の列として規定出来る. オブジェクトの移動の基本ス%\linebreak テップは, relocate-old-result-in-newというサブルーチンで実現する. このサブルーチンは, 引数, 移動すべきオブジェクトへのポインタを oldという名のレジスタからとる. 指示されたオブジェクトを移動し, (処理中にfreeを増やし,) 移動したオブジェクトへのポインタを newというレジスタに置き, レジスタrelocate-continueに格納された入り口へ分岐して戻る. ごみ集めを始めるには, freeとscanを初期化した後, rootポインタを移動するためにこのサブルーチンを起動する. rootが移動出来ると, 新しいポインタを新しいrootとし, ごみ集めの主ループに入る.

begin-garbage-collection
  (assign free (const 0))
  (assign scan (const 0))
  (assign old (reg root))
  (assign relocate-continue (label reassign-root))
  (goto (label relocate-old-result-in-new))
reassign-root
  (assign root (reg new))
  (goto (label gc-loop))

   ごみ集めの主ループでは, 走査すべきオブジェクトがまだあるかどうか決めなければならない. それにはscanポインタがfreeポインタと一致しているかどうかテストする. ポインタが等しければ, すべてのアクセス可能なオブジェクトは移されており, 中断した計算が続行出来るよう後始末するgc-flipへ分岐する. まだ走査すべき対があれば, 次のcarを移すため, (carポインタをoldに置いて,) 移動のサブルーチンを呼び出す. relocate-continue レジスタは, サブルーチンがcarポインタの更新に戻るように設定する.

gc-loop
  (test (op =) (reg scan) (reg free))
  (branch (label gc-flip))
  (assign old (op vector-ref) (reg new-cars) (reg scan))
  (assign relocate-continue (label update-car))
  (goto (label relocate-old-result-in-new))

update-carでは, 走査している対のcarポインタを修正し, その対の cdrの移動に進む. その移動が済むと, update- cdrへ戻る. cdrを移動し更新すると, その対の走査が終了し, 主ループを続行する.

update-car
  (perform
   (op vector-set!) (reg new-cars) (reg scan) (reg new))
  (assign old (op vector-ref) (reg new-cdrs) (reg scan))
  (assign relocate-continue (label update-cdr))
  (goto (label relocate-old-result-in-new))

update-cdr
  (perform
   (op vector-set!) (reg new-cdrs) (reg scan) (reg new))
  (assign scan (op +) (reg scan) (const 1))
  (goto (label gc-loop))

   サブルーチンrelocate-old-result-in-newは, オブジェクトを次のように移動する: (oldが指している)移動すべきオブジェクトが対でなければ, オブジェクトへの同じポインタを変更せずに(newに)戻す. (例えばそのcarが整数4である対を走査しているとする. carを5.3.1節で述べたように, n4で表現したとすれば, 「移動した」carポインタはやはりn4であって欲しい.) それ以外は移動を行わなければならない. 移動すべき対のcarの場所が失恋タグを持っていれば, その対は実際既に移されているので, (失恋対のcdrの場所から)移転先アドレスをとり, これをnewに返す. oldのポインタがまだ移動前の対を指していれば, この対を新しいメモリーの(freeが指している)最初の自由セルへ移動し, 失恋タグと移転先アドレスを古い場所に格納して, 失恋対を設定する. relocate-old-result-in-newはoldの指すcarやcdrを保持するのにレジスタ oldcrを使う.18

relocate-old-result-in-new
  (test (op pointer-to-pair?) (reg old))
  (branch (label pair))
  (assign new (reg old))
  (goto (reg relocate-continue))
pair
  (assign oldcr (op vector-ref) (reg the-cars) (reg old))
  (test (op broken-heart?) (reg oldcr))
  (branch (label already-moved))
  (assign new (reg free)) ; 対の新しい場所
  ;; freeポインタを更新
  (assign free (op +) (reg free) (const 1))
  ;; carとcdrを新しいメモリーへコピー  (perform (op vector-set!)
           (reg new-cars) (reg new) (reg oldcr))
  (assign oldcr (op vector-ref) (reg the-cdrs) (reg old))
  (perform (op vector-set!)
           (reg new-cdrs) (reg new) (reg oldcr))
  ;; 失恋対を構成  (perform (op vector-set!)
           (reg the-cars) (reg old) (const broken-heart))
  (perform
   (op vector-set!) (reg the-cdrs) (reg old) (reg new))
  (goto (reg relocate-continue))

already-moved
  (assign new (op vector-ref) (reg the-cdrs) (reg old))
  (goto (reg relocate-continue))

   ごみ集めの処理の一番最後で, ポインタを交換, つまりthe-carsを new-carsと, the-cdrsをnew-cdrsと交換して, 古いメモリーと新しいメモリーの役割を交換する. これで次回メモリーを使い切った時, またごみ集めを実行する準備が出来る.

gc-flip
  (assign temp (reg the-cdrs))
  (assign the-cdrs (reg new-cdrs))
  (assign new-cdrs (reg temp))
  (assign temp (reg the-cars))
  (assign the-cars (reg new-cars))
  (assign new-cars (reg temp))

13 これはそのうちには真でなくなるかも知れない. メモリーは十分大きくなり, 計算機の生涯の間に自由メモリーを使い切ることは不可能になる. 例えば一年は約3× 10¹³マイクロ秒だから, 一マイクロ秒に一回consするとすれば, 30年間メモリーを使い切らずに演算出来る計算機を構築するには, 10¹⁵のメモリーセルを必要とする. この大きさのメモリーは今日の標準でいえば, 馬鹿でかいが, 物理的に不可能ではない. 他方, 処理装置はどんどん速くなり, 将来の計算機は単一メモリーに対し, 並列に演算する多数の処理装置を持つようになろう. そこで仮想したより, ずっと早くメモリーを使い切ることは可能であろう.

14 ここでスタックは5.3.1節に述べたように, リストで表されているとする. 従ってスタックの項目は, スタックレジスタのポインタからアクセス出来る.

15 この考えは MIT電子工学研究所の PDP-1のLisp実装の一部として Minskyが発明し, 初めて実装した. これは Multics時分割システムのLispの実装で使うため, FenichelとYochelson(1969)が更に発展させた. その後 Baker(1978)はこの方式の「実時間」版を開発し, ごみ集めの間も計算を停止する必要をなくした. Bakerの考えは Hewitt, Lieberman とMoonが, ある構造はより一時的であり, またあるものはより永続的であるという事実を利用するように拡張した(LiebermanおよびHewitt 1983参照).

もう一つよく使われるごみ集めの技法は, マーク・スウィープ(mark-sweep)法である. これでは計算機レジスタからアクセス出来るすべての構造を辿り, 到達した対に印をつける. 次に全メモリーを走査し, 印のないものはごみとして「掃除」され, 再利用可能とされる. マーク・スウィープ法の詳細な議論は Allen 1978にある.

Minsky-Fenichel-Yochelsonアルゴリズムは, 大きいメモリーを持つシステムでは, メモリーの有用な部分だけ調べるので, 有力なアルゴリズムである. これはスウィープフェーズでは, メモリー全体を調べなければならないマーク・スウィープとは対照的である. ストップアンドコピーのもう一つの利点は, それが 詰込み(compacting)ごみ集めであることである. つまりごみ集めのフェーズの終了は, 有用なデータは連続したメモリー領域に移され, ごみの対は押し潰されている. これは, 広く分散した記憶場所へのアクセスには, 余分のページ処理を必要とする, 仮想メモリーを持つ計算機では, 極めて重要な実行上の考察である.

16 レジスタリストには, 記憶場所割当てシステムに使うレジスタ, root, the-cars, the-cdrsおよび本節で紹介する他のレジスタは含まない.

17 失恋対(broken heart)という用語は, 1970年代の初めにMITで開発した Lispの方言MDLのごみ集めを書いた David Cresseyが作った.

18 実際のシステムではごみ集めの目的には対として扱うべきいろいろなことがあるので, ごみ集めではリスト構造の pair?演算の代りに低レベルの述語pointer-to-pair?を使う. 例えばIEEE標準に適合するSchemeシステムでは, 手続きオブジェクトはpair?述語を満足しない特別の種類の「対」として実装してもよい. シミュレーションの目的には, pointer-to-pair? はpair?として実装出来る.

[ 目次, 前節, 次節, 索引 ]