Rubyのメモリ管理の改善
Improving Memory Management for Ruby

東京⼤学⼤学院情報理⼯学系研究科創造情報学専攻

笹⽥ 耕⼀

sasada@ci.i.u-tokyo.ac.jp, ko1@rvm.jp

2009/10/28

第76回プログラミング研究会

1agenday 謝辞

y 貢献のまとめy 背景

y 現状のRuby処理系
y 改善⼿法の検討
y 実装
y 評価

y まとめ

2009/10/28

第76回プログラミング研究会

2

謝辞
y 本研究では，ネットワーク応⽤通信研究所のまつもとゆきひろ⽒を初めとしたRuby開発者の⽅々，電気通信⼤学の鵜川始陽⽒に助⾔を頂きました．
y Linuxカーネルのメモリ管理について，富⼠通株式会社の⼩崎資広⽒に助⾔を頂きました．
y メモリ管理実装の⼀部は，プログラミング＆セキュリティキャンプ2009の参加者によって試験実装を⾏ってもらいました．
y 本研究の⼀部は，⽇本学術振興会科学研究費補助⾦若⼿研究（若⼿（B）），課題番号21700024の助成を得て⾏いました．
2009/10/28

第76回プログラミング研究会

3

本発表の貢献のまとめ
y Ruby実装の『制約』を元にメモリ管理改善を検討
y ヒープサイズを⼤きくしてスループット向上
y OSと簡単に協調するヒープサイズ調整，スイープの改善
y メモリ管理機構の実装を⼀新
y 予備評価により，ある程度の成果を確認
y 来年リリースする Ruby 1.9.2 のメモリ管理へ
y メモリ周りでいい評判がないのでなんとかしたい
y あまりドラスティックな変更はできない
y 現在進⾏中の仕事
y まだ，全ての実装が終わっていないため，最後までまとまっていません．ご意⾒募集．
2009/10/28

第76回プログラミング研究会

4背景
y オブジェクトスクリプト⾔語Rubyy Ruby 1.9.1: 2009-01, Ruby 1.9.2: 2010-??
y Ruby on Rails などで世界中で⼤ヒット
y ! テキスト処理簡単⾔語

y Ruby処理系

y インタプリタy Cによる実装

y VM，実⾏時にバイトコードコンパイル [笹⽥2005]
y GC：保守的なマークアンドスイープ• オブジェクト操作は，ただのポインタ操作• 性能より，処理系および拡張ライブラリの作りやすさを優先
2009/10/28

第76回プログラミング研究会

5背景
Rubyのメモリ管理
y RVALUE が Ruby オブジェクトを表現
y 固定⻑ (5word)

y 収まらない部分は malloc(), free() で管理• この点は本研究の対象外• Boehm GC で全部管理すればどうなる？
• REE (Ruby Enterprise Edition) は tcmalloc を利⽤

y RVALUE は固定⻑配列(16KB) heap_slotsで管理
y 以前は可変⻑→オブジェクトフラグメンテーション対策

y 32bit マシンでは約200，64bitマシンでは約100 Objecty heap_slots は heaps という配列で管理
y アドレスで整列

2009/10/28

第76回プログラミング研究会

6Rubyのメモリ管理
heaps と heap_slots

2009/10/28

第76回プログラミング研究会

7Rubyのメモリ管理
GCの実装
y マークフェーズy 保守的にマシンスタックなどのルートから辿りマーク付
y ポインタをRVALUEへのポインタかどうかを判別• is_pointer_to_heap() という関数で実装• どれかの heap_slots の範囲内かチェック

y スイープフェーズ

y ヒープを全て辿って後始末，もしくはfreelist構築

2009/10/28

第76回プログラミング研究会

8Rubyのメモリ管理
制約
y ソースコード，バイナリの互換性は厳守
y 既存のソースコードを活かすため

y 研究としては，取らないという選択肢もあるが…

y 移動が出来ない

y コンパクションが出来ない
y コピーが出来ない

y ライトバリアが出来ない
y 世代別GCが実装できない

y インクリメンタルGCが実装できない

2009/10/28

第76回プログラミング研究会

9

関連研究
Rubyのメモリ管理への挑戦
y Ruby処理系の拡張ポリシの変更が必要
y 世代別GC [⽊⼭2001, ⽊⼭2002]→ ライトバリアが必要
y Mostly compaction [鵜川2009]→ 効率的な実装にはいくつかの仮定が必要
y インクリメンタルGC [相川2009]→ ライトバリアが必要（ツールによるサポートの提案）
y DDmalloc [Inoue2009]→ たまに再起動が必要（ウェブアプリ的にはOK）
y そうでない⼯夫
y ビットマップマーキング [中村2009]2009/10/28

第76回プログラミング研究会

10

検討
GCオーバヘッドの検討
y GCにかかる実⾏時間Tgcについて検討

y モデル• ⽣成するオブジェクトの数N• ヒープサイズH（オブジェクトの数）• ⽣きているオブジェクトの数：L（簡単のために固定）
y マーク時間y スイープ時間
y GC回数y 総GC時間2009/10/28

