実行環境の変化に即応する圧縮型ガーベッジコレクション

全文

(1)Vol. 45. No. SIG 12(PRO 23). Nov. 2004. 情報処理学会論文誌：プログラミング. 実行環境の変化に即応する圧縮型ガーベッジコレクション新. 田. 寛†. 寺. 島. 元. 章†. 圧縮型ガーベッジコレクション（mark-and-compact GC）で，GC 対象領域のオブジェクトの特性を考慮して処理内容を動的に変更する適応型 GC の実装とその評価にについて述べる．圧縮型 GC はその処理形態から GC 対象領域の使用中オブジェクトの分布など，GC の効率に影響を及ぼすようなオブジェクトの特性が詳細に得られる．本 GC では，処理の過程で副次的に得られたクラスタ（使用中オブジェクトの塊）分布を使用して，次回の GC での (1) 新世代領域の容量，(2) 殿堂入りのタイミング，(3) ソート法の採否を動的に決める．前の 2 つについては，すでに複写型 GC にある手法であるが，確率モデルに基づく量的な解析よりも対処が即応的であることを示す．3 項のソート法は複写型 GC とほぼ同じ時間量で処理を行うために必要な手法であるが，多数のクラスタが存在する場合はソート処理に時間を要し，MBT（マークビット表）を走査する方が速くなる．そこで，クラスタ分布に基づいて，両者を適用すべき GC 対象領域を決めることになる．本 GC も，今の結果から次回の GC 処理を決めるという予測モデルに基づくものであるが，その妥当性についても実験結果とともに述べる．. Adaptive Mark-and-compact Garbage Collection Hiroshi Nitta† and Motoaki Terashima† In this presentation, we describe the implementation and evaluation of adaptive garbage collection (GC), based on a mark-and-compact method, that dynamically changes its process according to the characteristics of data object being processed. The GC based on a mark-and-compact method, namely, mark-and-compact GC enables us to easily collect objects’ data such as the distribution of data objects being in use, that may affect the efficiency of the GC. In our adaptive GC, the distribution of clusters (i.e., bricks of data objects in use) that is obtained as a side effect is used to determine (1) the size of a new generation space, (2) promotion threshold, (3) the portion of the new generation space to which sorting method is applied, of the next GC invocation. The former two decisions have been practiced in generational copying collection GC, but our approach is more adaptive than that based on conventional statistical models. The sort method is used in order to perform GC process with the same time complexity as the copying collection GC. When there are a large number of clusters in the new generation space, however, the load of sorting becomes large and the alternative method that is to scan MBT (Mark Bit Table) is superior to the sorting method. Therefore, these two methods are selected considering the distribution of clusters. Our GC is of course based on a model of estimate that forecasts the behavior of the next GC invocation by the current GC’s. The evaluation of the model is also described with the experimental results.. 1. はじめに. いた領域を再利用する自動記憶管理機構のことである．. ガーベッジコレクション（以下，GC と呼ぶ）は動. ついて述べる．この GC は汎用計算機での実装に最適. 的データを扱う言語処理系の必須の機能として，これ. な停止回収型 GC ☆ に属する．圧縮型 GC は，ヒープ. までに数多くの実装方式の研究が行われてきた. 本稿では実行環境の変化に即応する圧縮型 GC に. 1),2). ．. 全体あるいはその一部の領域を連続して使用すること. GC は，ヒープに作られたデータオブジェクト（以下，. ができることや，各オブジェクトが領域中でつねにそ. 単にオブジェクトと呼ぶ）でもう参照されることのな. の作られた順序（これを生成順序3) と呼ぶ）で並ぶと. い使用済みのオブジェクトを回収し，それらが占めて. いう利点を持つ．これは世代別 GC 4),5) でいうところ. † 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, University of Electro-Communications. ☆. 83. GC が起動したら，その一連の処理が終了するまで他の処理（純計算）が待たされるもののこと．実装が比較的容易で，純計算に対する負荷が少ないといわれる．.

