RubyのGC改善による 私のエコライフ

RubyのGC改善による
私のエコライフ
レジ袋は結構ですよ(2009夏)
nari
ネットワーク応用通信研究所
Powered by Rabbit 0.6.1
先に
お詫び
いまからCRuby内部の
大変マニアックな
話をします
しかも30分も
m(_ _)m
今日話す内容
CRubyのGCを改善しましたというお話し
GC = ゲームキューブ？
今日の話にはついていけません
5/148
今日話す内容
GC改善 = ゴミ処理機性能アップ
なんとなくエコっぽい
流行ってるし
なんとなくタイトルに
6/148
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
7/148
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
8/148
自己紹介
自己紹介
nariと申します
id:authorNari(はてな)
nari3(twitter)
量産型中村
10/148
自己紹介
ネットワーク応用通信研究所に所属
島根の方から来ました
元アイス工場勤務，現NaCl勤務
注：NaClにアイス工場支社はない
「RailsのWebアプリを受託開発」などなど
お仕事募集中
11/148
自己紹介
無類のGC好き
「CRubyGCについて考えたりするコミッタ」
12/148
宣伝(1)
絶対復習というサービス
Railsで作ってます
復習を促進するサービス
復讐は促進しません＞＜
詳細は割愛
15/148
続きはWEBで
16/148
宣伝(2)
GCは作らない
巻末
GCはこれほど知られているのに
日本語でGCについて執筆された本がない
20/148
数少ない
GCファンに朗報!!
なんとGC本
執筆中
内容
アルゴリズムの話
実装の話
Pythonの..
androidの..
v8の..
rub..niusの..
監修は超大物
23/148
問題
誰が買うの？
今のところ笹田研のささだ先生が有力候補
24/148
宣伝はこれくらいで..
恒例のアンケート
GCに興味ある方？
ノシ
gc.cを読んだ事がある
方？
ノシ
GC本が出たらかうよ！っ
て人？
ノシ
予想...5人
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
31/148
CRubyのGC改善とエコ
GCとエコの密着した関
連性をお話ししましょう
GCとエコの関連性
CRubyGCを改善する
世界の RubyHacker のPCの熱量が1%下
がるとする
Rubyに費やす1ヶ月の電気使用量100円
1円分お得 => 1円分エコ
34/148
GCとエコの関連性
世界にはRubyプログラマ何人くらいいるだ
ろう？
まぁ，100万人くらいとしよう
100万人 X 2円 => 月間200万円エコ
年間2400万円エコ
35/148
ルピィに換算
ルピィに換算（インドの通貨）
3円 => 1ルピィ
年間約800万ルピィ
36/148
GCを改善すれば
年間約800万ルピィ分の
エコができますね！
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
38/148
現在のCRubyGC概要
現在のCRubyのGC
マークスイープ方式
CRubyのヒープ構造
malloc にて 16Kバイト のメモリ領域を確保
ヒープスロット
42/148
CRubyのヒープ構造
オブジェクトの配列を作成
オブジェクトサイズの20バイトでアラインメント
オブジェクトはそれぞれフリーリストでつながっ
43/148
ている
オブジェクトの割り当て
1. 処理系から割り当て要求
2. フリーリストからオブジェクトを一つ取り出し
3. 取り出したオブジェクトを初期化
44/148
マーク処理
1. フリーリストが尽きるとマーク処理開始
2. プログラムから見える範囲のオブジェクトを
再帰的にマーク
3. マーク処理は各オブジェクト内フラグのマー
クビットを1にする
4. 全てのルートに対してマークを終えるとマー
ク処理終了
45/148
スイープ処理
1. ヒープ内のすべてのオブジェクトを走査
2. マークされているオブジェクトはそのマーク
を消す
3. マークされてないオブジェクトはゴミと見な
し，スイープ処理を行う
4. ヒープ内を全て走査し終わるとスイープ処
理終了
46/148
シンプルな
マークスイープの実装
マーク(印付け)して
スイープ(掃除)する
ここは雰囲気だけ
つかんで貰えば
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
50/148
問題点 その1
CopyOnWrite
CopyOnWrite
多くのLinux環境では子プロセス作成時
(fork)のメモリは共有領域に置かれる
書き込みがあった際に，それぞれのプロセス
の私有領域にコピーされる
（注）Rubyの機能ではない
53/148
子プロセス生成時のメモリ領
域
54/148
実際にはコピーしない
読み込みをする時はそれでも充分
55/148
書き込み(write)が発生
56/148
そのタイミングで私有領域に
Copy
57/148
Writeの時に
Copyする
CopyOnWrite
実はCRubyGCと
CopyOnWriteは相性が
悪い
無駄なコピーの発生
CRubyGCではマークの際に生存している
全てのオブジェクトに対して印付けする
つまりWriteする
forkしたプロセスの場合，CopyOnWriteが
効いて無駄なコピーが．．
62/148
無駄なコピーの発生
63/148
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
64/148
エコ活動 その1
BitmapMarkingGC
オブジェクトの印付け用bitのみを別の領域
に移す
これをビットマップと呼ぶ
オブジェクトの生存，死亡はビットマップにて
管理
マーク時に直接オブジェクトを操作する事が
なくなる
無駄なコピーが発生しにくい
66/148
Bitmap領域を確保
Bitmapは非常に小さいサイズ
67/148
そこに印付けする
Copyが発生しない
68/148
BitmapMarkingGC導入前
例
RubyEnterpriseEditionというRuby実装
(REE)
Hongli Laiさん達によって作成
REEと呼ばれる
69/148
REEとは？
Apache+passenger 用のRuby処理系
ruby1.8.6ベース
Apache が fork() してリクエスト捌いてる
GCをBitmapMarkingGC
70/148
REEでの改善
RubyOnRails+REE+Apacheで動作させた
リクエスト毎秒 22％ が高速化
総メモリ使用量が 31％ 削減した
71/148
じゃあ，これを本家に取り
込んじゃおうよ！
ちょっと問題が…
ビットマップ位置探索
それぞれのヒープスロットにビットマップ領域がある
74/148
ビットマップ位置探索
75/148
ビットマップ位置探索
オブジェクトのアドレス->Rubyのヒープスロット
76/148
ビットマップ位置の探索をど
うしよう？
オブジェクトのアドレスしか渡ってこない
アドレスから紐付くヒープスロットを見つけな
ければならない．
77/148
単純に考える
オブジェクトにスロットを指すポインタをもうける
78/148
駄目，絶対
ヒープ領域が大きくなりメモリ消費量が大き
くなってしまう
せっかく1.9でオブジェクトをダイエットした
のに..
色んな人から怒られる
79/148
REEはどうするか
線形探索
ちょ，線形探索ですか＞＜
81/148
問題点：遅い
ビットマップ位置探索に線形探索を使用して
いる
forkしないプログラムの場合，GCがビット
マップマーキング処理の分遅くなる
82/148
REEは1.8系なのでセーフ
1.8系のRubyヒープスロットは1.8倍で大きくな
る
ヒープスロットはまぁ増えても20個とかそのくら
い
83/148
1.9系ではアウト
1.9系はRubyヒープスロットのサイズが固定
84/148
1.9系ではアウト
Rubyヒープスロット自体を増やす
1.8系で10個 => 1.9系だと357個
これだと線形探索はつらくなってくる
1.9に適した探索法を見つける必要がある
そのまま取り込めないね…
85/148
アイデア
アライメントを利用すれば
いいじゃないか
基本的なアイデア
ヒープスロットサイズは16KB
16KB = 2の14乗
0b100000000000000
88/148
基本的なアイデア
下位14bitが全て0のアドレスがヒープスロット内の
どこかに存在するはず
89/148
基本的なアイデア
90/148
ビットマップ位置探索
アドレスが 0b10101010111010000
91/148
ビットマップ位置探索
マスクする
0b10101010111010000 &
0b11100000000000000
0b101000000000000000
92/148
ビットマップ位置探索
ビットマップ位置が探索可能
93/148
問題解決
O(n)からO(1)へ
大分早くなった
94/148
ただしやっぱり少しだけ
遅い
ベンチマーク結果
skk.rb ベンチマーク（自作）
96/148
詳細は論文で！
http://www.narihiro.info/
まつもとさんと連名！
97/148
このパッチの行方
一応まつもとさんのパッチ袋へ
そのまま永眠かな..
fork()なんて..別にいいし..
98/148
（´・ω・）...
さぁ，気を取り直して
他の問題点を探そうじゃ
ないか！
ちなみにAndroid
DalvikVM
これと全く同じ問題がある
マルチタスク => いっぱい fork()
BitmapMarkingが必要になる
101/148
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
102/148
問題点 その2
長寿命
オブジェクト問題
RubyOnRailsの
Rubyヒープ使い方を
調査してみた
結果
106/148
構文木オブジェクトが
半数を占めていた
構文木オブジェクトって？
何かがおかしい…
YARV命令列にしたら構文木オブジェクトは
いらない
自然にGCされるはず
ずっと生きているのは何でだろう？
113/148
さらに調査
以下の種類の構文木オブジェクトが多かった
1. NODE_WHILE
2. NODE_METHOD
3. NODE_FBODY
4. NODE_CFUNC
114/148
メソッドで使われる構文木
NODE_METHOD,NODE_FBODY,NODE
_CFUNC
これらはメソッド生成時に使用＆保持
長寿命
115/148
NODE_WHILE
YARV内のインラインキャッシュ（最適化）に
使用
長寿命
116/148
長寿命なオブジェクトが半数
を占める
半分は無駄なマークになる
スイープはあんまり関係ない
117/148
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
118/148
エコ活動 その2
まず，まつもとさんに相談
昔は構文木オブジェクトはGCの対象じゃな
かった
どこかで面倒になってGCの対象にしちゃっ
た
構文木の部分だけ世代別にしたらどう？
120/148
おぉ！なるほど！
長寿命GC
（勝手に命名）
長寿命GC
123/148
長寿命GC
124/148
メリット
マークするオブジェクトが減る
ベンチマークが遅くならない
make benchmark
125/148
デメリット
ベンチマークがぐんと早くはならない
make benchmark
ちょっぴり早い
126/148
ライトバリア問題もクリア
構文木オブジェクトはRubyレベルから参照
出来ない
ライトバリアを入れるのがコア内部で完結
Cの拡張ライブラリとか考えなくていい
127/148
効果のあったベンチマーク
ao-bench
id:hogelogさん，id:miura1729さんに測ってい
ただきました
128/148
パッチのその後
trunkに無事取り込まれた
色々改良してきたけど初採用
感激(T.T)
131/148
が，，
反応
この辺の インラインキャッシュ やら ノードとかその辺
は，GC 対象外領域にしてしまおうと思っています．
by ささださん
133/148
（´・ω・）...
Rejectされる日は近い
話の続き
昨日の懇親会
この辺はGC対象外にしたよ！
あれはバグを生むし，とっちゃおうよ
by ささださん
137/148
（´・ω・）...
早めにReject
しますね！
カバレッジも100%に！
アジェンダ
1. 自己紹介
2. CRubyのGC改善とエコ
3. 現在のCRubyGC概要
4. 問題点
5. エコ活動
6. CRubyGCの今後
141/148
CRubyGCの今後
個人的にやりたい事(1)
色々な処理系のGCいいとこ取り
執筆の関係で色々なGCを読んでいるので
CRubyに使えそうなのはメモってる
143/148
個人的にやりたい事(2)
BoehmGCを適用してみる運動
一応動くようにした
すごく遅くなった
ちょっとチューニングする必要があるかな...
144/148
まとめ
エコ活動しました
なんやかんやで何も成果がありませんでした
先生の次回作にご期待ください
145/148
提供
(株)ネットワーク
応用通信研究所
ご静聴
ありがとうございました
質疑応答
タイム