gcを知らない人のためのmruby gc

gc(garbage collection)とは

確保したメモリを自動的に解放してくれる仕組み

メモリを確保する際は、アプリケーションが要求した量より多い量が確保される。その多い分は、要求したメモリの管理のためで、管理領域があることで要求したメモリが辿れるようになっている。アプリケーションが要求した領域を解放する際は、管理領域を使って、順次メモリを辿っていき、合致する領域を探すといった事を行う。

mark & sweep

古典的なgcの一つにmark & sweepがある
mark & sweepでは、使っていないメモリを探して解放する。

例えば、rootと呼ばれるglobal変数があって、rootからたどることが出来る（参照がある）場合は、まだ使っていると判断出来る。反対に、どこからも参照されていない場合、そのメモリはもう使っていないと判断できる。
このように、どこからも参照されていないメモリ探して、適時解放する仕組みがmark & sweep。

ただ、この方式は確保しているメモリの全領域をスキャンし、使っているかどうか調べる必要がある。
これでは時間がかかり、Stop the Worldしてしまう。
通常時のgcが走らない時は、アプリケーションが早く終了するのに、たまにgcが走るとなかなかアプリケーションが終了しないといったことが起こってしまう。

世代別gc (generational gc)

mark & sweepではメモリの全領域をスキャンしているためにStop the Worldが発生していた。それ対し、メモリを世代といったグループに分けて、一回のスキャン量を減らそうといったアプローチのgcが世代別gc.

ソフトウェアの世界においては、一般的に確保されたメモリはすぐ使われて、大体はすぐ解放される。たまにすぐ解放されないものもいる。そういったすぐ解放されないメモリは、起動時とかに確保されて、ずっと使い続けられるといった特徴がある。
この特徴を利用し、確保するメモリを、確保してすぐ解放される若い世代と、なかなか解放されない古い世代に分けて、スキャン対象を減らそうとしている。

インクリメンタルgc

世代別gcでは、mark & sweepのStop the Worldを、メモリを世代に分けて、一回のスキャン量を減らそうといったアプローチを行った。
それに対しインクリメンタルgcは、一気に全部はスキャンしないで、ちょっとずつ処理していこうといったアプローチをとる。

スキャンの上限を決めておいて、到達したらスキャンは中断する。そしてアプリケーションのプログラムが動作し、また上限まで処理をし、少しずつgcを行い、ブロックする時間を減らしていく。

ちょっとずつgcするのは、デメリットもある。スキャンの途中で中断するため、その後のアプリケーションにより参照関係が崩されてしまう。
アプケーションにより参照関係が崩されないようにする仕組みがインクリメンタルgcにはあって、write_barrierと呼ばれている。

mruby gc

mrubyのgcは世代別gcとインクリメンタルgcの組み合わせ。
基本的な考え方はmark & sweep。
通常は、世代別gcの若い世代を対象としたgc(is_maior).
閾値を超えると、世代別gcの古い世代を対象としたgcとなる(is_major).
古い世代のgcはインクリメンタルgcになっていて、ちょっとずつ解放されていく。

古い世代を対象としたgc

インクリメンタルgcは3つのフェーズ(state)からなる。
1. ルートスキャンフェーズ
2. マーキングフェーズ
3. スウィープフェーズ
1.は一気に処理され、2.と3.がちょっとずつ処理される。
古い世代をインクリメンタルにgcする事でブロッキング時間を低減する。

若い世代を対象としたgc

実は若い世代を対象としたgcも、インクリメンタルgcを利用して実現されている。ルートスキャンフェーズになるまでgcを続けるといった事を行って実現している。
ルートスキャンフェーズになるまでgcを継続すると、ブロックしてしまう気がした。
しかし若い世代はオブジェクト数が少ない前提であるため継続するとなっているようだ。

mrubyのgcのコードを確認

mrb_incremental_gcがgcのメインの関数。incrementalとついているが、世代別gcも中で行われている。
- is_minor:若い世代を対処としたgc
- is_major:古い世代を対処としたgc

  if (is_minor_gc(gc)) {
    /* 若い世代を対象としたgc. ROOTになるまでincremental_gcを続ける */
    incremental_gc_until(mrb, gc, MRB_GC_STATE_ROOT);
  }
  else {
    /* 古い世代を対象としたgc. ちょっとずつ incremental_gcを進める */
    incremental_gc_step(mrb, gc);
  }

if (gc->state == MRB_GC_STATE_ROOT) {
  mrb_assert(gc->live >= gc->live_after_mark);
  /* 閾値をmark後に生きているobject数 x interval_ratioとする
  * interval_ratioはdefaultで200であるため、
  * mark後に生きているobject数 x 2にlive objectの数がなった場合にgcが走る
  */
  gc->threshold = (gc->live_after_mark/100) * gc->interval_ratio;
  if (gc->threshold < GC_STEP_SIZE) {
    gc->threshold = GC_STEP_SIZE;
  }

  if (is_major_gc(gc)) {
    /* 古い世代を対象としたgcの閾値(majorgc_old_threshold)を
    * 古い世代を対象としたgc後に生きているobject数 x 2とする
    */
    gc->majorgc_old_threshold = gc->live_after_mark/100 * DEFAULT_MAJOR_GC_INC_RATIO;
    gc->full = FALSE;
  }
  else if (is_minor_gc(gc)) {
    /* 若い世代のgcの場合、生きているobject数が、古い世代を対象としたgcの閾値を超えていた場合、古い世代のgcを行う */                                                                                                                                                                            
    if (gc->live > gc->majorgc_old_threshold) {
      clear_all_old(mrb, gc);
      gc->full = TRUE;
    }
  }
}

gcはいつ呼ばれるか

オブジェクトの生成時に、閾値を超えた場合にgcは呼ばれる。
例えば以下のような例になる。

s = "hello" # オブジェクトsが生成される。
            # もしこの時点で、閾値を超えた場合はgcが走る
puts s

write_barrier

インクリメンタルgcはスキャンに上限を設けるため、スキャンの途中で中断され、アプリケーションに処理が戻される。中断中にアプリケーションにより、スキャン結果の書き換えが行われても、適切に解放する仕組みがwrite_barrierだった。
一番困るのは、スキャンの結果、誰も使っていないとなったオブジェクト（メモリ）が、スキャンの中断中にアプリケーションにより使用中とされる場合。この場合write_barrierがないと、使用中のオブジェクトを解放してしまう。

ではいつwrite_barrierが呼ばれるか?
それはオブジェクトの書き換え時で、例えば以下のような場合に行われる。

s = "hello" # オブジェクトsが生成される。
            # もしこの時点で、閾値を超えた場合はgcが走る
s = "world" # オブジェクトsがhelloからworldへ書き換えられる
            # このような書き換え時にwrite_barrierを行い参照関係の保障を実現している
puts s