普段プログラムを書いていると、あまり気にすることのないGCの動きについて知りたくなったので、調べた内容をまとめてみました。
GC自体は様々な言語に導入されており、アルゴリズムもそれぞれですが今回はRuby(C Ruby)のGCについて書いていきます。

RubyのGCアルゴリズムについて

Rubyでは元来「mark&sweep」というアルゴリズムでGCが動いておりました。
このmark&sweepでは

マークフェーズ
スイープフェーズ
の２つのフェーズがあります。

まずマークフェーズでは、rootオブジェクトから参照のあるオブジェクトのみにマークしていきます。
スイープフェーズではマークのついていない、つまり使われていないオブジェクトを解放していきます。
この２つのフェーズを行うだけのシンプルな手法です。
ですが、この手法ではスイープの際に全てのオブジェクトに対してマークがあるかどうかのスキャンが必要となり、他のすべての処理がブロックされてしまうという欠点がありました。
この現象を「Stop the World」と言います。

この欠点を補うために導入されたアルゴリズムが「世代別インクリメンタルGC」です。
世代別インクリメンタルGCは「世代別GC」と「インクリメンタルGC」の合わせ技となっているので、順に解説していきます。

世代別GC

世代別GCとはオブジェクトの空間を世代別に分けることによって、GCが行われる範囲を小さくする手法です。
世代には、

新しいオブジェクトのみを対象とするマイナーGC
古いオブジェクトを含めたすべてのオブジェクトを対象とするメジャーGC

があり、運用時には新しいオブジェクトの寿命が短いことがほとんどであるということを前提に、マイナーGCを高頻度で行います。
そして、メジャーGCではオブジェクトの数が一定の閾値を超えた場合のみ実行されます。
この世代で分けた手法によりmark&sweepのみに比べて処理性能の改善が可能となります。
ただし、古い世代も対象とするメジャーGC実行時のブロック時間が掛かるという問題はまだ残ります。

インクリメンタルGC

その欠点を補うのがインクリメンタルGCです。
インクリメンタルGCでは、実行プログラムと細かなGCを交互に行うことで、ブロック時間を短くする事が出来ます。
対象プログラムの総実行時間が短くなるわけではありませんが、これでStop the Worldを回避できます。
プログラムとGCを交互に細かく行うということはオブジェクトの参照関係の変更される可能性がありますが、それを検知する為にライトバリアという手法が採用されています。

世代別インクリメンタルGC

上記２つのアルゴリズムを合わせたものを世代別インクリメンタルGCと言い、Rubyではこちらが採用されています。
世代別GCをベースにブロック時間が長いメジャーGCではインクリメンタルGCが実行されています。

GCの動きを確認してみる

仕組みはざっくり理解出来たので、GCが実際に実行されるのを確認する為の簡単なプログラムを動かしてみましょう。

環境

ruby 2.5.1

hoge.rb

GC::Profiler.enable
puts "プログラム実行前: #{GC.stat.slice(:minor_gc_count, :major_gc_count, :heap_free_slots, :heap_live_slots, :old_objects)}"
a = Array.new(10000000) do
  'hello'
end
puts "プログラム実行後: #{GC.stat.slice(:minor_gc_count, :major_gc_count, :heap_free_slots, :heap_live_slots, :old_objects)}"
puts "total_time: #{GC::Profiler.total_time.round(3).to_s}ms"

変数aに10000000個の'hello'の文字列が入った配列を作り、その処理中に実行されるGCの動きをRubyの組み込みモジュールのGCとGC:: Profilerを使って結果を出力してみました。
ここではGC.stat(現在のGCのステータス値を出力するメソッド)の結果を、

:minor_gc_count
- マイナーGCが行われた回数
:major_gc_count
- メジャーGCが行われた回数
:heap_free_slots
- 空きスロット数
:heap_live_slots
- 有効な全オブジェクトの数
:old_objects
- マイナーGCでは開放されないマークされたオブジェクト

の5つだけに絞っています。
そして結果はこのようになりました。

$ ruby hoge.rb
プログラム実行前: {:minor_gc_count=>9, :major_gc_count=>2, :heap_free_slots=>96, :heap_live_slots=>23135, :old_objects=>15229}
プログラム実行後: {:minor_gc_count=>21, :major_gc_count=>7, :heap_free_slots=>396, :heap_live_slots=>10016377, :old_objects=>6333071}
total_time: 0.301ms

プログラム実行後を見ると、

マイナーGC: 12回
メジャーGC: 5回

