Ruby 2.2のインクリメンタルガベージコレクター

この記事では、Ruby 2.2で導入されたインクリメンタルガベージコレクター（インクリメンタルGC）について説明します。 このアルゴリズムをRincGCと呼びます。 RincGCでは、Ruby 2.1より短い休止時間（GC休止時間）が可能です。



著者について：Sa田浩一はHerokuで働き、NobuとMatzをルビーのコアにしています。 YARV 、Ruby 2.1用の世代別ガベージコレクター（RgenGC）、およびruby 2.2用のインクリメンタルGCとこの記事を執筆しました。

前提

RubyはGCを使用して未使用のオブジェクトを自動的に収集します。 ガベージコレクターのおかげで、Rubyプログラマーはオブジェクトを手動で削除する必要がなく、そのような削除のバグを心配する必要もありません。

Rubyの最初のバージョンでは、すでにマークアンドスイープ（M＆S）アルゴリズムが使用されていました。 M＆Sは最も単純なGCアルゴリズムの1つであり、2つの段階で構成されています。

1.マーク：すべての生きているオブジェクトを調べて、それらを「生きているオブジェクト」としてマークします

2.スイープ：ラベルが付いていないオブジェクトは使用されなくなったため、すべて廃棄します。



M＆Sは、生きているオブジェクトの中から見つかったすべてのオブジェクトが生きているオブジェクトであるという知識に基づいています。 M＆Sアルゴリズムは非常に単純であるため、非常にうまく機能します。





マーク＆スイープGCアルゴリズム



この単純で効率的なアルゴリズム（およびガベージコレクションの保守的な方法）により、Cでの拡張機能の記述が非常に簡単になります。 その結果、Rubyには多くの便利な拡張機能があります。 ただし、このアルゴリズムのため、圧縮やコピーなどの移動GCアルゴリズムを適用することは困難です。



C拡張を記述することは、FFI（外部関数インターフェイス）を使用できるため、現時点ではそれほど重要ではありません。 しかし、最初は、多数の拡張機能を持ち、C拡張機能を介して多くの機能を提供することは大きな利点であり、Rubyインタープリターの人気が高まりました。



M＆Sアルゴリズムはシンプルで優れた動作をするという事実にもかかわらず、いくつかの問題があります。 最も重要な潜在的な問題は、スループットと一時停止時間です。 GCは、ガベージコレクションのオーバーヘッドのためにRubyプログラムを遅くします。 つまり、GCのパフォーマンスが低いと、アプリケーションの合計実行時間が長くなります。 各ガベージコレクションはアプリケーションを一時停止します。 長い一時停止は、UI / UX Webアプリケーションに影響します。



パフォーマンスの問題を解決するために、Ruby 2.1では世代別GCガベージコレクターが導入されました。 世代別GCは、ヒープスペースをいくつかの世代のいくつかの部分に分割します（Rubyでは、ヒープスペースを若いスペースと古いスペースに分割します）。 新しく作成されたオブジェクトは「若いスペース」に配置され、それに応じて「若いオブジェクト」としてマークされます。 若いオブジェクトがいくつかのガベージコレクション（Ruby 2.2では3つ）を生き残った後、それらは「古いオブジェクト」のカテゴリに入り、「古いスペース」に置かれます。 オブジェクト指向プログラミングでは、ほとんどのオブジェクトが若くして死ぬことを知っています。 したがって、ガベージコレクションを開始する必要があるのは「若いスペース」のみです。 若いスペースにオブジェクトを作成するのに十分なスペースがない場合、「古いスペース」のガベージコレクターが起動します。 ガベージコレクターが若いスペースで動作する場合は「マイナーGC」、すべてのユーザー（若いスペースと古いスペースの両方）に対しては「メジャーGC」と呼びます。 世代別GCアルゴリズムにいくつかの修正を加えて実装し、アルゴリズムとガベージコレクションの実装を「RGenGC」と名付けました。 EuRuKoでのプレゼンテーションとスライドを見て、詳細を確認できます。