(2) 84. 情報処理学会論文誌：プログラミング. の新古世代のオブジェクト群が連続的に配置されてい. Nov. 2004. 懸案である．. ることを意味する．もう 1 つの利点はヒープ中の使用. 本稿で述べる GC はその解決策として，新世代 GC. 中オブジェクトの分布データなどのミクロ的な情報が. （新世代領域を対象にする GC で，minor collection. GC 処理の過程で副次的にかつ大きな負荷なく得られることである．. とも呼ばれる）を 1 回経験したオブジェクトに対して，そのまま殿堂入りさせるか，再度，新世代 GC の対象. 一般に GC 間で生成される個々のオブジェクトの容. とするかをその分布に基づいて動的に決める．前者は. 量や使用期間などのオブジェクト特性は変化する．そ. GC 1 回で，後者は GC 2 回の経験回数で殿堂入りす. うした実行環境の変化を察知し，次回の GC 処理内容. ることになる．結果的に，新世代領域は見かけ上，拡. を変化に合ったものに変更できる GC は，画一的な処. 大したり縮小したりというように変化する．これは，. 理を行う GC よりも効果的である．本稿で述べる GC. ある程度分かったオブジェクトの特性に基づいて量を. はその処理内容を決める次の 3 つの量や値を動的に変. 変えるのであって，今後作られるであろう未知のオブ. 更することができる．. ジェクト群を「予測」して決めるのではない．したがっ. (1) (2) (3). ソート法の適用対象領域. て，仮にそれらの特性が変化したとしても拡大や縮小. 殿堂入りの閾値. が過度になることも過大に振動することもない．. 新世代領域. 新世代領域の容量は実装対象の計算機の二次キャッ. 使用中オブジェクトのアドレスを大小順にソートし. シュ容量に見合うようにとると，キャッシングが有効. て使用するソート法は圧縮型 GC の高速化6)∼8) の要. に働き，多くの場合，GC 処理を含むプログラムの総. であり，圧縮型 GC の時間計算量を複写型（copying. 処理時間の短縮という効果を生むことが分かっている．. ☆. collection）GC. 9). の時間計算量と同じにする効果を. 新世代領域の拡大は GC 時間の短縮や記憶領域の使用. 持つ．単独の使用中オブジェクトやそれらの連続した. 効率の向上を生むが，二次キャッシュ容量を超えるよ. 塊をクラスタと呼ぶと，アドレスの個数はクラスタの. うな過度な拡大は，キャッシュミスを生み，結果とし. 個数と同じになる．しかし，アドレスの個数の大幅な. て，総処理時間の増加になる恐れもある．新世代領域. 増加はその効果を相殺してしまう．そこで，GC 対象. の容量変更は，占有率のきわめて高いプログラムに対. 領域のうちで，アドレスの少ない部分にソート法を適. して，新世代領域を拡大するように働く．. 用し，残りの部分はオブジェクトの印付け情報のある. 本稿では，これら 3 つの動的変更手法とその評価に. MBT（Mark Bit Table）の該当部分を走査する．後者を MBT 走査法と呼ぶ．. ついて述べる．適応型 GC は PHL（Portable Hashed. 今回の実装では，処理を単純にするために GC 対象. クプログラムを実行した．評価はその結果に基づいた. 領域を 2 分割し，古いオブジェクト群の存在する部分にソート法を，新しいオブジェクト群の存在する部分に MBT 走査法を適用する．理由は，統計的に前者の部分がクラスタ数が少ないと考えられるからである．ソート法と MBT 走査法が適用される境界は今回の. GC で得られたクラスタの分布から次回のそれを決めるという「予測」に基づく動的変更である．殿堂入りとは，ある世代のオブジェクトがそれより. Lisp）翻訳系10) の実行環境下で実装し，ベンチマーものである．. 2. 適応型 GC 実行環境の変化に即応できるような GC は世代別. GC の開発過程で登場した．オブジェクトの生存期間に関する仮説に基づいて殿堂入りなどの処理を行う世代別 GC では，現在処理中のオブジェクトの特性を反映した処理を行う必要があるからである．. 1 つ古い世代のオブジェクトになることである．一般. Ungar らは新世代領域のオブジェクトの殿堂入りを. に，殿堂入りを遅らせると当該オブジェクトに対する. 行う際に，その候補（オブジェクト）がある一定量を超. GC 処理が増え，時間効率を低下させるし，逆に，殿. えたときに古いものから順に殿堂入りさせる GC（de-. 堂入りを早めると死蔵オブジェクト（使用済みでも回せる．その最適な時期をどのように決めるかというこ. mographic feedback-mediated tenuring）11),12) を考案した．実行プログラムで異なる使用中オブジェクト量がある値に到達するまで殿堂入りを待つのである．. とは「殿堂入り問題」として，世代別 GC では長年の. 当然，殿堂入りまでのオブジェクトの GC 経験回数は. 収不能なもの）を増加させ，時間と記憶効率を低下さ. ☆. プログラムにより異なる．この GC は死蔵オブジェクオブジェクトが複数のフィールド（ヒープの 1 語）で構成される場合はその先頭アドレスである．同様に，使用中オブジェクトが連続した塊ではその最古のオブジェクトのアドレスである．. ト（tenured garbage）の回収を行う古世代 GC の頻度を減少させることができるが，各オブジェクトの生.

