iriya_ufo’s blog

Curiosity was simply the first derivative of knowledge.

History of T 第16,17,18,19,20パラグラフ

専門的なこと


第16パラグラフ
このころ、Sussmanのグループは MIT Scheme につながる開発を始めだした。
そしてSussmanとAbelsonが共同で教育目的で使用するための本、
"SICP"="Structure and Interpretation of Computer Programs"
を書きはじめた。Lispマシンの努力はSymbolicsとLMIにまで続き、
そしてそれはZetalispやFlavorsが生まれる原因ともなったMaclispを作りだし
またそれらは Common Lisp と Common Lisp's Object System にも多大なる影響を与えた。
でも私はそこから脇道にそれて、Yaleに戻ってきたのだった。


第17パラグラフ
TはかなりクールなGCを備えていた。PDP-10上のMaclispは mark,sweep方式の GC を採用していた。
(それの有名なものとして"ran in the register set"というものがある。それはまた別の
話になるけどね。)それはエンコーディングの型情報に"BIBOP"schemeを使用していた。
すべてのオブジェクトはボックス化されており型によってページに分離している。
その結果オブジェクトアドレスの上位ビットは、ページにどんな種類のものが
含まれているかといったあなたが知りたい情報をページテーブルへのインデックスとして
使用されていたし、そうすることができた。
これはちゃんとしたメモリーシステムをもつPDP-10だからこそ、よく頼れるものであった。
しかし広大なアドレス空間上ではあなたは stop,copy方式 を使いたくなるかもしれない。
なぜなら stop,copy方式 ではあなたは生のデータをコピーすることに注意を払うだけでよく
ごみの量に対して比例するコストなどには気をつかわなくていいからだ。
32ビットマシーンにアロケートできる巨大なヒープとしてそれはすばらしく適している。
ほとんどの stop,copy方式 コレクターはヒープの横形探索(BFS)であるCheneyアルゴリズムで
実装している。しかしBFS(breadth-first search)はメモリー操作としてはそれほど
優れているわけではない。単なるコピーとして全てのヒープ領域に、閉じたデータ構造を
形態的にばらまくだけだからである。これはよくないことだ。
Tはあまり知られていない(シンプルな論文2頁ほどで記述された)アルゴリズムを使用している。
深さ優先探索というものだ。(これはCheneyアルゴリズムを賢くしたものである。ヒープの
データ構造をBFSのキューに提供する。クラークは探索スタックを提供するためにヒープを
使用した。)
深さ優先探索の意味するところはリンクされたリストをガベージコレクトしたら
GCはリストの要素に注意を向ける前にリストの塊として閉めだす、ということである。
なのでそれら"spine"セルはメモリーの中で逐次的に取り出しているのである。
リストはベクターと変換しある位置に固定する。


第18パラグラフ
Tはこのアルゴリズムを80年代後半に古典的なBFSとして採用していた。
その時David Kranzは、BFSアルゴリズムの copy は少しばかり定数要素よりも早い、という
理由から switch を使用していたよ、ということを私に教えてくれた。


第19パラグラフ
That standard religion I just gave you about "stop© only pays
for the good stuff, but in mark&sweep you have to pay for the garbage,
as well"? *1
それは本当のことじゃない。私たちはそれを何十年も信じていたけれど。
でも、ハーバード大学のNorman Ramseyは mark,sweep方式 は stop,copy方式 と
ほとんど漸近的なコストで実装可能になる賢い事例を見せた。
このことは特にタイトなメモリーシステムを持つヒープデータにとって朗報であった。
Normanの所見は実にはっきりしており明瞭であった。
見た瞬間に印象的な結果であると分かるようなものである。
だからこそそれは何十年もの間避けられていたのだった。
しかし、多くの人が GC に対して気を使わなかったというわけではない。
GC のことは研究者から多くの注目を集めていた。勉強会もあったほどだ。


第20パラグラフ
私は T 以外で深さ優先探索の事例を見たことはない。
ところで T ガベージコレクターは T で書かれているということを知っているだろうか？
ちょっとした驚きである。これは T はネイティブコードコンパイルされ、ガベージコレクターは
コンパイラー特権で書かれているという美点によって達成されたものである。
コンパイラーはソースの扱いを正確に熟知しており、実行中にヒープアロケートを必要としない
よう注意深く扱ってくれるのだ。


ミニあとがき
もうすぐ半分ですね。かなりノロノロ進行な更新です。

*1:ここの意味が全く分かりませんでした。