RGenGCは、非常に高速なマイナーGCにより、ガベージコレクションのパフォーマンスを大幅に向上させます。 Major GCはプログラムを長時間一時停止しますが、この時間はRuby 2.0以前のバージョンの一時停止の長さと同じです。 ほとんどのガベージコレクションは、マイナーGCによって実行されます。





メジャーGCおよびマイナーGCでの一時停止



長い一時停止の問題を解決するには、増分ガベージコレクターが最適です。

増分ガベージコレクション

インクリメンタルガベージコレクションアルゴリズムは、ビルドプロセス自体をいくつかの小さなプロセスに分割し、GCプロセスとRubyプロセスを交互に切り替えます。 増分ガベージコレクターは、長い一時停止の代わりに、多くの短い一時停止を生成します。 一時停止の合計期間は同じままですが（増分ガベージコレクターを使用する場合のオーバーヘッドのために少し長くなります）、個々の一時停止は短くなります。 これにより、パフォーマンスがより安定します。



Ruby 1.9.3は、「遅延スイープ」GCを導入しました。これは、スイープフェーズでの一時停止時間を短縮します。 レイズスイープの意味は、スイープフェーズをすぐにではなく、段階的に開始することです。 レイジースイープは、個々の一時停止の期間を短縮し、インクリメンタルGCアルゴリズムの半分です。 次に、メジャーGCの作業段階をインクリメンタルにする必要があります。



オブジェクトのインクリメンタルマーキングのプロセスを説明する3つの概念を紹介します。「白いオブジェクト」-ラベルのないオブジェクト、「灰色のオブジェクト」-ラベルが付いていますが、白いオブジェクト、「黒いオブジェクト」を参照できます-マークされていますが、白いオブジェクトを示していません。



これらの3色を使用して、「マークアンドスイープ」アルゴリズムを次のように説明できます。

1.すべての既存のオブジェクトは白としてマークされます

2.スタック上のオブジェクトなどの明示的なライブオブジェクトは、灰色でマークされます。

3.灰色のオブジェクトを選択し、それが参照するオブジェクトも灰色にマークします。 元のオブジェクトの色を黒に変更します。 灰色のオブジェクトがなくなるまで繰り返しますが、白黒のオブジェクトのみです。

4.すべての生きているオブジェクトは黒く塗られているため、白いオブジェクトを収集します。



プロセス全体をインクリメンタルにするには、ステップ（3）をインクリメンタルにする必要があります。 計画は次のとおりです。灰色のオブジェクトを選択し、それらが参照するオブジェクトをグレーアウトしてから、Rubyコードの実行に切り替え、タグ付けプロセスなどに戻ります。





通常のマーキングプロセス（STW：世界を止める）対増分



オブジェクトの増分マーキングプロセスには1つの問題があります。 黒のオブジェクトは、ルビーコードの実行中に白を指すことができます。 定義上、黒いオブジェクトは白いオブジェクトを参照できないため、これは問題です。 これを防ぐために、「書き込みバリア」を使用して、黒のオブジェクトから白へのリンクの作成を検出します。



たとえば、配列オブジェクト「ary」はすでに黒としてマークされています。

ary = [] # GC    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードを実行すると、オブジェクト「obj = Object.new」は白になります。

 ary << obj #   obj GC  
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、黒いオブジェクトは白いオブジェクトを参照します。 「obj」を参照する灰色のオブジェクトがない場合、「obj」はオブジェクトをマークする段階の最後で白になり、したがって誤って廃棄されます。 すべての生きているオブジェクトを収集することは重大な間違いであり、避ける必要があります。



オブジェクトが新しいオブジェクトの参照を開始するたびに、書き込みバリアが呼び出されます。 記録バリアは、黒いオブジェクトから白へのリンクがいつ作成されたかを決定します。 これが発生すると、黒のオブジェクトの色がグレー（または白のオブジェクトへのポインターを含むグレー）に変わります。 記録障壁は、すべての生き物を収集する問題を完全に解決します。