(3) Vol. 45. No. SIG 12(PRO 23). 実行環境の変化に即応する圧縮型ガーベッジコレクション. 85. 存期間やその量的な把握が必要である．少し時間をおいて，GC 経験回数で殿堂入りの候補を決める GC が考案された．Wilson らの Opportunistic. GC 13) と田中らの Adaptive GC 14) である．新世代領域の一部である生成領域（creation space）に Water Mark という閾値を設け，閾値以内の（比較的古い）オブジェクト群は殿堂入りし，閾値を超えた（比較的新しい）オブジェクト群は新世代領域の保存領域（aging semi-spaces）に移される．これらは次回の GC で殿堂入りする．この GC の利点は，実行プログラムの特性に応じて，殿堂入りの GC 経験回数を 1 から 2 の間で任意に設定できることである．もう 1 つは，オブジェクトの生存期間のモデルに基づいてヒープや新世代領域の容量を自動調整する GC である．オブジェクトの生存分布のような一般的モデ. 図 1 圧縮型 2 世代 GC（殿堂入り条件：GC 経験 1 回） Fig. 1 Two generational GC of mark-and-compact (promotion threshold: GC 1 time).. ルがあればそれに合致するように GC を動作させれば時間的かつ領域的な利得が得られる．吉川らはごみ比率（占有率の逆の意味）のモデルに基づいて，実行プログラムに対して新世代領域のサイズを動的に調整す. わりに空になる．この世代別 GC は最も単純な世代. るような GC 15) を考案した．. 別管理であるが，利得もある程度期待できる．既成. これらの GC はいずれも，ベースモデルが複写型. の GC 16)∼18) では，新世代領域を対象計算機の二次. GC である．また，ある程度の効率の改善はされるが，. キャッシュサイズに合うように設定している．これは. すべてのプログラムに対して万能とはいえない．. ヒープよりもかなり少ない容量である．その理由は，. 3. 高速圧縮型 GC. 頻繁に使用される新世代の領域がキャッシュ記憶に置. ここでは適応型 GC のベースモデルである高速圧縮. 化が期待できるからである．. 型の機能の概略について述べる．. 3.1 2 世代の世代別 GC 図 1 は圧縮型 GC が行う新古 2 世代のデータオブジェクト管理の様子である．新世代 GC はヒープの一. かれれば，キャッシュヒットの効果により処理の高速. 3.2 1 回の GC 対象領域走査 GC 対象領域を走査する回数は 1 回だけである．印付けに MBT などの「外部表」を使用する場合でも，補正表の作成と，使用中オブジェクトの再配置やポイ. 部である新世代領域（図中の new）が消費されたとき. ンタ補正を別個に行うと GC 対象領域は 2 回走査さ. 起動される．使用中オブジェクトはヒープの左側に詰. れることになる．補正表の作成と並行してこれらの作. められ，古世代領域（図中の old）を形成する．世代別. 業を行えば走査回数を 1 回にできる．. GC でいうところの「1 回の GC 経験で殿堂入り」す. 補正表は各小区画の先頭フィールドの補正値（そこ. る．新世代と古世代の境界は可変で，1 つの変数（図. のオブジェクトが再配置で移動する距離）を 1 つのエ. 中の sb）がその位置を決める．次の新世代領域は古世. ントリとして持つ．この補正値と小区画内の印付け情. 代領域に隣接してとられる．. 報☆ で個々のデータオブジェクトの補正値を定数時間. 古世代 GC（major collection とも呼ばれる）が起. で求めることができる．. 動されるのは新古 2 世代の領域が一杯になったときで. 通常，オブジェクトのポインタはそれより古いオブ. ある．GC 対象領域はヒープ全体となる．使用中オブ. ジェクトを指す．「新しいものは古いものから作られ. ジェクトはヒープの左端に詰められて，古世代領域を. る」からである．このようなポインタを逆向きポイン. 形成する．新世代 GC と古世代 GC の違いは単に GC. タと呼ぶ．逆向きポインタは，起点のオブジェクトの. 対象領域が異なる（後者の方が広い）だけである．. 再配置時にそのポインタが指すオブジェクトの再配置. 「1 回の GC 経験で殿堂入り」することは，古世代. 場所を作成中の補正表から求めることができる．そこ. のオブジェクトから新世代のオブジェクトを指すポインタを記録するリメンバードセット5) が各 GC の終. ☆. 実装では MBT の 8 ビット分16) ．.

(4) 86. Nov. 2004. 情報処理学会論文誌：プログラミング. で，補正表の作成と並行してオブジェクトの再配置を. ドレスを順に得る手間は MBT の 0 の（クラスタが存. 行い，逆向きポインタの補正も済ます．しかし，古い. 在しない）エントリを読み続ける手間よりもはるかに. オブジェクトから新しいオブジェクトを指す前向きポ. 少ないはずである．現版では，0 のエントリを読んだ. インタ☆ の補正はその時点ではできない．一般に，前. ら，ソート済みのアドレスを引くようになっている．. 向きポインタの個数は多くないので，それらの基点オ. その後の処理は MBT 走査法に任せられる．これを両. ブジェクトのアドレスを登録しておき，補正表が完成. 者の「ミクロ」的融合と呼ぶ．MBT 走査法とソート. してからポインタ補正が行われる．. 法の優劣は，ソート処理の手間と 0 のエントリを読み. 補正表はオブジェクトの再配置にともない別の使用中オブジェクトが上書きされることを前提に使用するものである．圧縮型 GC でも，上書きされないオブ. 飛ばす手間の大小で決まるといえる．. 4. 動的変更手法. の分布に依存するが，量的に無視できないという報. 4.1 ソート法の適用対象領域新世代領域を 16 に分けた大区画について，新世代. 告19) がある．そこで，こうしたオブジェクトにその. 領域が 1 回走査されるときにそれらの各大区画に存在. 再配置先を指すポインタを埋め込めば，ポインタ補正. するソート対象アドレスのヒストグラムが作られる．. を間接参照というより高速な操作で実行できる．. それらは，ソート法が作成したソート対象アドレスや，. ジェクトは存在する．その量は占有率やオブジェクト. これは複写型 GC で forward pointer と呼ばれてい. MBT 走査法で得られるソート対象アドレスである．. る技法である．当然，この操作でポインタができるオ. 大区画を 16 個にするのは経験則で，これより小さい. ブジェクト群（比較的新しいオブジェクト群）が存在. とデータの緻密性が失われ，逆に大きいと，特異点な. する領域の補正表の作成は不要となる．時間的には，. どの処理上好ましくないデータが現れるからである．. こうしたオブジェクトの量が多いほど，GC 処理時間. ソート法は，統計的にクラスタ数が少ないと見なさ. は短縮される．さらに，CONS は CAR 部，シンボル. れる古いオブジェクト群の存在する部分（図 1 の新世. やベクトルはヘッダ部など，ポインタを埋め込む場所. 代領域の左部分）に，MBT 走査法は残りの部分に適. の洗練化もあるが，こうした事項は本稿の主題ではな. 用される．両者の境界は大区画の 1 つの境界である．. いので，これ以上は述べない．. ただし，初回の GC は MBT 走査法がすべての大区画. 3.3 MBT 走査法とソート法. に対して適用される．. MBT の各エントリは，ヒープ中の連続した 32 語（小区画）の印の情報☆☆ を持つ．印付けを MBT で行. 各大区画を左から右に，0 から 15 で表し，その値で示される大区画から MBT 走査法が適用されるとす. う理由は，オブジェクトの再配置と無関係に印情報が. る．このとき，次回の GC で MBT 走査法が適用され. 保持できることと，印情報に関するメモリ参照が局所. る大区画（bnext ）は，今回の GC で MBT 走査法が. 的になることである．. 適用された大区画（b）と，ヒストグラムの解析で得. MBT 走査法は MBT の各エントリを読み取り，使用済みオブジェクトを飛ばしてクラスタを見つける．. られた値（i）と前回の GC の解析で得られた値 iprev とで次のように決定される．. . 各エントリに対するビット演算を使用すると，同じ小区画内の他のクラスタは容易にかつ比較的高速に求めることができる．すべてのビットが 0 か 1 であるようなエントリは読んで飛ばす（個々のビットは調べな. bnext =. i (i + b)/2. if i = iprev otherwise. 上段の条件は定常状態に早く収束させるためであり，. い）．それでも，すべてのエントリを順に調べるので，. 下段の平均化は急激な変化に対する過度の振動を防止. 時間計算量は GC 対象領域量に比例する．. する．なお，初期値は b = 0 と iprev = 0 である．. ソート法は MBT 走査法を補完する．占有率が小さ. ヒストグラムの解析は 0 の大区画から始めた和が. いか，GC 対象領域にクラスタが散在するような場合. ソート上限数を超えたときの大区画の値を返す．ソー. は，ソート対象となるアドレスの個数も小さく，ソー. ト上限数は処理系に依存する定数であり，ソートの対. トの負荷も少ない．こうしたときは，ソート済みのア. 象となるアドレスの個数の上限を示している．その具体的な値については実験の章で述べる．. ☆ ☆☆. こうしたポインタは SETF などの書き換え操作で生まれる． C 言語の int や unsigned int 型の多くが 32 ビットの 1 語に対応することによる．64 ビット対応の C コンパイラが使用できれば，小区画は 64 語になる．. 4.2 殿堂入りの閾値新世代 GC を 1 回経験したオブジェクトが，そのまま殿堂入りするか，再度，新世代 GC の対象になるか.

