圧縮型ガーベッジコレクションの高速化について

• Item type: Trans(1)
• 公開日: 2004-05-15
• タイトル: 圧縮型ガーベッジコレクションの高速化について
• タイトル / 言語: en
• タイトル: Fast Mark -and- compact Garbage Collection
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, University of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, University of Electro - Communications
• 著者名: 新田, 寛; 寺島, 元章
• 著者名(英): Hiroshi, Nitta; Motoaki, Terashima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 圧縮型ガーベッジコレクション（mark-and-compact GC）の処理の高速化に使用した技法とその評価について述べる．古典的な圧縮型GC はその処理時間がGC対象領域の容量に比例することから，使用中オブジェクト量が少ない場合や大きな記憶領域を使用する場合は複写型GCよりも時間的に劣勢にあると見なされてきた．最近の圧縮型GCは使用中オブジェクトあるいはその塊（クラスタ）のアドレスをソートすることで複写型GCとほぼ同じ時間量で処理を行うことができる．この種の圧縮型GCでも，印付けやポインタ補正，ソート処理のために複写型よりも多くの処理時間を要する．本稿では，ソート対象データの個数を減らすことと，ポインタ補正を効率的に行うことでさらなる高速化が得られることを示す．前者はソートの処理だけでなく，印付け処理の負荷も軽減できる．後者は時間的かつ領域的な利得を生む．これらの高速化技法により，比較的大きな容量のヒープでも圧縮型GCが効果的に使用できるようになった．また，GC処理時間がプログラムの実行に要する総処理時間の長短に必ずしも直結しないことも示す．圧縮型GCが複写型GCと比べて総処理時間では優位になるプログラムが多くある．これは圧縮型GCの利点である位置に関する局所性の保存と固定容量記憶に対する効率性の良さに起因するものと考えられるが，こうした解析結果についても述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this presentation, we describe garbage collection (GC) schemes used in an implementation of fast mark-and-compact GC and its effects. The traditional mark-and-compact was regarded as inferior to copying GC in its execution time in case of few objects being in use or a large storage space, because the execution time of mark-and-compact GC is proportional to the size of storage space being processed. The mark-and-compact GC that has been developed recently can process its task with the same time complexity as the copying GC by means of an effective technique that sorts address data of objects in use (or clusters made of these objects). Nevertheless such mark-and-compact GC requires more time than the copying GC, due to its phases of marking, sorting and pointer adjustment that are costly in time. We point out that the speed-up of the mark-and-compact GC described above can be performed by decreasing the number of data being sorted and refining a scheme of the pointer adjustment. The former has a good effects on the execution time of both marking and sorting phases, and the latter does on both time and space. They enables the mark-and-compact GC to use a large size heap. The execution time of GC does not necessarily have much effect on the total time of program execution. The mark-and-compact GC the total time of many programs shorter than the copying GC. This fact may result from the merits of the mark-and-compact GC: locality of data objects in the heap and efficiency of the heap utilization.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 45, 号 SIG05(PRO21), p. 26-35, 発行日 2004-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会