これがインクリメンタルアルゴリズムの主な意味です。 ご覧のとおり、これはそれほど難しくありません。 あなたは質問があるかもしれません：「なぜRubyはまだこの単純なGCアルゴリズムを使用していないのですか？」

Ruby 2.2のインクリメンタルガベージコレクター

Rubyインタープリター（CRuby）でインクリメンタルタグ付けプロセスを実装すると、深刻な問題が発生します-書き込みバリアの欠如。



Ruby 2.1で実装された世代別GCには、書き込みバリアも必要でした。 世代別GCを実装するために、「書き込みバリア、保護されていないオブジェクト」という新しいメソッドを発明しました。 これは、すべてのオブジェクトを保護対象と非保護対象に分割したことを意味します。 このようにして、参照されているすべての保護オブジェクトが制御下にあることを保証できます。 安全でないオブジェクトからリンクを制御することはできません。 保護されていないオブジェクトの概念の導入により、Ruby 2.1で世代別GCを実装できます。



安全でないオブジェクトを使用してインクリメンタルGCを適切に実装することもできます。

1.既存のすべてのオブジェクトを白で色付けする

2.スタック上のオブジェクトを含む、すべての明確に生きているオブジェクトをグレーで色付けします

3. 1つの灰色のオブジェクトを取得し、それが参照するすべてのオブジェクトを灰色でペイントします。 色を黒に変更します。 灰色のオブジェクトがなくなるまで繰り返します。 白黒のみ。 このフェーズは段階的に実行されます。

4.白いオブジェクトを収集します。 すべての生き物は黒です



そのため、白い生き物がないことを保証できます。





保護されていないオブジェクトの書き込みバリアからの再スキャン（WB unp。）タグ付けプロセスの終了時



残念ながら、第4段階では長い休止が発生する可能性があるため、回避したいと考えています。 ただし、合計一時停止時間は、保護されていないライブオブジェクトの記録バリアの数に関連付けられています。 Rubyのほとんどのオブジェクトは、文字列、配列、ハッシュ、またはプログラマーによって作成された単純な（純粋な）オブジェクトです。 それらは保護されたオブジェクトです。 実際には、ほとんどの場合、保護されていないオブジェクトの記録に対する障壁の一時停止は問題を引き起こしません。



次のように、メジャーGCに対してのみ増分タグ付けプロセスを行いました。 マイナーGCの一時停止について文句を言う人はいません。 インクリメンタルGCの最大休止時間は、マイナーGCよりも短くなります。 マイナーGCのブレークタイムに満足している場合、メジャーGCのブレークタイムについて心配する必要はありません。



また、RubyでインクリメンタルGCを実装するためのトリックを適用しました。 「黒くて安全でない」オブジェクトのセットがあります。 ガベージコレクターを迅速に動作させるために、保護されていないオブジェクトである「安全でない」ビットマップと、マークされたオブジェクトを示す別の「タグ付き」ビットマップを作成しました。 論理積を使用すると、「黒くて安全でない」オブジェクトを見つけることができます。

GCの一時停止時間の増分推定

ガベージコレクション中の一時停止の期間を測定するために、 gc_tracerを使用します 。 Gc_tracerにはGC：Tracerモジュールがあり、ガベージコレクションプロセスに関連するパラメーターを追跡できます。 gc_tracerは、このような各パラメーターをファイルに出力します。



ガベージコレクションには、次のイベントが含まれます。

始める

end_mark

end_sweep

newobj

freeobj

入る

出る



前述したように、RubyのGCには「マーク」と「スイープ」の2つのフェーズがあります。 「開始」イベントはマークフェーズの開始を意味し、「end_mark」はその完了を意味します。 end_markイベントは、スイープフェーズの開始もマークします。 明らかに、「end_sweep」はスイープフェーズの終了を示し、ガベージコレクションプロセスの完了も意味します。



「Newobj」と「freeobj」は、オブジェクトにメモリを割り当てて解放するときのイベントです。