(5) Vol. 45. No. SIG 12(PRO 23). 実行環境の変化に即応する圧縮型ガーベッジコレクション. 87. 占有率. 1.0 (3) (1). 0.5 (2) 0. low (old). 新世代領域. -. 図 2 オブジェクト分布 Fig. 2 Objects distribution.. high (new). は，前述の大区画の占有率で決まる．図 2 は新世代領域中の使用中オブジェクトの分布，いいかえれば，. 図 3 新世代 GC Fig. 3 Minor collection.. 大区画あたりの占有率を模式的に示したものである．横軸は新世代領域上の位置を，縦軸は占有率を表す．圧縮型 GC では生成順序が保存されるため，オブジェ. 以下となる．. クトの存在する位置はその新旧に対応している．図で. GC 経験回数が 2 回で殿堂入りさせる場合の GC 処. は右端が最も新しいオブジェクトが存在する領域であ. 理ルーチンの付加的作業は，図 3 (1) のポインタのよ. り，左に行くほど古いオブジェクトが存在する領域と. うに，古世代オブジェクトから新世代オブジェクトを. なる．この図で示された 3 つの分布曲線において世. 指すポインタが存在すれば，それをリメンバードセッ. 代別 GC で効果的に処理できるのは，(1) で示される. トに登録することである．結果として，リメンバード. ような指数分布に近いオブジェクト分布か，(2) で示. セットは空にならないことがある．. されるような底を這うオブジェクト分布である．(3). これに類似した殿堂入りは上野らの GC 18) で実装. のような占有率が高止まりする分布に対しては新世代. されているが，相違点は占有率のサンプリングと閾値. GC の時間的損失が多い．そこで，0 の大区画の占有. の設定法である．前者に関しては比較的緻密であるし，. 率（α0 ）と，15 の大区画の占有率（α15 ）から，次の. 後者については殿堂入りのオブジェクト量が多くなる．. 2 つの条件を満たすときは再度，GC の対象にする． (1) (2). α0 < α15 （両端で分布は右上がり） α0 が閾値基準占有率以下. ここで閾値基準占有率は処理系に依存する定数である．その具体的な値については実験の章で述べる．この条件によれば図 2 の (3) のような分布をする. 4.3 新世代領域前述したように，新世代領域の容量は殿堂入り閾値の変更でも微小に変化する．新世代領域の容量の変更は，つねに占有率が高いプログラムの実行で生じる殿堂入りオブジェクトの量的減少を意図して行われる．これは新世代領域の容量を増やすことで解決される．. オブジェクト群は明らかに殿堂入りとなる．また，占. しかし，新世代領域が実装対象の計算機の二次キャッ. 有率が小さくても，右下がりになるような分布を持つ. シュ容量を超えると，キャッシュミスの増加を招き，総. オブジェクト群も殿堂入りする．オブジェクトの生存. 処理時間の短縮にならないこともある．. 期間に関する仮説に反するからである．これらのオブ. 新世代領域量は実装対象の計算機の二次キャッシュ. ジェクト群が比較的長い生存期間を持つならば，早く. 容量を考慮して設定されている．この容量が増えるの. 殿堂入りした方が好ましいし，そうでなければ新世代. は，α0 （0 の大区画の占有率）の 5 回の平均値（α0 ）. 領域が生成オブジェクトに対して狭すぎることになる．. が拡大基準占有率を超えたときである．拡大基準占有. この動的変更は，図 3 (2) のようにわずかであるが. 率は処理系に依存する定数である．その具体的な値に. 新世代領域を拡大したり縮小したりする．しかし，こ. ついては実験の章で述べる．α0 を使用するのはオブ. の変化は今後作られるであろう未知のオブジェクト群. ジェクトを限定するためであり，平均値を用いるは過. を「予測」して決めているのではない．したがって，. 度の増加を防止するためである．新世代領域は元の q. 仮にそれらの特性が変化したとしても効率が低下する. 倍になるが，それは次のように決められる．. ことはない．また，平均的に見れば，この殿堂入りのタイミングの条件は，GC 経験回数で 1 回以上で 2 回.

