効率的なビットマップマーキングを用いた Ruby用ごみ集め

2008-3-(1): 情報処理学会プロ グ ラ ミ ン グ 研究会 発表資料 2008 年 10 月 28 日
1
効率的なビットマップマーキングを用いた Ruby 用ごみ集め実装
中
村
成
洋†1
松
本
行
弘†1
Apache HTTP サーバの元で提供さ れる Web サービ ス のよ う な ひんぱんにサブプロ セス が生成
さ れる 環境下では， 現在 Ruby が採用し ている マーク ビ ッ ト を オブジェ ク ト ヘッ ダ内に持つマーク ス
イ ープ方式のゴ ミ 集め実装は， copy-on-write によ る メ モリ ページ共有を 疎外し ， 必要以上にメ モリ
を 消費する ． 本研究では， マーク を オブジェ ク ト ヘッ ダ内から 独立し たビ ッ ト マッ プに移すこ と によ
る メ モリ 消費量実行性能の変化を 示す． 効率的なビ ッ ト マッ プマーキ ン グ のためにはオブジェ ク ト ポ
イ ン タ から ビ ッ ト マッ プの特定の位置の計算が必要であ る ． 一般的にはビ ッ ト マッ プ位置を たと え ば
1MB バイ ト 単位でア ラ イ ン し ておき ア ド レ ス を マス ク する こ と でビ ッ ト マッ プ位置を 求める こ と が
行われている ． し かし ， Ruby のよ う に種々のプラ ッ ト フ ォ ーム で動作する 言語処理系では， 利用で
き る メ モリ 割り 当て API は malloc() し かないため， 効率良く アラ イ ン さ れたメ モリ を 確保する 方法
は知ら れていない． 本研究では Ruby のオブジェ ク ト 配置方式を 利用し ， 移植性を 維持し たま ま ， オ
ブジェ ク ト ポイ ン タ から 定数時間でビ ッ ト マッ プ位置を 計算する 手法を 提案する ． ま た， ニ分検索を
用いたビ ッ ト マッ プマーキ ン グ と 比較し たマーキ ン グ 性能の改善も 示す．
Ruby Garbage Collection Using Efficient Bitmap Marking
Narihiro Nakamura†1 and Yukihiro Matsumoto†1
Since mark-and-sweep garbage collection scheme, which Ruby interpreter uses modifies
every living object, it suffers performance problems due not to utilize copy-on-write memory page sharing among processes, under the circumstances like web-services running under
Apache HTTP servers. In this paper, we proposes adding bitmap marking for Ruby’s garbage
collection. We show much memory usage and performance change by bitmap marking. For
efficient bitmap marking, it is needed to calculate bitmap position from an object pointer.
Prior art uses aligns heap memories and pointer masking to retrieve bitmap position from
object pointer. But Ruby interpreter runs on various platforms, and we do not have portable
memory allocation API to obtain aligned memory region without wasting region. In this paper, we propose portable scheme to map from object pointers to corresponding bitmap table
in constant time. We also show how much proposed bitmap marking improves performance,
comparing bitmap marking method using binary search to obtain bitmap position from object
pointers.
なプロ セス では， 省メ モリ 化は重要な要素であ る ． そ
1. は じ め に
こ で筆者ら はス ク リ プト 言語であ る Ruby に注目し ，
近年， ス ク リ プト 言語は様々なシーン で見かける よ
う になっ た． こ れは， ス ク リ プト 言語が技術者にと っ
省メ モリ 化に取り 組んでいる ．
言語で記述さ れている ． 多く のユーザを 抱える 大規模
Web ア プリ ケ ーショ ン において ， メ モリ を 大量に
消費する 原因は， 言語内のガーベジコ レ ク ショ ン (以
下 GC) が一つの原因であ る と 考え る ．
現在， Ruby では GC にシン プルなマーク ス イ ープ
な Web ア プリ ケ ーショ ン が Perl， Ruby3) の様な ス
方式を 採用し ている ． こ れは， オブジェ ク ト の参照ルー
ク リ プト 言語で書かれて いる と いう のは珍し く な い．
ト から ， 生き て いる 全て のオブジェ ク ト に 1bit の印
こ れから も ， 多く の Web ア プリ ケ ーショ ン はス ク リ
付けを し ， 最後に印付けがさ れていないオブジェ ク ト
プト 言語で書かれる であ ろ う ．
を 解放する GC のア ルゴ リ ズム であ る ．
て扱いやすく ， 生産性が高いためであ る ．
1)2)
現在， 多く の Web ア プリ ケ ーショ ン はス ク リ プト
し かし ， その場合， 問題点は多く あ る ． その一つが
し かし ， こ の方式は copy-on-write4) によ る メ モリ
メ モリ の大量消費であ る ． 常駐する Web サーバの様
共有を 阻害する 問題がある ． 通常 Linux ではサブプロ
†1 (株) ネッ ト ワ ーク 応用通信研究所
Network Applied Communication Laboratory Inc.
セス 生成時に， メ モリ 空間を すべてコ ピ ーし ない． 多
く のメ モリ 空間を 親プロ セス と 共有する ． 共有さ れて
2
いる メ モリ 領域が， サブプロ セス にコ ピ ーさ れる タ イ
ブジェ ク ト の配列 (以下ヒ ープス ロ ッ ト ) を 作成す
ミ ン グ は， そのメ モリ 領域に書き 込みがあっ たタ イ ミ
る ． 現在， オブジェ ク ト のサイ ズ はすべて 20byte
ン グ (変化する 際) である ． こ れを ， copy-on-write(以
下 CoW) と 呼ぶ．
つま り ， オブジェ ク ト に対し て， 印付けを 行う マー
であ る ．
( 2 ) 確保し た 16KB のメ モリ 領域で， オブジェ ク ト
サイ ズの倍数のアド レ ス から ヒ ープス ロ ッ ト と し て
ク ス イ ープ方式は， CoW と 非常に相性が悪い． なぜ
使用する ． つま り ， 20byte でアラ イ ン を 行う ． こ れ
なら ， マーク ビ ッ ト の操作によ り そのページ全体がコ
によ り 注意すべき 点は， 確保し たメ モリ のアド レ ス
ピ ーさ れる から である ． こ の事によ り ， ApacheHTTP
によ っ ては， 配列内に定義さ れる オブジェ ク ト の個
サーバ
5)
の様な頻繁にサブプロ セス を 生成する 環境の
元では， う ま く メ モリ 共有でき ず、 多く のメ モリ 空間
が無駄に確保さ れる 事になる ．
こ れを 軽減する 手法がビ ッ ト マッ プマーキ ン グ 6) で
ある ． こ の手法では， オブジェ ク ト に直接マーク せず，
ビ ッ ト マッ プと 呼ばれる 専用の領域にオブジェ ク ト を
マッ ピ ン グ し ， そこ にマーク を 行う こ と で， メ モリ を
数が 1 つ減る 事があ る と いう 点であ る (図 1)．
( 3 ) ヒ ープス ロ ッ ト を 構築し たのちに， フ リ ーリ ス
ト と 呼ばれる リ ス ト に配列内の要素を リ ン ク し てお
く ． 処理系から 使用割り 当ての要請があ っ た際にフ
リ ーリ ス ト から ， 一つだけオブジェ ク ト を 取り 出し ，
初期化を 行う ．
ジェ ク ト のポイ ン タ から ビ ッ ト マッ プ位置を 探索し な
( 4 ) フ リ ーリ ス ト が尽き る と ， マーク 処理を 開始す
る ． マシンス タ ッ ク や CPU レ ジス タ など の領域から
オブジェ ク ト への参照であ る ルート を 発見し ， その
ルート から オブジェ ク ト の参照関係を 再帰的にマー
ク する ． マーク キ ン グ ではオブジェ ク ト 内の flags
ければなら ない． こ の処理は， 一定時間であ り ， かつ
のマーク ビ ッ ト を 1 にし ている ． こ れで現在利用し
高速であ る こ と が求めら る ． なぜなら ， マーキ ン グ 処
ている オブジェ ク ト にはすべて印付けが行われた事
理は生き ている オブジェ ク ト すべてに対し て行われる
になる ．
( 5 ) ス イ ープ時にはヒ ープ内のを すべてのオブジェ
ク ト を 探索し ， マーク さ れて いた オブジェ ク ト は，
コ ン パク ト に使用し ， メ モリ 共有を 阻害し にく いと い
う 利点があ る ．
ビ ッ ト マッ プマーキ ン グ では， マーク する 際， オブ
処理であ り ， 処理系にと っ てボト ルネッ ク の部分であ
る から だ．
ま た， Ruby はさ ま ざ ま なプラ ッ ト フ ォ ーム で動作
マーク ビ ッ ト を 0 に戻し ， マーク さ れていないオブ
し ている ． こ の様に多く のプラ ッ ト フ ォ ーム で動作す
ジェ ク ト は回収し ， フ リ ーリ ス ト につなぐ ．
る アプリ ケ ーショ ン では， プラ ッ ト フ ォ ーム に依存し
こ れでマーク ス イ ープは終了と なる ．
ないポータ ブルなビ ッ ト マッ プ位置探索手法が求めら
れる ．
こ のよ う に Ruby ではシン プルな保守的なマーク ス
本研究では， その様な要求を 満たすビ ッ ト マッ プ位
置探索手法を 提案する ． ま た， それを 利用し たビ ッ ト
マッ プマーキ ン グ を Ruby に実装する ．
2. Ruby のメモリ管理
こ の章では現在の Ruby のメ モリ 管理方法と 問題点
について簡単に述べる ．
2.1 Ruby のマークスイープ方式 GC
Ruby では， 生成さ れる オブジェ ク ト や文字列など
イ ープ 7) が実装さ れている ．
2.2 マークスイープによるメモリ共有の阻害
近年， 簡単に素早く Web ア プリ ケ ーショ ン を 作成
でき る と いう 特性を も っ た ， RubyOnRails8) と いう
Ruby の Web フ レ ーム ワ ーク が誕生し ， Web サービ
ス で Ruby を 使用する 例が非常に多く なっ ている ．
その場合， 多く の Web サービ ス では， HTTP サー
バに ApahceHTTP サーバを 使用し て いる ． Apache
は安定し ており ， 性能も 優れた HTTP サーバであ る
のデータ は Ruby で独自に管理し ている ヒ ープ領域に
から だ． し かし ， Apache と Ruby を 組み合わせる と ，
確保さ れる ． そのため， GC はその領域を 対象と し て
あ る 問題が発生する ．
行われる ．
Apache では， ク ラ イ ア ン ト 通信を 行う 際に， 頻繁
以下に Ruby のメ モリ 管理の大ま かな動作を 記述す
にサブプロ セス の生成を 行う ． Linux カ ーネルではサ
る ． ま た， Ruby(1.9.0-4) のヒ ープ構造を 図 1 に示す．
ブプロ セス 生成時に， 親プロ セス で使用し て いた メ
(1)
モリ 空間を 複製し ない． 親プロ セス にて使用し ていた
malloc にて 16KB のメ モリ 領域を 確保し ， オ
メ モリ 空間を すべて共有し ， 書き 込みが発生し た場合
3
図 1 Ruby のヒ ープ構造
Fig. 1 Heap struct in Ruby
に初めてサブプロ セス に複製さ れる ． こ れが CoW で
ある ．
し かし ， こ の CoW と 現在 Ruby のマーク ス イ ープ
GC と は非常に相性が悪い． なぜなら ， すべての生き
ている オブジェ ク ト のマーク ビ ッ ト を 立てる 際に， 共
有さ れている ページに書き 込みを 行い， サブプロ セス
への複製が発生する から であ る ．
こ れを 改善する 手法と し てビ ッ ト マッ プマーキ ン グ
と いう 手法があ る ． オブジェ ク ト のマーク ビ ッ ト のみ
を 別の領域 (ビ ッ ト マッ プ ) に移し ， オブジェ ク ト の
生存， 死亡はそのビ ッ ト マッ プにて管理する 手法であ
る ． こ の手法を 使用する と ， マーク 時に直接オブジェ
ク ト を 扱う こ と がなく なり ， 無駄な複製を 抑える 事が
図 2 ア ラ イ ン さ れたメ モリ 領域を 利用し た定位置探索
Fig. 2 The fixed position search by aligned memory area
でき る ．
こ の 手法で Ruby の GC を 改善する 事に よ っ て ，
CoW にう ま く 対応し ， サブプロ セス 動作時のメ モリ
消費量を 抑え る 事が可能になる ． つま り ， Apache の
環境で動く ， Ruby を 使用し た多く の Web アプリ ケー
ショ ン が省メ モリ で動作する よ う になる ．
3. Ruby へのビットマップマーキングの実装
こ の章では， 従来のビ ッ ト マッ プ位置の探索の手法
と ， 本研究で提案する 新し い手法を 示す．
3.1 アラインされたメモリ領域の確保によるビッ
トマップ位置の探索
ビッ ト マッ プマーキングを 行う 際， オブジェ ク ト のポ
イ ン タ から ビッ ト マッ プの位置を 探索する 必要がある ．
Ruby において， も っ と も 簡単な方法は各オブジェ
ク ト にビ ッ ト マッ プへのポイ ン タ を 持たせる こ と であ
る ． し かし ， こ れではオブジェ ク ト のポイ ンタ のフィ ー
ルド 分メ モリ 領域を 圧迫する こ と になり ， 今回の目的
であ る 省メ モリ 化の意味がなく なる ．
オブジェ ク ト にフィ ールド を 追加せずに， ビッ ト マッ
プ位置を 探索する 手法の一つと し て， アラ イ ン さ れた
メ モリ 領域を 利用する 方法があ る ．
4
static inline struct heaps_slot *
find_heap_slot_for_object(RVALUE *object)
{
int i;
for (i = 0; i < heaps_used; i++) {
struct heaps_slot *heap = &heaps[i];
if (object >= heap->slot
&& object < heap->slot + heap->limit)
return heap;
}
return NULL;
}
static inline struct heaps_slot *
find_heap_slot_for_object(
rb_objspace_t *objspace,
RVALUE *object)
{
int i;
register size_t hi, lo, mid;
lo = 0;
hi = heaps_used;
while (lo < hi) {
mid = (lo + hi) / 2;
struct heaps_slot *heap = &heaps[mid];
if (heap->slot <= object) {
if (object < heap->slot + heap->limit) {
return heap;
}
lo = mid + 1;
}
else {
hi = mid;
}
}
return NULL;
図 3 線型探索によ る ビ ッ ト マッ プ位置探索
Fig. 3 BitMap position search by liner
例え ば， 1MB ア ラ イ ン で確保し たメ モリ 領域内に
オブジェ ク ト を 配置し ， 確保し たメ モリ 領域の先頭に
はビ ッ ト マッ プへのポイ ン タ を 設定し ておく ． そし て，
ビ ッ ト マッ プ位置を 探索する 際には， オブジェ ク ト ポ
イ ン タ の下位 20bit を 0 でマス ク し ， アラ イ ン さ れた
メ モリ 領域の先頭の位置を 求める ． (図 2)
こ の手法は， ヒ ープス ロ ッ ト の個数は関係がな い．
O(1) のア ルゴ リ ズム であ る ．
ビッ ト マッ プ位置探索は前述し た通り ， 処理系にと っ
てボト ルネッ ク になる 部分であ る ． こ の手法は， 高速
に動作する と いう 面では， 今回の要求を ク リ ア し て
いる ．
}
図 4 二分によ る ビ ッ ト マッ プ位置探索
Fig. 4 BitMap position search by binary
こ の改善は， ビ ッ ト マッ プマーキ ン グ によ り ， 多く
のメ モリ が共有でき た事によ る も のだ 12) と ， 彼ら は
考え ている ． ApacheHTTP サーバによ っ て， 頻繁に
さ て， 問題はアラ イ ン し たメ モリ 領域の確保方法で
生成さ れる サブプロ セス と ， 親プロ セス 間で， う ま く
ある ． Linux の場合， アラ イ ンさ れたメ モリ 領域の確保
メ モリ が共有さ れ， 省メ モリ で各プロ セス が動作する
には， posix_memalign を 使用する ． posix_memalign
事で Web ア プリ ケ ーショ ン の性能が向上し たと いう
は POSIX
事であ る ．
9)
準拠の API であ る ． 指定し たサイ ズでア
ラ イ ン さ れたポイ ン タ を 返却する 働き を する ．
REE では， ビ ッ ト マッ プ位置探索に， ポータ ブル
し かし ， Ruby は Linux 以外でも 様々な環境で動作
な 手法と し て 線型探索を 使用し て いる ． 各ヒ ープス
する ． ア ラ イ ン さ れた メ モリ 領域の確保は， 環境に
ロ ッ ト を ， 先頭から 一つずつ， オブジェ ク ト のポイ ン
依存し た手法し かなく ， 多く のプラ ッ ト フ ォ ーム で動
タ が， ど のヒ ープス ロ ッ ト に属する のか比較し ていく
作する アプリ ケ ーショ ン には適用でき ない． その様な
と いう 非常にシン プルな実装であ る ． 実際のコ ード を
アプリ ケ ーショ ン では， こ の手法ではなく ， プラ ッ ト
図 3 に示す．
フ ォ ーム に依存し ないビ ッ ト マッ プ位置探索手法が必
要であ る ．
ま た， 類似し たも う 一つの案と し て， 二分探索13) の
方法があ る ． 図 1 に示し て いる 各ヒ ープス ロ ッ ト は，
現在二分探索の為， アド レ ス の若い順に格納さ れてい
3.2 ポータブルなビットマップ位置の探索
る ． こ れを 利用し ， オブジェ ク ト ポイ ン タ を 元に， 探
Ruby へビッ ト マッ プマーキングを 実装し た前例と し
索を 行う ． 実際のコ ード を 図 4 に示す．
て， Hongli Lai ら によ る RubyEnterpriseEdition(以
下 REE)10) と いう 処理系があ る ．
二分探索は， Ruby のヒ ープス ロ ッ ト の数に比例し
て処理時間は O(log2 n) で増加する ．
彼ら は， その REE を ApacheHTTP サーバ環境の
ま た REE に至ってはビッ ト マッ プ位置検索に線型探
元で動作する RubyOnRails アプリ ケ ーショ ン に適用
索を 使用し ている ． 処理時間はヒ ープス ロ ッ ト によ っ
し ， そのアプリ ケーショ ン について計測を 行っ ている ．
て O(n) で増加する ． こ れは二分探索よ り も 処理速度
その結果と し て， リ ク エス ト 毎秒 22 ％が高速化し ，
総メ モリ 使用量が 31 ％削減し たと 報告し た．11)
が遅い．
こ れら ， 二つの手法は， プラ ッ ト フ ォ ーム に依存し
5
ないポータ ブルな手法である が， 処理速度が遅い． ビッ
ト マッ プ位置探索はオブジェ ク ト を マーク する 際に必
ず行う 処理である ． こ のボト ルネッ ク の箇所に O(log2
n) や， O(n) のア ルゴ リ ズ ム を 毎回使用する こ と は，
処理系にと っ て大き な負荷になる ．
効率的なビ ッ ト マッ プマーキ ン グ を 実現する ために
は， 高速でビ ッ ト マッ プ位置を 探索する 事は， 非常に
重要な要素と いえる ． ま た， こ のビ ッ ト マッ プ位置探
if (((RVALUE *)p)->as.free.flags & FL_ALIGNOFF)
{
res = (RVALUE *)((((VALUE)p & ~0x3FFF) + 0x4000) /
sizeof(RVALUE) * sizeof(RVALUE));
}
else {
res = (RVALUE *)(((VALUE)p & ~0x3FFF) /
sizeof(RVALUE)*sizeof(RVALUE));
}
図 5 Ruby における ア ラ イ ン 手法でのビ ッ ト マッ プ位置探索
Fig. 5 Bitmap place search by Align method in Ruby
索を O(1) のア ルゴ リ ズム に変更する こ と で， 前述し
たよ う な実用的な Web ア プリ ケ ーショ ン は， 更に性
能が向上する はずであ る ．
3.3 Ruby のヒープ構造を利用した新規探索手法
本研究では Ruby における ， ポータ ブルな探索手法
であ り ， かつ O(1) のア ルゴ リ ズム と し て以下を 提案
する ．
Ruby のヒ ープス ロ ッ ト はそ れぞれ 16KB で確保
さ れている ． 16KB と は， 2 の 14 乗であ る ． つま り ，
ヒ ープス ロ ッ ト 内には， 下位 14bit が 0 である 箇所が，
先頭か， 末尾か， ど こ かに存在する はずであ る ． その
場所にビ ッ ト マッ プへのポイ ン タ を 定義すれば， オブ
ジェ ク ト のポイ ン タ の下位 14bit を マス ク する こ と で，
図 6 ヒ ープス ロ ッ ト の初期化
Fig. 6 Initialize heap slot
目的のビッ ト マッ プ領域が探索可能と なる はずである ．
だが， こ れで はオ ブジェ ク ト のア ド レ ス が， 下位
14bit でマス ク し たア ド レ ス よ り 小さ い場合， ヒ ープ
ス ロ ッ ト 外の違う 場所を さ すこ と になる ． そこ で， ヒ ー
プス ロ ッ ト の開始位置から ， 下位 14bit が 0 であ る ア
ド レ ス ま でのオブジェ ク ト に， フ ラ グを 立てる ． (図 6)
こ のフ ラ グ には， ビ ッ ト マッ プマーキ ン グ の適用によ
(0x4000 /sizeof(RVALUE) + 2) * sizeof(RVALUE);
図 7 ヒ ープス ロ ッ ト サイ ズの計算
Fig. 7 Calculation of the heap slot size
り ， 使用さ れなく なったマーク ビッ ト を 使用し た． マー
キ ン グ の際には， こ のフ ラ グ を 利用し ， オブジェ ク ト
の位置を 判断し ， ビ ッ ト マッ プ位置の計算を 行う ．
さ ら に， ヒ ープ内はオブジェ ク ト のサイ ズによ っ て
アラ イ ン さ れている ． その為， 位置計算の際にはオブ
ジェ ク ト ポイ ン タ の下位 14bit を マス ク し たアド レ ス
を ， オブジェ ク ト のサイ ズでアラ イ ン する ． 図 5 に実
際に行う C のコ ード を 示す．
ま た， Ruby の場合， ヒ ープス ロ ッ ト を 拡張する 必
要があ る ．
こ の手法では， 必ず一つだけ， 下位 14bit が 0 であ
図 8 ヒ ープス ロ ッ ト サイ ズの調整
Fig. 8 Adjustment of the heap slot size
る アド レ ス を 含むオブジェ ク ト が， そのヒ ープス ロ ッ
ト 内に存在し なければなら ない． し かし ， 現在， Ruby
可能性があ る のだ． (図 8) そこ で， 今回は 図 7 様な
ではヒ ープス ロ ッ ト を オブジェ ク ト サイ ズでアラ イ ン
コ ード でヒ ープス ロ ッ ト のサイ ズを 少し 拡張し た．
する 際に， ヒ ープス ロ ッ ト 内に存在する オブジェ ク ト
ま た， 綺麗に 20byte でア ラ イ ン さ れたア ド レ ス の
の個数が変動する 事は， 1 章にて前述し た通り であ る ．
ヒ ープス ロ ッ ト が確保さ れた場合， ビ ッ ト マッ プへの
つま り ， 位置計算し て求めたオブジェ ク ト が削ら れる
ポイ ン タ が二つになっ てし ま う 為， こ のケ ース におい
6
obj_num = HEAP_SIZE / sizeof(struct RVALUE) - 1
size = sizeof(int) * (obj_num / (sizeof(int) * 8)+1);
map = (int *)malloc(size);
図 9 ビ ッ ト マッ プ領域の確保
Fig. 9 Allocate bitmap area
作せず， そのま ま にし ておく ．
こ れは， 極力， CoW さ れないよ う にする 為であ る ．
( 5 ) 一つのヒ ープス ロ ッ ト を ス イ ープし た後， マー
ク を 消去する 為， ヒ ープス ロ ッ ト に対応し たビ ッ ト
マッ プ領域を 0 でク リ ア する ．
obj_index = (obj_p - slot) / sizeof(RVALUE);
index = obj_index / (sizeof(int) * 8);
offset = obj_index % (sizeof(int) * 8);
map[index] |= 1 << offset;
図 10 ビ ッ ト マッ プへのマーキ ン グ
Fig. 10 Marking to bitmap
( 6 ) すべてのヒ ープス ロ ッ ト に対し てス イ ープを 行
い， GC を 終了する ．
こ の様に Ruby 処理系に， 本研究で提案し たビ ッ ト
マッ プ探索手法を 利用し た， ビ ッ ト マッ プマーキ ン グ
を 実装し た．
ては意図的に一つオブジェ ク ト を 削る 事と する ． こ れ
によ り ， ヒ ープス ロ ッ ト 内にず一つだけ， ビ ッ ト マッ
プへのポイ ン タ が確保さ れる 事が保証さ れた． (図 8)
こ の探索手法ではヒ ープス ロ ッ ト の個数は関係ない．
O(1) のア ルゴ リ ズ ム であ る ． よ っ て ， ボト ルネッ ク
であ る マーク 処理内において， 高速かつ， 安定し て動
作する ．
ま た， posix_memalign の手法と は違い， プラ ッ ト
フ ォ ーム 依存が少ない． よ り ポータ ブルな手法であり ，
Ruby のよ う に多く のプラ ッ ト フ ォ ーム で動作する ア
プリ ケ ーショ ン に， 適用可能であ る ．
4. 性 能 評 価
こ の章では新手法の性能を 評価する ． 評価では以下
に示す 3 種類の Ruby 処理系で同一のプロ グ ラ ム を 実
行する こ と で行う ．
• orign
従来の Ruby 処理系． バージョ ン は 1.9.0-4 であ る ．
• btree
Ruby1.9.0-4 にビ ッ ト マッ プマーキ ン グ を 適用し た
処理系． ビ ッ ト マッ プの探索には二分探索を 使用し
ている ．
• align
3.4 Ruby へのビットマップマークスイープ実装
本手法を 適用し た Ruby 処理系の， ビ ッ ト マッ プ
マーキ ン グ から ス イ ープま での手順を 以下に記す． 処
理内容に変更の無い箇所については， 説明を 割愛する ．
Ruby1.9.0-4 にビ ッ ト マッ プマーキ ン グ を 適用し た
処理系． ビ ッ ト マッ プの探索には本研究で紹介し た
手法を 使用し ている ．
計測は IntelCoreDuo(1.83GHz, 2MB L2 キ ャッ
シュ , 667MHz FSB)， メ モリ ２ GB の計算機で行っ
( 1 ) ビ ッ ト マッ プは int 型の配列で作成する ． 作成
し た配列のサイ ズ (bit) は， ヒ ープス ロ ッ ト 内に存
在する オブジェ ク ト の個数分確保する ．
C のソ ース コ ード を 図 9 に示す．
( 2 ) マーク 時には， オブジェ ク ト のポイ ンタ から 図 5
た ． OS は Linux2.6.24， コ ン パイ ラ は gcc 4.2.3 を
を 使用し ， ビ ッ ト マッ プ位置を 探索を 行う ．
( 3 ) ビッ ト マッ プにマーキングする 際， ヒ ープス ロ ッ
ト から マーク 対象のオブジェ ク ト ま でのイ ン デッ ク
ス を 求める ． そのイ ン デッ ク ス を int のサイ ズで除
用いた．
4.1 skk.rb
skk.rb14) は SKK サーバ15) の様な動き を する ． 起
動時に， 辞書フ ァ イ ルを ハッ シュ に詰め込み， 自身を
デーモン 化する ． 今回， 郵便番号と 住所の辞書フ ァ イ
ル16) を 使用する 事と する ．
その後， 5 個のサブプロ セス を 生成し ， 親プロ セス
算し ， マーキ ン グ 位置のイ ン デッ ク ス を 求める ． ま
で TCP での通信を 待つ． ク ラ イ アン ト 側では， SKK
た， int のサイ ズで剰余演算を 行い， マーキ ン グ 位
サーバが待っ ている ポート に郵便番号を TCP プロ ト
置へのオフ セッ ト を 求める ． こ の二つの値を 元に，
コ ルにて送信する ． その通信を 親プロ セス がキ ャッ チ
ビ ッ ト マッ プ位置へマーキ ン グ を 行う ．
し ， 生成し ておいたアイ ド リ ン グ 中のサブプロ セス に
C のソ ース コ ード を 図 10 に示す．
処理を 渡す． サブプロ セス は自身のも つハッ シュ にて
( 4 ) ス イ ープ時に， フ リ ーリ ス ト にオブジェ ク ト を
つな ぎ 直す際， 元々フ リ ーリ ス ト に繋がっ て おり ，
使用さ れていないオブジェ ク ト に関し ては， 何も 操
郵便番号を 住所に変換し ， 結果を ク ラ イ アン ト 側に返
す仕組みであ る ．
今回の計測は， ク ラ イ ン ト 数 10， それぞれのリ ク
7
表 1 GC 最大処理時間
Table 1 GC max time
処理系
処理時間
orign
48
btree
92
52
align
単位はすべて msec
ビ ッ ト マッ プマーキ ン グ を 適用し ， メ モリ 消費量を
マーク 時間
ス イ ープ時間
28
72
36
20
20
16
抑える 事によ っ て通常よ り も 高速に動作し ている 事が
分かる ． ま た， ビ ッ ト マッ プ位置探索に， 本研究で提
案し た手法を 用いる と ， 更に性能が向上し ている 事が
わかる ．
5. ま と め
表2
処理系
各プロ セス の合計メ モリ 使用量
Table 2 Memory usage
合計メ モリ 使用量
共有メ モリ 使用量
orign
123956
46304
50348
90836
btree
align
51740
91152
単位はすべて KB， ま た， ヒ ープ領域内のみの使用量
表 3 サーバア ク セス 速度
Table 3 Server access speed
処理系
平均リ ク エス ト 終了時間 (秒)
orign
btree
align
0.0090224
0.0086908
0.0084847
本研究では， RubyGC にビ ッ ト マッ プマーキ ン グ
を 実装する 事によ っ て， サブプロ セス を 生成する 実用
的な プロ グ ラ ム にて メ モリ 使用量が 62 ％削減さ れ，
メ モリ 消費量を 抑え る 事に効果的であ る 事を 示し た ．
ApacheHTTP サーバの環境の元で動作する Web ア
プリ ケ ーショ ン のよ う に， 頻繁にサブプロ セス を 生成
する アプリ ケーショ ン では， こ の手法を 適用する 事で，
よ り 少ないメ モリ 消費量で動作する 事が可能であ る ．
ま た， ビッ ト マッ プ位置を 探索する 手法と し て， ポー
タ ブルで， かつ， 高速に探索可能な手法を 提案し ， こ
れを RubyGC に実装し た． こ れによ り ， 通常のマー
ク ス イ ープ GC よ り も 処理時間が 7 ％遅く なっ た． し
かし ， ビ ッ ト マッ プ位置探索に二分探索を 使用し た場
エス ト 数 200 回で測定を 行っ た．
表 1 では発生し た GC の最大処理時間の比較を 示
し ている ．
GC の最大処理時間では， オリ ジナルの Ruby 処理
系 (orign) に比べて本研究によ り 提案し たビ ッ ト マッ
プマーキ ン グ を 用いた処理系 (align) の方が 7 ％程遅
く なっている ． ま た， 二分探索によ る ビッ ト マッ プマー
キ ン グ を 用いた処理系 (bree) では 91 ％程遅い．
align の速度低下について はビ ッ ト マッ プを 計算す
る イ ン ス ト ラ ク ショ ン が増えた為， 仕方のない範囲の
劣化である 筆者ら は考える ． ま た， align はビ ッ ト マッ
プ位置検索に二分探索を 使用し た btree よ り も かなり
高速に動作し ている 事が分かる ．
ス イ ープ時間では align が， 25 ％程速い． ビッ ト マッ
プマーキ ン グ ではス イ ープ時にマーク フ ラ グ を 一つ一
つ消す必要がなく ， ビ ッ ト マッ プ領域を 一度初期化す
る だけでよ い． こ れによ り ス イ ープ処理が速く なっ た
と 思われる ．
表 2 では計測後の， 各 5 個のプロ セス のメ モリ 使用
の合計値を 表し ている ．
ビッ ト マッ プマーキン グを GC に適用する 事によ り ，
総メ モリ 使用量が通常の半分以下に削減さ れている こ
と が分かる ． こ れは， 2 章で述べた 通り ， CoW 向け
の改善によ る も のであ る ．
表 3 では SKK サーバへのリ ク エス ト から ， ク ラ イ
ア ン ト ま でのレ ス ポン ス の速度を 表し ている ．
合よ り も GC 処理時間を 43 ％速く する 事に成功し た．
参 考
文
献
1) Ousterhout, J.: Scripting: Higher level programming for the 21st century, IEEE Computer, Vol.31, No.3, pp.23–30 (1988).
2) Prechelt, L.: An Empirical Comparison of
C, C++, Java, Perl, Python, Rexx, and
Tcl for a Search/String-Processing Program,
Technical Report 2000-5, Fakultät für Informatik, Universität Karlsruhe, Germany (2000).
ftp.ira.uka.de.
3) ま つも と ゆき ひろ ， 石塚圭樹： オブジェ ク ト 指
向ス ク リ プト 言語 Ruby， アス キー出版局 (1999).
4) 高橋浩和， 小田逸郎， 山幡為佐久： Linux カ ー
ネ ル 2.6 解読室， ソ フ ト バン ク ク リ エ イ ティ ブ
(2006).
5) The Apache Software Foundation: Apatch
HTTP Server Project, http://httpd.apache.
org/.
6) Jones, R. and Lins, R.: Garbage Collection:
Algorithms for Automatic Dynamic Memory
Management, Wiley (1996).
7) Hans-Juergern Boehm and Mark Weiser:
Garbage collection in an uncooperative enviroment, Software Practice and Experience,
Vol.18, No.9, pp.807–820 (1988).
8) David Heinemeier Hansson: Ruby on Rails,
http://www.rubyonrails.com/.
9) Lewine, D.A.: Posix Programmer’s Guide, Or-
8
eilly and Associates Inc (1991).
10) HongliLai and NinhBui: RubyEnterpriseEdition, http://www.rubyenterpriseedition.com/.
11) HongliLai and NinhBui: Performance and
memory usage comparisons, http://www.
rubyenterpriseedition.com/comparisons.html.
12) HongliLai and NinhBui: 33 ％ memory reduction and faster? Is this for real?， http://www.
rubyenterpriseedition.com/faq.html#thirty_
three_percent_mem_reduction.
13) Knuth, D. E.: The Art of Computer Programming: Fundamental Algorithms, AddisonWesley, third edition (1997).
14) : 郵 便 番 号 変 換 簡 易 skk サ ー バ ， http://
github.com/authorNari/skkzipcode/tree/master.
15) SKK Open lab: http://openlab.jp/skk/
index.html.
16) SKK Open lab: http://openlab.jp/skk/
skk/dic/zipcode/SKK-JISYO.zipcode.