Tm = Wm*L
Ts = Ws*H
Ngc= N / (H-L)
Tgc = N/(H-L) * (Wm * L + Ws * H)
N/(1-L/H) * (L/H * Wm + Ws)

第76回プログラミング研究会

11⽅針
ヒープを⼤きくすると，総GC実⾏時間が下がる→ できるだけヒープを⼤きく取りスループット向上
y 問題

1. 勝⼿にヒープを⼤きくすると，他のプロセスに迷惑がかかるかもしれない
2. ヒープを⼤きくするとオブジェクトフラグメン
テーションにより，必要なときに解放できない
3. 広い区間をたどるので，スイープ時のメモリアクセス局所性が低下してしまう
2009/10/28

第76回プログラミング研究会

12検討
他プロセスと協調するヒープサイズ調整
y OSのメモリ状況を知る⽅法はOSに問い合わせる
y /proc などで⾒ると，詳細情報は取れるが，正しくバランスさせるのは困難
y ⾃プロセスのメモリのページアウトを監視
y ページアウトが1度でも発⽣したらメモリ逼迫と判断
y POSIX の getrusage() システムコールで取得＊ 今回はこの⽅針でやってみたて成果が出るのだけど，ページキャッシュなど考えるとまだ検討が必要…
y 関連研究沢⼭ [Grzegorczyk07, Yang04, Zhao09]
y そもそも，ページアウトを起こさせない仕組みを検討
y OS，ハードウェアに特殊な仕組みを要求
2009/10/28

第76回プログラミング研究会

13検討
オブジェクトフラグメンテーション対策1. heap_slots のサイズを 16KB から 4KB に変更
y 断⽚化の可能性は減少
y is_pointer_to_heap() などが若⼲⾼負荷に
2. 短寿命オブジェクトのみに広いヒープを⽤意
y その他のオブジェクトはy オブジェクトの寿命予測を利⽤
y 関連研究沢⼭ [Barrett93, Seidl98, Blackburn07,…]•••yy
2009/10/28

静的メモリ管理の効率化のために利⽤
GC では，オブジェクトの pre- tenuring に利⽤
今回は「短寿命オブジェクト」だけを知りたいのは新しいかも

プロファイルベースが必要か？ 負荷は⼤丈夫？
本研究では実装していないため，未検証
第76回プログラミング研究会

14検討
スイープの実⾏時間削減
y heap_slots ごとに，2種類のカウンタを⽤意
y MC - マークカウンタ：⽣きているObjectの数

y FC - ファイナライザカウンタ：後始末必要なObjectの数
y MC はマークフェーズで更新（若⼲の負荷増）

y MC, FCともに 0 なら，heap_slots ごと消去可能→ heap_slots 内を⼀切触らずに消去が可能→ メモリアクセスの局所性向上

2009/10/28

第76回プログラミング研究会

15

実装
1. heap_slots の管理⽅法に Arena を導⼊mmap() を利⽤してArenaを⼀気に確保（128MB）y•

アクセスされない限り実メモリを消費しない

heap_slots のサイズを 4KB （ページサイズ）にy•

heap_slots が 4KBアラインメントになって⾊々効率化

madvise() で heap_slotsごとに実メモリを直接解放y•yfree() と⽐べて直接返却

heap_slots 追加，消去ポリシを変更

2. マークカウンタを効率的に実装

3. ページアウト監視を getrusage() を使って実装
2009/10/28

第76回プログラミング研究会

16

実装
Arena の導⼊

2009/10/28

第76回プログラミング研究会

17

余談
本研究の最初の思惑と挫折
y Arena構造を導⼊して明⽰的なメモリ管理をすれば，メモリ管理全般が⾼速化するのでは？ → しなかった
y 期待
y madvise() で即座に OS に返却することで，システムのスループットが向上するのでは
y 4KB 管理でいろいろ効率化が出来るのではy 実際
y madvise() はそれなりに遅い（ページテーブル弄るし，システムコールだし）ので，多発するとかなり遅かった
y is_pointer_to_heap() とかはボトルネックじゃなかった
y 4KBにしてフラグメンテーション解消があまり出来なかった
2009/10/28

第76回プログラミング研究会

18

実装
マークカウンタy 4KBアラインメントを利⽤して，heap_slots 固有のヘッダに対して簡単アクセス

y (RVALUEへのポインタ) & ~(4KB)

y ビットマップマーキングへの応⽤も簡単→今後の課題

y スイープ時，マークカウンタが 0 なら後始末やfreelist への追加を⾏わずに即座に解放→ 局所性の向上
y ただ，局所性の向上だけならLazy sweepでもいいのでは？ → 今後の課題
2009/10/28

第76回プログラミング研究会

19

実装
ヒープサイズの調整
y getrusage() により，メジャーフォールト数記録
y heap_slots を要求する（使い切る）ごとにチェックy 前回の調査と⽐べて1回でも発⽣していればGC起動