(6) 88. Nov. 2004. 情報処理学会論文誌：プログラミング. q=. 1.5. if α0 ≤ 1.5× 拡大基準占有率. 2. otherwise. gcc-2.95.3 である．処理時間の測定は gethrtime() 20) による．ナノ秒単位の時間計測ができるが，MPU 時間そのものを返すので，他のプロセスの影響を極力排除. ただし，α0 < α15 を満たすことが必要である．後. するようにした．もう 1 つは Dell Precision 530（デ. 者は 15 の大区画の占有率の 5 回の平均値である．こ. ルコンピュータ社製）で，1.5 GHz の Intel Xeon を 2. の条件によって，占有率が特に高い場合には急速に容. 個搭載する．二次キャッシュ容量は 256 KB で，主記. 量を拡大することになる．ここで用いている拡大の倍. 憶は 1 GB である．OS は Red Hat Linux 9 で，C コ. 率は経験則から適切と判断した値である．. ンパイラは gcc-3.2.2 である．処理時間の測定はこれ. 5. 実験と評価. も MPU のクロック数を返す rdtsc 命令を利用した．. 5.1 実験環境本 GC を含む各 GC の性能評価は，それらを組み. 数21) のほかはすべて Reduce 22) プログラムである．. 使用したプログラムは，Lisp で書かれた Tarai 関. Tarai-6 list ver. はリストを引数とする Tarai 関数で. 込んだ PHL 翻訳系の実行環境下で行い，言語やその処理系の特性に依存しない普遍的な結果を得ることを目標とした．こうした環境では，純粋に機械語のプロ. ある．整数の大小をリストの長短に対応させることで長大な再帰計算を行うものである．. Reduce は A.C.Hearn 教授らが開発した数式処理シ. グラムが生成するデータオブジェクトのみが GC の. ステムで，不定積分や因数分解のパッケージを除いた. 対象になるからである．なお，PHL は可搬性のある. 基本部分は Lisp ソースにして約 4000 行，翻訳すると. Lisp 処理系で，これまでに，SPARC，Alpha，MIPS， Pentium，MC68000 などの命令セットアーキテクチャを持つ計算機で稼働している．. 約 600 KB（UltraSPARC）になる．Reduce プログラ. 今回使用した計算機は Sun Fire 280R（Sun Mi-. ムは，Reduce が読み込み，解釈し，結果を出力するという形式で実行される．この実行過程で生成されるオブジェクトの特性は数式や計算内容で大きく変わる．. crosystems 社製）で，900 MHz の Ultra SPARC-III. 個々のプログラムでは，Differential は多項式の数式. Cu を 2 個搭載する．二次キャッシュ容量は 8 MB で，主記憶容量は 4 GB である．オペレーティングシステム（OS）は日本語 Solaris8 である．C コンパイラは. 微分，F and G series 33 は F&G 系列の 33 項までの算出，Fourier analysis はフーリエ解析計算，Matrix. 6×6 は Matrix は 6 行 6 列の逆行列の算出とその検. Tarai–6 by lists. Fourier analysis. 1000. 10 r r r r r r. 8 6 4 2 r. r r r r r r r r r r r r r r 0 r r r r r r r r r r r r r r r 2 0 4MB. 600 400. r. r. r r r 200 rrr r rr rr rr rrr r 0 r r 0. Matrix 6×6. 1000 800 600 r. r. 400 200. r r rr r rr r r 0 r r r r r 0. r rrr r. r rr. r rr r. r rrr 2. r r r r rrr. r r r r rr. rr r r rr rr. r r r rr rr. r r rr rrr. r r rrr r. r r rr rr r. r r r r rr r rr. r. rr r r r r rr. r r r r rr r rr rr r rr. 2. r r rr rrr r. r r r rr r. r rr r rrr rrr. 4MB. Bignum vectors. r r r r r r r. rr. r. r. 800. r r r rr. rr rrr. r r r r r rrr r. r r r rr r r rr r. r r rr r rrr rr r rrr. r rr rr r r rr r r rr r rr r rr rr rr rr 4MB. 1000 800 600 400 r. rr r rr r r r r r r r r r r r r r 0 2 0. 200. 図 4 クラスタ分布 Fig. 4 Cluster distribution.. rrr rrr rr r. r r r r rrrr r rrr r. rrr rr rrr r r 4MB.

