Rubyのメモリ管理方法1: 基本概念（翻訳）
本シリーズは2回に分けてお送りいたします。本シリーズの目的は、Rubyのメモリ管理の基本概念を紐解くことと、#18045で導入された可変幅アロケーション（Variable Width Allocation）によってRubyのメモリパフォーマンスがどのように向上するかを深く調べることです。
RVALUE
Rubyプログラムでは、動的なメモリアロケーションにヒープ（heap）メモリを利用しており、ヒープの基本単位はスロット（slot）です。個別のスロットはRVALUEと呼ばれる値を占有します。RVALUEのサイズは40バイトで、ArrayやStringやClassなどのあらゆる型のオブジェクトを保存するコンテナです。
RVALUEの40バイトの内訳は次の通りです。
- 冒頭の8バイト
- （フラグ用に予約）
- 次の8バイト
- Klassポインタ
- 残り24バイト
- （オブジェクト固有のフィールド用に予約）
たとえばClassオブジェクトには拡張オブジェクトへのポインタが保存され、Stringオブジェクトにはその内容が保存されます。
ヒープページ
これらの40バイトのスロットが集まってヒープページになります。ヒープページは、16KBのメモリ領域を持つコンテナです。すなわち、ヒープページ1個につき408〜409個のスロットがあり、同一ヒープページ上のすべてのスロットは隙間なく連続しています。
フリーリスト
最初にヒープページが作成されると、すべてのスロットがT_NONEという特殊な型を持つRVALUEで埋められます。T_NONEは空のスロットを表し、フラグ1個と、nextと呼ばれるKlassポインタ値だけを含みます。このポインタはさらに別のポインタを指すことができます。
また、ヒープページが初期化されるときには、ヒープページの最初のスロットにfreelistと呼ばれるポインタが設定され、そこを起点に各スロットを順にたどります。各スロットをたどるたびに、freelistポインタを現在のスロットのアドレスに設定し、現在のスロットのnextポインタを直前のスロットのアドレスに設定します。
これはFreeListと呼ばれる空のスロットのLinkedList（リンク付きリスト）を作成し、最後にたどったスロットのアドレスを元に直前のスロットのアドレスを導出します。
オブジェクトを割り当てる
そのため、オブジェクトをアロケーションする必要が生じると、Rubyはヒープページの空スロットアドレスを要求します。
言うまでもなく、このヒープページは常に空スロットへのアドレスを持つfreelistポインタを返し、freelistポインタを次の空ポインタへのアドレスで更新し、そのfreelistの現在の空スロットへのリンクを解除します。これによって、Rubyがそこにデータを置けるようになります。
freelistを使うことで、オブジェクトのアロケーションが定数時間内に収まるので、Rubyが空スロットを要求するたびに、ヒープページはfreelistポインタの値をチェックしてそのアドレスをRubyに返すだけで済みます。
Rclass型のオブジェクトをアロケーションする場合:
RString型のオブジェクトをアロケーションする場合:
RArray型のオブジェクトをアロケーションする場合:
スロットがすべて埋まると、死んだオブジェクトからメモリスペースを取り戻すためにガベージコレクタ（GC）が動き出します。
ガベージコレクション
RubyのGCアルゴリズムには「マーク-スイープ-コンパクション」方式が使われており、GCの動作中はRubyコードが実行されません。GCの3つのフェーズを見ていくことにしましょう。
1: マーク
このフェーズでは、どのオブジェクトが生きていて、どのオブジェクトが解放可能かを決定します。最初にグローバル変数やクラスなどのroot的な部分にマーキングし、その後それらの子へのマーキングをマークスタックが空になるまで繰り返します。
ここで、4つのスロットを持つヒープページが2つあり、ヒープページ1にはスロットA、B、Cが、ヒープページ2にはスロットE、F、Gがあるとしましょう。空のスロットは空きスロットを、黒塗りのスロットはマーキング済みを表します。矢印は参照を表します。たとえばAからGへの矢印は「オブジェクトAは、Gで宣言されているインスタンス変数を持つ」ことを表します。
最初はROOT要素から開始します。ROOTの下にはAとBがあるので、この2つをマークスタックにプッシュします。
それではスタックの要素を1つポップしてマーキングしてから、その子をスタックにプッシュしてみましょう。ここではAをポップしてからAの子であるGをマークスタックにプッシュすることになります。次はBをポップしてマーキングし、Bの子であるEをマークスタックにプッシュします。この作業を、マークスタックが空になるまで繰り返します。すべてのオブジェクトとその子オブジェクトをマーキングしたら、次のスイープフェーズに進みます。
2: スイープ
このフェーズでは、マーキングされていないすべてのオブジェクトをGCで回収できます。すなわち、上述のマーキング後のヒープページは以下のようになります。
GCは全ヒープページをスキャンして、マーキングされていないオブジェクトがあるかどうかをチェックし、あればメモリスペースを解放します。この場合はCとFがマーキングなしなので、GCはCとFのメモリスペースを解放します。
3: コンパクション
このフェーズは、ヒープページ内のオブジェクトをヒープの冒頭に移動します。これによってメモリを削減でき、GCそのものも高速化し、パフォーマンスも向上するといったさまざまなメリットが得られます。また、コンパクションでは2つのステップも関連します。
コンパクション: コンパクションは、ヒープページ内のオブジェクトをヒープページの冒頭に移動し、「メモリ使用量の削減」「ガベージコレクションの高速化」「書き込みパフォーマンスの向上」などさまざまな効果が得られます。コンパクションでは以下の2つのステップが関連します。
3-1: コンパクションステップ
以下の2つのカーソルを使います。このため2フィンガーアルゴリズムとも呼ばれ、2つのカーソルが出会うとステップは完了します。
- フリーカーソル: 前方（末尾）に移動します
- コンパクトカーソル: 後方（冒頭）に移動します
例を元に説明します。以下の白い矢印はフリーカーソル、黒い矢印はコンパクトカーソルです。
- フリーカーソルはヒープの冒頭から開始し、そこから最初の空きスロットに移動します。
- コンパクトカーソルはヒープの末尾から開始し、そこから最初の使用中スロットに移動します。
- コンパクトカーソルが指すオブジェクトを空きスロットに移動し、このオブジェクトの移動先を記憶するために元のオブジェクトに転送先アドレスを残しておきます。
- フリーカーソルを前方に移動し続け、コンパクトカーソルを後方に移動し続けて、2つのカーソルが出会うまで上のステップを繰り返します。カーソルが出会うとステップは完了します。
ステップが完了すると、最初の空きスロットがすべて埋まっていることがわかります。
3-2: 参照更新ステップ
参照更新ステップでは、コンパクションステップで移動したオブジェクトへのポインタを更新します。上の例から続けてみましょう。
参照更新のカーソルは1個だけです。このカーソルはオブジェクトを線形にスキャンし、オブジェクトが転送先アドレスへの参照を持っているかどうかをチェックします。
このの場合、オブジェクトAとBは「Moved to Heap Page 1」という転送先アドレスへの参照を持っていて、正しいオブジェクトGとEへの参照が更新されます。
第1回は、Rubyのメモリ管理方法とガベージコレクションの仕組みについて見てきました。次回は可変幅アロケーション（Variable Width Allocation）の仕組みについてです。
概要
原著者の許諾を得て翻訳・公開いたします。