Ruby GC実装の歴史を読む
はじめに †
Ruby 1.9.3にて、lazy sweepという仕組みが導入されました。1.9.2以前のGCはストップ・ザ・ワールドと呼ばれ、GCが始まるとRubyの実行が止まってしまうことがたびたび問題とされてきました。lazy sweepはこの問題に対する解決策として導入されたものです。というわけで見ていくことにしましょう。対象としたのは1.9.3-p484です。
lazy sweepの前に †
lazy sweepを見ていく前にRHGで取り上げられている1.7.3から1.9.3までに導入されたGCの変更点を見ていきましょう。
heaps_slot構造体 †
1.7.3ではheapsはRVALUEのポインタのポインタでしたが、1.8(のどこか。未調査)からheaps_slot構造体のポインタになりました。
rb_objspace構造体 †
1.9.1から導入されheapsなどの実体はこの構造体に入るようになりました。1.9.2でマルチVMが導入されVMごとにメモリ空間を持てるようになったみたいです。
従来グローバル変数だったheapsなどは
1
2
3
4
|
| #define heaps objspace->heap.ptr
#define heaps_length objspace->heap.length
#define heaps_used objspace->heap.used
#define freelist objspace->heap.freelist
|
のようにdefineされており、変更なくアクセスできるようになっています。
rb_newobj() †
では、rb_newobj()から見ていきましょう。rb_newobj()を上から見ていくと以下のコードがあります。
1
2
3
4
5
6
| -
-
|
|
!
!
| if (UNLIKELY(!freelist)) {
if (!gc_lazy_sweep(objspace)) {
during_gc = 0;
rb_memerror();
}
}
|
いきなりlazy sweepに出くわしてしまいました(笑)
ちなみに1.9.2では相当部分は以下のようになっています。
1
2
3
4
5
6
| -
-
|
|
!
!
| if ((ruby_gc_stress && !ruby_disable_gc_stress) || !freelist) {
if (!heaps_increment(objspace) && !garbage_collect(objspace)) {
during_gc = 0;
rb_memerror();
}
}
|
使われてないRVALUEがなかった場合、heaps伸ばす必要があったら伸ばして*1、heaps伸ばさない場合はGCを行うという処理をしています。
gc_lazy_sweep() †
というわけでgc_lazy_sweep()を見てみましょう。プロファイルやらlazy sweepをオフにしている場合のコードやらはカットして載せます。
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
32
33
34
35
36
37
38
39
40
|
-
|
|
|
|
|
|
-
|
-
|
!
|
!
-
-
|
|
!
!
|
|
|
|
-
|
!
|
-
|
-
|
|
!
!
|
|
!
| static int
gc_lazy_sweep(rb_objspace_t *objspace)
{
int res;
if (!ready_to_gc(objspace)) return TRUE;
during_gc++;
if (objspace->heap.sweep_slots) {
res = lazy_sweep(objspace);
if (res) {
return res;
}
after_gc_sweep(objspace);
}
else {
if (heaps_increment(objspace)) {
during_gc = 0;
return TRUE;
}
}
gc_marks(objspace);
before_gc_sweep(objspace);
if (objspace->heap.free_min > (heaps_used * HEAP_OBJ_LIMIT - objspace->heap.live_num)) {
set_heaps_increment(objspace);
}
if(!(res = lazy_sweep(objspace))) {
after_gc_sweep(objspace);
if(freelist) {
res = TRUE;
during_gc = 0;
}
}
return res;
}
|
処理は大きく2つに分かれています。
- sweep_slotsがあったらlazy_sweep()を呼び出してオブジェクトを回収する。なかったらheaps伸ばしてみる(下の部分で空いてるオブジェクトが少なすぎたら増加量が設定されている)
- どちらも駄目ならオブジェクトのマークを行い、before_gc_sweep()、lazy_sweep()を呼び出してオブジェクトを回収する
ポイントはsweep_slotsのようです。lazy_sweep()はsweep_slotsがあったらスイープされてるだけっぽいです。というわけでsweep_slotsを設定してそうなgc_marks()に進みましょう。
gc_marks() †
gc_marks()読むとマークのやり方がちょっと変わったことに気づきます。
1.9.2までは、
- ルートオブジェクトを起点にマシンスタックが尽きるまでマーク
- マークしきれない分はmark_stackに積んでおいて後でマーク
ですが、1.9.3からは
- ルートオブジェクトをmark_stackに積む(それぞれのマーク関数を経由して最終的にgc_mark()で積まれる)
- gc_mark_stacked_objects()を呼び出して子要素をマークする(実際にマークするのはこれまで通りgc_mark_children())
- gc_mark_children()では子要素をマークするためにgc_mark()が呼ばれており、gc_mark_stacked_objects()まで戻ってくると、「仕事が終わったはずなのに追加の仕事が(゜Д゜)」な状態になり新たに積まれなくなるまでループする
といった感じになっています。1.9.2まではmark_stackが有限サイズでもう詰めないという場合は全オブジェクト再チェックということをしていたのですが、この変更が入ったってことは結構起こってたのでしょうかね?
ちなみにgc_mark_children()では可能な限り再帰呼び出しを減らす努力が行われているようです。これは1.8.7の時点ですでにそうなっているようですね。
さてというわけでgc_marks()を見てきました。・・・mark_stackの変更に気を取られて忘れてましたがseep_slotsに関する記述はありませんでした。どうやらsweep_slotsの設定は別の関数みたいです。というわけでgc_marks()の次に呼ばれているbefore_gc_sweep()を見てみましょう。
before_gc_sweep() †
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
-
|
|
|
-
|
|
!
|
|
|
|
-
|
!
!
| static void
before_gc_sweep(rb_objspace_t *objspace)
{
freelist = 0;
objspace->heap.do_heap_free = (size_t)((heaps_used * HEAP_OBJ_LIMIT) * 0.65);
objspace->heap.free_min = (size_t)((heaps_used * HEAP_OBJ_LIMIT) * 0.2);
if (objspace->heap.free_min < initial_free_min) {
objspace->heap.do_heap_free = heaps_used * HEAP_OBJ_LIMIT;
objspace->heap.free_min = initial_free_min;
}
objspace->heap.sweep_slots = heaps;
objspace->heap.free_num = 0;
if (GET_VM()->unlinked_method_entry_list) {
rb_sweep_method_entry(GET_VM());
}
}
|
おや、ありました。結局、スイープ対象のスロットってわけではなくheaps全体が設定されるようです。
lazy_sweep() †
では次にlazy_sweep()。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
-
|
|
|
-
|
|
|
-
|
|
!
!
|
!
| static int
lazy_sweep(rb_objspace_t *objspace)
{
struct heaps_slot *next;
heaps_increment(objspace);
while (objspace->heap.sweep_slots) {
next = objspace->heap.sweep_slots->next;
slot_sweep(objspace, objspace->heap.sweep_slots);
objspace->heap.sweep_slots = next;
if (freelist) {
during_gc = 0;
return TRUE;
}
}
return FALSE;
}
|
slot_sweep()呼んで空きオブジェクトができたらそこで止めています。slot_sweep()の中身はその名の通り1スロット分だけスイープする関数で特に目新しい点はありません。
おわりに †
というわけでコードを見てきましたがlazy sweepの動きをまとめると以下のようになります。
- まずマークする
- 1スロットについてマークされてないオブジェクトを解放してみて空きオブジェクトができたらそこで止める
といった感じです。さてそうすると、「マークされた後、使われなくなったけどマークされたままのオブジェクト」というものが発生します。が、「そんなのチェックするためにいちいち全オブジェクトのチェックとスイープしてたら時間かかるでしょ、そのうち(次のマークの機会に)マークされなくなるんだからいいじゃん」といった感じなのでしょう。うぅむ、lazy(なまけた)の名に違わないですね:-)