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などは

Everything is expanded.Everything is shortened.
  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()を上から見ていくと以下のコードがあります。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
-
-
|
|
!
!
    if (UNLIKELY(!freelist)) {
        if (!gc_lazy_sweep(objspace)) {
            during_gc = 0;
            rb_memerror();
        }
    }

いきなりlazy sweepに出くわしてしまいました(笑)

ちなみに1.9.2では相当部分は以下のようになっています。

Everything is expanded.Everything is shortened.
  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をオフにしている場合のコードやらはカットして載せます。

Everything is expanded.Everything is shortened.
  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つに分かれています。

  1. sweep_slotsがあったらlazy_sweep()を呼び出してオブジェクトを回収する。なかったらheaps伸ばしてみる(下の部分で空いてるオブジェクトが少なすぎたら増加量が設定されている)
  2. どちらも駄目ならオブジェクトのマークを行い、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からは

  1. ルートオブジェクトをmark_stackに積む(それぞれのマーク関数を経由して最終的にgc_mark()で積まれる)
  2. gc_mark_stacked_objects()を呼び出して子要素をマークする(実際にマークするのはこれまで通りgc_mark_children())
  3. 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()

Everything is expanded.Everything is shortened.
  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;
 
    /* sweep unlinked method entries */
    if (GET_VM()->unlinked_method_entry_list) {
        rb_sweep_method_entry(GET_VM());
    }
}

おや、ありました。結局、スイープ対象のスロットってわけではなくheaps全体が設定されるようです。

lazy_sweep()

では次にlazy_sweep()。

Everything is expanded.Everything is shortened.
  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. まずマークする
  2. 1スロットについてマークされてないオブジェクトを解放してみて空きオブジェクトができたらそこで止める

といった感じです。さてそうすると、「マークされた後、使われなくなったけどマークされたままのオブジェクト」というものが発生します。が、「そんなのチェックするためにいちいち全オブジェクトのチェックとスイープしてたら時間かかるでしょ、そのうち(次のマークの機会に)マークされなくなるんだからいいじゃん」といった感じなのでしょう。うぅむ、lazy(なまけた)の名に違わないですね:-)


*1 関数名からはわかりませんがheaps_incrementは前のGCの結果、ヒープが小さすぎる(使われていないRVALUEが少なすぎる)と判断された場合のみheapsを伸ばします

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2014-02-02 (日) 21:56:25 (3962d)