「enter」イベントと「exit」イベントを使用して、一時停止の期間を測定します。 インクリメンタルGC（インクリメンタルマーキングとレイジースイープ）は、マークフェーズとスイープフェーズの中断を使用します。 「Enter」は「GC関連イベントの入力」を意味します。 最後に、「終了」は「GC関連イベントを終了する」ことを意味します



次の図は、現在のインクリメンタルGCでのイベントの経時的な分布を示しています。







各イベントの現在の時間を測定できます（Linuxでは、現在の時間はgettimeofday（）を呼び出した結果です）。 したがって、イベント「enter」および「exit」を使用して、GCで一時停止の期間を測定できます。



ko1-test-appを使用してパフォーマンスを比較します。 ko1-test-appは、Aaron Pattersonによって書かれたシンプルなRailsアプリケーションです。



gc_tracerジャムを使用するために、レーキルール「test_gc_tracer」を追加しました。

 diff --git a/perf.rake b/perf.rake index f336e33..7f4f1bd 100644 --- a/perf.rake +++ b/perf.rake @@ -54,7 +54,7 @@ def do_test_task app body.close end -task :test do +def test_run app = Ko1TestApp::Application.instance app.app @@ -67,6 +67,22 @@ task :test do } end +task :test do + test_run +end + +task :test_gc_tracer do + require 'gc_tracer' + require 'pp' + pp GC.stat + file = "log.#{Process.pid}" + GC::Tracer.start_logging(file, events: %i(enter exit), gc_stat: false) do + test_run + end + pp GC.stat + puts "GC tracer log: #{file}" +end + task :once do app = Ko1TestApp::Application.instance app.app
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、 バンドルexec rake test_gc_tracer KO1TEST_CNT = 30000を実行しました 。 30000の値は、30,000のリクエストをシミュレートすることを意味します。 結果はlog.xxxxファイルに書き込まれます。ここで、xxxxはアプリケーションプロセスのIDです。 ファイルは次のようになります。

 type tick major_by gc_by have_finalizer immediate_sweep state enter 1419489706840147 0 newobj 0 0 sweeping exit 1419489706840157 0 newobj 0 0 sweeping enter 1419489706840184 0 newobj 0 0 sweeping exit 1419489706840195 0 newobj 0 0 sweeping enter 1419489706840306 0 newobj 0 0 sweeping exit 1419489706840313 0 newobj 0 0 sweeping enter 1419489706840612 0 newobj 0 0 sweeping ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私のファイルには1,142,907行あります。



「タイプ」列には、イベントの名前「ティック」が含まれています-現在の時刻（gettimeofday（）結果、元号からのマイクロ秒数）。 この情報を使用して、一時停止の長さを確認できます。 上記の最初の2行を使用して、一時停止の長さを測定できます：10μs（1419489706840157-1419489706840147）。



次の小さなスクリプトは、各一時停止の期間を示しています。

 enter_tick = 0 open(ARGV.shift){|f| f.each_line{|line| e, tick, * = line.split(/\s/) case e when 'enter' enter_tick = tick.to_i when 'exit' st = tick.to_i - enter_tick puts st if st > 100 # over 100 μs else # puts line end } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このスクリプトは100μsごとに一時停止時間を出力するため、ログファイルには多くの行があります。



次の図は、測定結果を示しています。







世代別GCには7つの大きな休止があることがわかります。 これは、メジャーGCの起動による一時停止です。 最大休止時間は約15ms（15Kμs）です。 ただし、インクリメンタルGCでは、最大休止時間が2ミリ秒（2Kμs）に短縮されます。 素晴らしい。

おわりに

Ruby 2.2は、増分ガベージコレクションアルゴリズムを使用して、ガベージコレクションの一時停止時間を短縮します。



インクリメンタルGCは「特効薬」ではないことに留意してください。 すでに説明したように、インクリメンタルGCはパフォーマンスに影響しません。 要求が長すぎてメジャーGCを数回呼び出す場合、これは応答時間に影響しません。 ガベージコレクションの合計時間は、インクリメンタルGCのために短縮されません。