(7) Vol. 45. No. SIG 12(PRO 23). 89. 実行環境の変化に即応する圧縮型ガーベッジコレクション. 算，Bignum vectors は多倍長整数計算である．新世代領域は特に記述のない限り Sun Fire 280R で. 4 MB（ヒープの半分），Dell P530 で 512 MB である． 5.2 MBT 走査法とソート法図 4 は 4 つの代表的なプログラムにおけるクラス. 表 1 処理時間の比較（1） Table 1 Comparison of processing time (1).. α. Program Tarai-6 by lists. 0.3m. Fourier analysis. 0.04. F and G series. 0.06. Differential. 0.09. Matrix 6×6. 0.11. Bignum vectors. 0.13. タ分布である．横軸は各大区画に対応した新世代領域上の位置である．先に述べたように，圧縮型 GC においてはオブジェクトの存在する位置はその新旧に対応している．右端が最も新しいオブジェクトが位置する領域であり，左に行くほど古いオブジェクトが存在する領域となる．縦軸は個数である．個数が同じならば. 1 点に凝縮する．実線は平均値を結んだものである． Tarai や Bignum はオブジェクトの生存期間の仮説に示される指数分布に近い．Matrix も指数分布に近いが，全体としてなだらかな分布である．Fourier は起伏があるが，平均すれば平らな分布である．表 1 はソート対象アドレスの個数が既定値（a）を超えない範囲でソート法を適用したときのプログラム総処理時間（T）と GC 処理時間（Tgc）である．各プログラムの最上段と最下段はそれぞれ，ソート法と. MBT 走査法を単独で適用した場合である．結果的には，2 つの方法を「マクロ」的に融合した方が時間的に良い結果が得られている．この表を見る限り，ソート上限数には 200 を採用しても異存はないように思われる．使用した計算機は Sun Fire 280R である．表 2 は，計算機を Dell Prcision 530 に変更したときの実験データである．融合例はソート上限数を 200 とした場合が代表として記載してある．表 2 の R は両者の総処理時間（T）の比率である．R が大きいほど，Sun の場合に比べて処理速度が速い．その値は. 6 種のプログラムによって大きく異なる．Fourier と Differential では Sun の場合よりも遅くなっている． 5.3 殿堂入り表 3 は閾値基準占有率を 0.1（C1）と 0.2（C2）にしたときのプログラム総処理時間（T）と GC 処理時間（Tgc）である．C2 の方が殿堂入りするオブジェクトが少ない．同じく cond. 欄にある，1 と 2 は殿堂入りの GC 経験回数をすべて 1 と 2 に固定した場合である．各欄の上段と下段は，ソート法を単独で適用し. クト分布で殿堂入りのタイミングを切り替えた方が，時間的に良い結果が得られるプログラムが多い．また，ソート法と MBT 走査法を融合した方（下段）が良く，. Tgc 0.011 0.009 0.009 0.010 0.021 0.106 0.104 0.104 0.104 0.103 0.103 0.093 0.095 0.094 0.097 0.135 0.119 0.117 0.125 0.124 0.874 0.806 0.785 0.802 0.793 0.251 0.238 0.236 0.234 0.236. Tm 0.007 0.006 0.007 0.007 0.016 0.063 0.064 0.060 0.060 0.060 0.072 0.061 0.064 0.062 0.065 0.096 0.073 0.073 0.075 0.083 0.560 0.506 0.484 0.496 0.480 0.195 0.167 0.148 0.180 0.181. s 16 16 16 15 0 16 12 3 2 0 16 13 4 2 0 16 10 3 1 0 16 14 12 10 0 16 14 14 13 0. 表 2 処理時間の比較（2） Table 2 Comparison of processing time (2).. Program Tarai-6 by lists Fourier analysis F and G series Differential Matrix 6×6. 欄の再掲である．一般に，GC 経験回数を固定するよりも，オブジェ. T 3.12 3.12 3.12 3.12 3.19 19.6 19.1 19.1 19.1 19.4 9.9 9.6 9.6 9.6 9.8 25.6 25.5 25.5 25.5 26.0 21.7 21.6 21.5 21.6 21.8 16.9 16.8 16.8 16.8 17.0. （注）α は占有率，a はソート上限数，T は総処理時間，Tgc と Tm は GC 時間と印付けの処理の時間，s はソート対象となった区画数の平均値（総区画数は 16），m は千分の一を表す，処理時間の単位は秒，計算機は Sun Fire 280R．. た場合とソート上限数 200 でソート法と MBT 走査法を融合した場合である．cond. 欄の 1 は表 1 の該当. a — 1000 200 100 0 — 1000 200 100 0 — 1000 200 100 0 — 1000 200 100 0 — 1000 200 100 0 — 1000 200 100 0. Bignum vectors. a — 200 0 — 200 0 — 200 0 — 200 0 — 200 0 — 200 0. T 1.58 1.58 1.66 27.2 27.2 27.5 7.0 6.9 7.1 36.6 36.4 36.7 10.9 10.9 10.9 8.7 8.7 9.0. Tgc 0.013 0.010 0.020 0.080 0.077 0.077 0.065 0.064 0.065 0.095 0.085 0.087 0.766 0.663 0.546 0.154 0.157 0.163. Tm 0.011 0.010 0.011 0.046 0.039 0.039 0.042 0.038 0.039 0.055 0.043 0.044 0.542 0.431 0.413 0.119 0.123 0.127. R 2.0 2.0 1.9 0.72 0.70 0.71 1.4 1.4 1.4 0.70 0.70 0.71 2.0 2.0 2 1.9 1.9 1.9. （注）R は Sun Fire 280R に対する処理速度比，計算機は Dell P530，ほかは表 1 と同じ．.