y GCにより不要なheap_slotsが発⽣
1. まずは何もしないで放っておく2. メジャーフォールト発⽣時，放っておいたheap_slotsを madvise() で解放してまわる→ 無駄な madvise() 回数を削減，必要なときだけ解放

2009/10/28

第76回プログラミング研究会20

評価
y 評価環境y ハードウェア• CPU: Intel Xeon E5335 2.00GHz (4 core) x 2 = 8 core
• Memory: 2GB

y ソフトウェア• OS: GNU/Linux 2.6.26-2-amd64• Cコンパイラ: gcc version 4.3.2 (Debian 4.3.2-1.1)• Ruby: ruby 1.9.2dev (2009-10-26 trunk 25491)[x86_64-linux]

2009/10/28

第76回プログラミング研究会

21マイクロベンチマークy 単純な浮動⼩数点数計算 → (2)y オブジェクト寿命予測をしていないから，短寿命オブジェクトを沢⼭⽣成したいため
y ファイナライザカウンタを作っていないから，後始末の不要なオブジェクトを沢⼭⽣成したいためy ⻑寿命オブジェクトの数は調整可能にする → (1)size = (ARGV.shift || 10_000).to_i
ary = Array.new(size){|i| i.to_s} # (1)50_000_000.times do
0.5 + 0.7
# (2)end2009/10/28

第76回プログラミング研究会

22

評価対象
y proposedy Arena有り，マークカウント有り，page out 監視有り
y 不要ページはpage out起こるまで解放しない
y discardy Arena有り，マークカウント有り，page out 監視有り
y 不要ページは即座にmadivse()でOSに解放
y normalsweepy Arena有り，page out 監視有り
y 従来通り，sweep で全部辿る（局所性悪化）
y currenty 従来のインタプリタ
2009/10/28

第76回プログラミング研究会

23

評価
⻑寿命オブジェクトの数と実⾏時間
12

ベンチマークの実行時間（秒）108

proposed

6

discardcurrent
normalsweep
42

・ヒープが大きいので，安定して proposed が速い
・proposed と discard の差が madvise() のコスト
・current はバラツキが大きい02009/10/28

第76回プログラミング研究会

24

評価
複数プロセス同時実⾏（総実⾏時間）
すべてのプロセスが終了するためにかかった時間（秒）

160

140

120

100
proposed80

discardcurrent
normal sweep

60

40

20

01

2009/10/28

2345678

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

第76回プログラミング研究会

25

評価
複数プロセス同時実⾏（平均時間）
12・安定して proposed が速い（少し意外）・dicard が速い箇所がある
・n/sweep は current とあまり変わらない

総実行時間をプロセス数で割った時間（秒）108

proposed/ave
6

current/ave
discard/ave
normalsweep/ave

420
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

2009/10/28

第76回プログラミング研究会

26aobench での評価
現実的なレンダリングアプリケーション
450

400

350

300

250
proposed
discard200

current150

バグにより（多分，heap_slots 増加処理），#6でLinuxが死んでしまった

1005001

2009/10/28

2345678

第76回プログラミング研究会

910111227

考察
y ヒープサイズ⼤きくすれば速かった（当然）y madvise() 回数削減は有効y スイープ時にメモリを触らないようにする⼯夫は有効
y Lazy sweep でも同様に有効かも？
y Parallel sweep 実装は容易そう．⽐べてどうか？
y ページアウト監視は意外に有効かも？
y ファイル操作を伴うプログラムが無い，同じ挙動をするものばかりなので，さらに検討が必要
y aobenchが駄⽬だったのは，結局フラグメンテーション解消は出来ていないのでは？

y 寿命予測とか有効に働くだろうか？

y テンポラリオブジェクト作成APIを作るのはどうか？
2009/10/28

第76回プログラミング研究会

28

今後の課題y 短寿命オブジェクトの発⾒⼿法の実現
y プロファイルベースか？
y 短寿命オブジェクトと明⽰的に⽰すAPIの設計？
y ファイナライザカウンタ関連
y 後始末不要なデータ構造に変更
y ページアウト監視で良いのかの検討
y メモリ消費⾃粛期間を設けるべきだったかも
y 開発者の⽴場から：Ruby 1.9.2 に向けて
y mmap(), madvise() による Arena は取り⼊れたい
y ヒープサイズ決定アルゴリズムは修正できそう
y lazy sweep, bitmap marking は⼿軽なのでやりたい
2009/10/28

第76回プログラミング研究会

29

まとめ
Rubyのメモリ管理の改善
y 制約から，ヒープサイズを⼤きくする⽅針で検討
y ページアウトを監視してOSと協調するサイズ調整
y マークカウンタによる，スイープ時の局所性向上
y 4KB単位で管理することで断⽚化対策

y Arenaによるメモリ管理機構の⼀新

y mmap(), madvise() によるOSと直接メモリやりとり
y getrusage() によるページアウト監視y 予備評価により，ある程度の成果を確認
y ある程度効果を確認

y さらなる実装，評価が必要
2009/10/28

第76回プログラミング研究会

30