業務で調べる機会があったのでブログにもまとめる。
世代別 GC とインクリメンタル GC
Ruby 処理系には世代別 GC やインクリメンタル GC が採用されている。これらアルゴリズムを採用するには Write Barrier と呼ばれる仕組みが必要であるが Ruby には実装されていない。そこで Ruby 向けのアルゴリズムを使った RGenGC と RincGC が実装されている*1*2。
Write Barrier とは
世代別 GC には、メジャー GC とマイナー GC と呼ばれる、オブジェクトのライフタイム別 GC がある。メジャーは古いオブジェクトに対し、マイナーは新しいオブジェクトに対して GC を行う。古いか新しいかは GC を生き残った回数で計られる。
マイナー GC は新しいオブジェクトのみを GC 対象とするために困った問題が起こる。古いオブジェクトから新しいオブジェクトに参照があったときそれを検知できないのだ。なぜならマイナー GC は新しいオブジェクトをルートにし、そこから辿れるオブジェクトの参照しかチェックしていないから。もしマイナー GC で古いオブジェクトからの参照もチェックしていたら世代別 GC の意味がなくなってしまう。そして、問題というのは、古いオブジェクトから参照されている新しいオブジェクト、つまりまだ使いたいオブジェクトまで誤ってスイープされてしまう。
この問題を回避するために世代別 GC には Write Barrier という仕組みがセットで必要になる。Write Barrier は古いオブジェクトから新しいオブジェクトへの参照が追加されたとき、古いオブジェクトを「リメンバーセット」に登録する。リメンバーセットに登録されたオブジェクトは次のマイナー GC でマークするときの起点に含まれる*3。これにより参照されている新しいオブジェクトの誤ったスイープを回避できる。めでたし。
要約すると、Write Barrier は参照されている新しいオブジェクトを間違えてスイープしないための仕組みといえる。
Write Barrier Unprotected Objects とは
Write Barrier によって保護されていないオブジェクトのこと。
冒頭書いたように、Ruby には Write Barrier が実装されていないので、初期は全てが Write Barrier Unprotected Objects となる。笹田氏らは、Ruby でよく使われるオブジェクト (String, Array, Hash...) に集中的に Write Barrier を実装する戦略を採った。あまり使われないオブジェクトへの実装は後回しにすることで世代別 GC の旨味を早いうちに享受しつつ、順次改善できるという目論見らしい。
では、Write Barrier Unprotected Objects はマイナー GC で誤って Sweep されてしまうではないか、となるがそんなことはない。その辺りは*4に詳しく記されている。Unprotected Object は旧世代扱いにしないことで常にマイナー GC のマーク対象として辿れるようにしているらしい。
直近のリリース Ruby 3.3 でも Time クラスに Write Barrier が導入されたことが記されている*5。ちょっとずつ進んでいるらしい。
世代別GCで必要となるライトバリア（WB）を、複数のクラスに導入しました。WB がない場合は、時間がかかるけどちゃんとうごく、というアルゴリズムで、頑張って WB 入れれば速くなるぞ、みんなで移行しようね、という方針だったんですが、その移行処置を進めたということですね。Timeはよく使うので対応したかったんですが、よくわからなくて放置していたので対応されてよかったです。
ちょっとした実験
❯ ruby --version ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Ruby 3.1 時点では Time クラスは Write Barrier 未導入のクラスである。String クラスは Write Barrier が導入済みである。両クラスのオブジェクトをたくさん作ってみて Write Barrier Unprotected Object の数がどう変化するか見てみた。
irb(main):001> GC.stat => {:count=>24, :time=>33, :heap_allocated_pages=>150, :heap_sorted_length=>150, :heap_allocatable_pages=>0, :heap_available_slots=>61291, :heap_live_slots=>59407, :heap_free_slots=>1884, :heap_final_slots=>0, :heap_marked_slots=>45843, :heap_eden_pages=>150, :heap_tomb_pages=>0, :total_allocated_pages=>150, :total_freed_pages=>0, :total_allocated_objects=>234419, :total_freed_objects=>175012, :malloc_increase_bytes=>22992, :malloc_increase_bytes_limit=>16777216, :minor_gc_count=>20, :major_gc_count=>4, :compact_count=>0, :read_barrier_faults=>0, :total_moved_objects=>0, :remembered_wb_unprotected_objects=>282, :remembered_wb_unprotected_objects_limit=>462, :old_objects=>45438, :old_objects_limit=>72896, :oldmalloc_increase_bytes=>1509072, :oldmalloc_increase_bytes_limit=>16777216} irb(main):002> ary = Array.new => [] irb(main):003> 100.times { |n| ary[n] = String.new } => 100 irb(main):004> GC.stat => {:count=>40, :time=>56, :heap_allocated_pages=>150, :heap_sorted_length=>150, :heap_allocatable_pages=>0, :heap_available_slots=>61291, :heap_live_slots=>59651, :heap_free_slots=>1640, :heap_final_slots=>0, :heap_marked_slots=>47291, :heap_eden_pages=>150, :heap_tomb_pages=>0, :total_allocated_pages=>150, :total_freed_pages=>0, :total_allocated_objects=>462873, :total_freed_objects=>403222, :malloc_increase_bytes=>8928, :malloc_increase_bytes_limit=>16777216, :minor_gc_count=>36, :major_gc_count=>4, :compact_count=>0, :read_barrier_faults=>0, :total_moved_objects=>0, :remembered_wb_unprotected_objects=>285, :remembered_wb_unprotected_objects_limit=>462, :old_objects=>46874, :old_objects_limit=>72896, :oldmalloc_increase_bytes=>1994128, :oldmalloc_increase_bytes_limit=>16777216} irb(main):005> 100.times { |n| ary[100+n] = Time.new } => 100 irb(main):006> GC.stat => {:count=>43, :time=>62, :heap_allocated_pages=>150, :heap_sorted_length=>150, :heap_allocatable_pages=>0, :heap_available_slots=>61291, :heap_live_slots=>59802, :heap_free_slots=>1489, :heap_final_slots=>0, :heap_marked_slots=>47588, :heap_eden_pages=>150, :heap_tomb_pages=>0, :total_allocated_pages=>150, :total_freed_pages=>0, :total_allocated_objects=>515147, :total_freed_objects=>455345, :malloc_increase_bytes=>30416, :malloc_increase_bytes_limit=>16777216, :minor_gc_count=>39, :major_gc_count=>4, :compact_count=>0, :read_barrier_faults=>0, :total_moved_objects=>0, :remembered_wb_unprotected_objects=>385, :remembered_wb_unprotected_objects_limit=>462, :old_objects=>47087, :old_objects_limit=>72896, :oldmalloc_increase_bytes=>1966240, :oldmalloc_increase_bytes_limit=>16777216}
remembered_wb_unprotected_objects を見ると現在の Unprotected Object の数が分かる。結果は、String クラスのオブジェクト生成では Unprotected Object は増えなかったが、Time クラスの時は増えた。
初期状態: 282 String 生成後: 285 Time 生成後: 385
Write Barrier 実装 PR
軽く PR を見てみたところ直近のもので Enumerator や TracePoint に Write Barrier が実装されていた。