(8) 90. Nov. 2004. 情報処理学会論文誌：プログラミング表 3 処理時間の比較（3） Table 3 Comparison of processing time (3).. Program. cond. 1. P 0.3. Tarai-6 by lists. C1,C2. 0.07. 2. 0.04. 1. 43. C1,C2. 27. 2. 24. 1. 63. C1. 54. C2. 52. 2. 52. 1. 91. C1,C2. 74. 2. 58. 1. 88. C1. 23. C2. 23. 2. 21. 1. 123. C1. 2.3. Fourier analysis. F and G series. Differential. Matrix 6×6. Bignum vectors. C2,2. 1.1. T 3.12 3.12 3.11 3.13 3.19 3.18 19.6 19.1 19.0 19.0 19.8 18.8 9.9 9.6 9.8 9.7 9.9 9.8 10.0 9.8 25.6 25.5 25.6 25.5 27.0 26.3 21.7 21.5 21.5 21.4 21.5 21.5 21.6 21.6 16.9 16.8 16.8 16.8 16.8 17.0. Tgc 0.011 0.009 0.015 0.016 0.016 0.015 0.106 0.104 0.125 0.155 0.140 0.177 0.103 0.095 0.123 0.126 0.150 0.137 0.156 0.164 0.135 0.117 0.150 0.161 0.173 0.349 0.874 0.785 0.941 0.875 0.956 0.864 1.009 0.966 0.251 0.236 0.260 0.241 0.260 0.237. N2 :N1 (s) 0 : 33 (15.2) 31 : 2 (15.3) 33 : 0 (15.5) 0 : 18 (3.2) 11 : 7 (3.2) 18 : 0 (3.2) 0 : 14 (3.8) 6: 8 (3.9) 11 : 3 (4.0) 14 : 0 (4.4) 0 : 11 (2.9) 4: 7 (3.0) 11 : 0 (3.0) 0 : 67 (11.9) 57 : 10 (10.3) 58 : 9 (10.3) 67 : 0 (10.3) 0 : 28 (13.9) 26 : 2 (14.1) 28 : 0 (14.1). （注）Program 欄の上段と下段はソート法（単独）と融合（a=200）， condition は殿堂入りの条件，P は殿堂入りオブジェクト量の平均値（単位は K 語），N2 : N1 は GC の回数比，ほかは表 1 と同じ．. 表 4 処理時間の比較（4） Table 4 Comparison of processing time (4).. Program. C 4. Fourier analysis. 1 0.5 4. Differential. 1 0.5 4. Bignum vectors. 1 0.5 (0.5). α 0.06 0.06 0.09 0.10 0.11 0.12 0.10 0.13 0.14 0.16 0.14 0.18 0.11 0.11 0.40 0.32 0.57 0.65 0.23 0.25. P 27.8 24.4 13.1 11.0 7.8 7.0 74.2 57.8 22.8 21.8 13.3 11.9 2.3 1.1 48.6 40.9 73.8 38.4 13.8 11.4. T 27.2 27.0 26.6 25.7 26.1 25.3 36.7 36.8 31.7 31.3 30.9 30.2 8.62 8.68 9.07 9.06 9.46 9.54 8.99 8.84. Tgc 0.097 0.099 0.139 0.159 0.173 0.195 0.112 0.140 0.142 0.177 0.150 0.175 0.123 0.126 0.486 0.476 0.696 0.917 0.133 0.144. （注）Program 欄の上段と下段は表 3 の C1 と 2 の条件の版．C は規定値（単位は MB），α は占有率，ほかは表 3 と同じ．. である．Program 欄の上段と下段は殿堂入りの条件が異なり，上段が C1 で，下段が GC 経験回数が 2 回である．Bignum の最下段は新世代領域が増加する場合である．拡大基準占有率は 0.2 としている．最終的に 2 MB まで増加するが，T と S は C=1 に固定した場合よりも短縮される．. Fourier や Differential のようなプログラムは新世代 GC を積極的に行って，ワーキングセットを小さくすると時間短縮の効果がでる．逆に，Bignum のようなプログラムは新世代領域を比較的大きくしないと，. GC 処理時間の増加が総時間を押し上げることになる．. 6. おわりに本稿では，圧縮型 GC の特性を利用した適応型 GC を提案した．圧縮型 GC では，GC 対象領域のオブ. 相乗効果が現れている．表 3 中の N2 : N1 は，新世代オブジェクト群が再度 GC の処理を受けた回数と，即時に殿堂入りした. ジェクトの詳細な分布情報を，その処理の過程において容易に得ることができる．本 GC では，ソート法と MBT 走査法を併用し，ソー. GC の回数の比である．6 種のプログラムの中では， C1 と C2 の場合でその比率が変わるものも変わらないものもある．（s）は表 1 の s である．使用した計算. ト対象アドレスの分布情報に基づいて両者を適用する. 機は Sun Fire 280R である．. することも行う．これらの手法を Lisp 処理系に実装. 範囲を動的に調節する．また，殿堂入りの閾値と新世代領域の大きさを，占有率の分布情報に基づいて調節. 5.4 新世代領域. して実験した結果，動的変更を行うことによって処理. 表 4 は，新世代領域量を指定値（C）に設定したとき. 時間が短縮されることが確認できた．. のプログラム総処理時間（T）と GC 処理時間（Tgc）. 今後，取得した分布情報の分析方法を改良すること.