行われている様子です。
old_objectsが6333071個にまで増えているのを見ると、生成した変数a内のオブジェクトのほとんどが古いオブジェクトとしてマークされているのが分かりました。

手動でマイナーGCを実行してみる

次にGC.startを使って手動でマイナーGCを実行してみます。

hoge.rb

GC::Profiler.enable
puts "プログラム実行前: #{GC.stat.slice(:minor_gc_count, :major_gc_count, :heap_free_slots, :heap_live_slots, :old_objects)}"
a = Array.new(10000000) do
  'hello'
end
GC.start(full_mark: false) # マイナーGCを実行
puts "プログラム実行後: #{GC.stat.slice(:minor_gc_count, :major_gc_count, :heap_free_slots, :heap_live_slots, :old_objects)}"
puts "total_time: #{GC::Profiler.total_time.round(3).to_s}ms"

マイナーGCを実行するにはGC.start(full_mark: false)を追加すればOKです。
結果を見てみます。

$ ruby hoge.rb
プログラム実行前: {:minor_gc_count=>9, :major_gc_count=>2, :heap_free_slots=>104, :heap_live_slots=>23126, :old_objects=>15229}
プログラム実行後: {:minor_gc_count=>22, :major_gc_count=>7, :heap_free_slots=>788, :heap_live_slots=>10016383, :old_objects=>10016160}
total_time: 0.383ms

先程と比べてheap_free_slotsに空きが少し出来ていますが、old_objectsがさらに増えているのを見ると、古いオブジェクトと判断されたものがほとんどでマイナーGCでのメモリの解放対象となるオブジェクトは少なかったのが分かります。
GC実行時間は先程と比べると、おおよそ80msほどかかっています。

手動でメジャーGCを実行してみる

次に手動でメジャーGCを実行してみます。
変数a内にあるオブジェクトをメジャーGCの対象にしたいので少しコードを変更しました

hoge.rb

GC::Profiler.enable
puts "プログラム実行前: #{GC.stat.slice(:minor_gc_count, :major_gc_count, :heap_free_slots, :heap_live_slots, :old_objects)}"
a = Array.new(10000000) do
  'hello'
end
a = Array.new(100)
GC.start # メジャーGCを実行
puts "プログラム実行後: #{GC.stat.slice(:minor_gc_count, :major_gc_count, :heap_free_slots, :heap_live_slots, :old_objects)}"
puts "total_time: #{GC::Profiler.total_time.round(3).to_s}ms"

Arrayオブジェクトをの中で'hello'を大量に生成した後、すぐにnilが100個入ったArrayを変数aに代入してみます。
少し無理やりですが、これではじめに作った変数a内の10000000個のオブジェクトは参照マークが外れてメジャーGCの対象になるはずなので実行してみます。
結果がこちら。

$ ruby hoge.rb
プログラム実行前: {:minor_gc_count=>9, :major_gc_count=>2, :heap_free_slots=>95, :heap_live_slots=>23137, :old_objects=>15229}
プログラム実行後: {:minor_gc_count=>21, :major_gc_count=>8, :heap_free_slots=>6326296, :heap_live_slots=>16377, :old_objects=>16157}
total_time: 0.404ms

old_objectsもマイナーGCの時と比べてかなりGC実行前の初期値に近くなっており、古いオブジェクトのほとんどが解放されたのが分かります。
heap_free_slotsも6326296まで増えていますね。

最後に

ざっくりとですがRubyのGCのアルゴリズムとサイクルを理解することが出来ました。
実務でメモリがネックとなる問題が起こった際などには、現在は「新しいオブジェクトの寿命が短いことがほとんどである」という前提のアルゴリズムで動いているということだけでも頭にいれておけば、調査の際の手助けとして、上記の例で使ったGCモジュールなどを使って長生きなオブジェクトを大量に作っていないかをチェックすることが出来そうです。
とはいえGCが動く条件などが実行プログラムによって大きく変わることが多く、かつ複雑でもあるのでトライ&エラーを繰り返す必要がありそうです。

参考

http://www.atdot.net/~ko1/activities/sasada-ipsj-pro101.pdf
https://ja.wikipedia.org/wiki/%E4%B8%96%E4%BB%A3%E5%88%A5%E3%82%AC%E3%83%99%E3%83%BC%E3%82%B8%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3
https://docs.ruby-lang.org/ja/latest/class/GC.html
https://qiita.com/yuroyoro/items/14ec7079f6574ad74409