(9) Vol. 45. No. SIG 12(PRO 23). 実行環境の変化に即応する圧縮型ガーベッジコレクション. によって，さらなる性能向上も期待できる．こうした情報を動的変更に利用できることは，圧縮型 GC の大きな利点となりうる．. 参. 考文. 献. 1) Wilson, P.R.: Uniprocessor Garbage Collection Techniques, Technical Report, University of Texas, Tex. (1994). 2) Jones, R. and Lins, R.: Garbage Collection, John Wiley & Sons, UK. (1996). 3) Terashima, M. and Goto, E.: Genetic Order and Compactifying Garbage Collectors, Information Processing Letters, Vol.7, No.1, pp.27– 32 (1978). 4) Lieberman, H. and Hewitt, C.: A Real-time Garbage Collector based on the Lifetimes of Objects, CACM, Vol.26, No.6, pp.419–429 (1983). 5) Ungar, D.M.: Generation Scavenging : A Nondisruptive High Performance Storage Reclamation Algorithm, ACM Conference on Practical Programming Environments, pp.157–167 (1984). 6) Suzuki, M., Koide, H. and Terashima, M.: MOA — A Fast Sliding Compaction Scheme for a Large Storage Space, IWMM95, LNCS 986, pp.197–210, Springer-Verlag (1995). 7) Chung, Y.C., et al.: Reducing Sweep Time for a Nearly Empty Heap, POPL ’00, ACM, pp.378–389 (2000). 8) Terashima, M., Ishida, K. and Nitta, H.: The Design and Analysis of the Fast Sliding Compaction Garbage Collection, Advanced LISP Technology, Taylor & Francis, N.Y. (2002). 9) Fenichel, R.R. and Yochelson, J.C.: A Lisp Garbage Collector for Virtual Memory Computer Systems, CACM, Vol.12, No.11, pp.611– 612 (1969). 10) 寺島元章，山本洋司，古川敦司，渡辺美苗：PHL の新コンパイラ，記号処理研究会資料 SYM 78， pp.17–24, 情報処理学会 (1995). 11) Ungar, D. and Jackson, F: Tenuring Policies for Generation-based Storage Reclamation, ACM SIGPLAN Notices, Vol.23, No.11, pp.1– 17 (1998). 12) Ungar, D. and Jackson, F: An Adaptive Tenuring Policy for Generation Scavengers, ACM Trans. Programming Languages and Systems, Vol.14, No.1, pp.1–27 (1992). 13) Wilson, P.R. and Moher, T.G.: Design of the Opportunistic Garbage Collector, ACM OOPSLA’89, SIGPLAN Notices, Vol.24, No.10, pp.23–35 (1989).. 91. 14) 田中詠子，田中良夫，中西正和：Adaptive Garbage Collection — 実装とその評価，電子情報通信学会誌，Vol.J79-D-1, No.5, pp.253–260 (1996). 15) 吉川隆英，近山隆：効率のモデルに基づきヒープサイズを自動調整する世代 GC 方式，情報処理学会論文誌：プログラミング，Vol.41, No.SIG9(PRO 8), pp.78–86 (2000). 16) 佐藤圭史，寺島元章：圧縮型ガーベッジコレクションの高速化，情報処理学会論文誌，Vol.40, No.5, pp.2397–2403 (1999). 17) 宮本崇生，寺島元章：ハイブリッドガーべッジコレクションの実装と評価，情報処理学会論文誌：プログラミング，Vol.40, No.SIG7(PRO 4), pp.24–31 (1999). 18) 上野真由子，山室弥久，寺島元章：圧縮方式による世代別ガーべッジコレクションの実装について，情報処理学会論文誌：プログラミング，Vol.43, No.SIG1(PRO 13), pp.1–9 (2002). 19) 寺島元章，新田寛：圧縮型ガーベッジコレクションの高速化について，情報処理学会プログラミング研究会発表資料 (Oct. 2003). 20) Mauro, J. and McDougall, R.: Solaris Internals, Prentice Hall (2001). （福本秀ほか訳）： SOLARIS インターナル，ピアソン・エデュケーション． 21) Okuno, G: The Report of the 3rd Lisp Contest and the first Prolog Contest, 情報処理学会研究報告 85-SYM-33 (1985). 22) Hearn, A.C.: REDUCE User’s Manual, version 3.4, The Rand Corporation, CA. (1988). (平成 15 年 12 月 20 日受付) (平成 16 年 2 月 24 日採録) 新田. 寛. 昭和 46 年生．平成 15 年電気通信大学大学院情報システム学研究科博士後期課程を単位取得済退学．平成. 16 年同研究科で博士（工学）の学位を取得．プログラミング言語処理系における記憶管理方式に興味を持つ．.

(10) 92. 情報処理学会論文誌：プログラミング. 寺島元章（正会員）昭和 23 年生．昭和 48 年東京大学理学部卒業．昭和 50 年同大学院修士課程，昭和 53 年同博士課程修了．理学博士．昭和 53 年電気通信大学計算機科学科助手．現在，同大学院情報システム学研究科助教授．プログラミング言語とその処理系，記憶管理に興味を持つ．ACM 会員．. Nov. 2004.

(11)