kenjuの日記

About Programming, Mathematics and Security

『Rubyのしくみ -Ruby Under a Microscope』の読書メモ<第12章>

Rubyのしくみ -Ruby Under a Microscope-

Rubyのしくみ -Ruby Under a Microscope-

第12章 MRI・JRuby・RubiniusにおけるGC

GC。それはRubyオブジェクトが生まれ、そして死にゆく場所。

GC

GCは3つの問題を解決する

  • GCは新しいオブジェクトが使用するメモリを割り当てる
  • GCはプログラムが使用しなくなったオブジェクトを判別する
  • GCは使われなくなったオブジェクトのメモリを回収する

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

  • 1960年に John McCarthyによってLISP上で実装され使われていたもの
  • 利用可能なメモリ、すなわちヒープを使い切るまで新しいオブジェクト用のメモリをプログラムに渡す。使い切ったところで、プログラムを停止して、生きたオブジェクトをマークし、マークされなかったゴミオブジェクトをスイープするアルゴリズム
  • MRIの初期のGCアルゴリズムは、マークスイープ
    • スイープ処理は、単に各RVALUEのポインタを調整し、フリーな連結リストにするだけ
  • MRIは、オブジェクトをマークしたかしていないかの情報を、ビットマップマーキングという技術を使って記録する
    • 生きたオブジェクトをフリービットマップと呼ばれるデータ構造内に一連のビット情報として記録する技術
    • マークビットをオブジェクトと別に保存することで、MRIはプロセス間で同じ値を含んでいるメモリ量を最大化する

遅延スイープ

  • 1.9.3 以降のバージョンで、MRIは遅延スイープという最適化を導入した
  • GCによる中断によって掛かる全体のコストを単に分割で返済しているに過ぎず、GCが行う仕事の全体量を減らしているわけではない

マークスイープのデメリット

  • 処理の間プログラムを停止しなくてはならない
  • GCを実行するのに掛かる時間が、ヒープの合計サイズに比例する
  • フリーリストの要素全てが同じサイズでなくてはならない

デバッグ

  • ObjectSpace.count_objectsの返り値の:TOTAL, :FREEでトータルのオブジェクト数、フリーのオブジェクト数を知ることができる
  • GC.startでフルGCを発動できる
  • GC::Profilerを使うとGC利用のプロファイルを表示できる
    • GC::Profiler.enable -> GC::Profiler.report

コピーGC

  • コピーGCは一つの巨大なヒープまたはメモリセグメントから新しいオブジェクト用のメモリを割り当て、メモリセグメントが使い果たされたタイミングで、生きているオブジェクトだけを2つ目のメモリセグメントにコピーする
    • つまり、ゴミオブジェクトはコピーされずに残り解放される
  • 半空間アルゴリズム(semi-space algorithm)
    • From空間To空間 という二つのヒープを使う
    • Edenヒープという、新しいオブジェクトの割り当て専用の第3のヒープ領域を有するバリエーションも存在する

世代別GC

  • 新しいオブジェクトと古いオブジェクトを別のものとみなす
  • 弱い世代別仮説
    • 「たいていの新世代オブジェクトは、旧世代のオブジェクトが長く生き続けることに比べると、寿命が短い」という仮説
    • 言い換えると、「新しいオブジェクトほど若くして死ぬ可能性が高い」ということ
  • Rubiniusは旧世代のオブジェクト用にImmixと呼ばせるGCアルゴリズムを使用する
    • 連続した領域に有効なオブジェクトを集めることで、使用する総メモリ量とヒープの断片化の量を減らそうとするアルゴリズム
  • ライトバリア
    • プログラムが旧世代オブジェクトから新世代オブジェクトへの参照を追加するタイミングを「監視し続ける」ことで、新世代オブジェクトの解放時に、旧世代オブジェクトから参照され生きているのにも関わらず、誤って解放してしまうミスを避ける

並行GC

  • アプリケーションとは別のスレッドでGCを行う
  • 整合性を取るために、三色マーキングとよばれる技術を使う
    • 別スレッドでのマーク処理中に、新たに参照されるようになったオブジェクトを誤って解放してしまうのを避ける
    • マークスタックとよばれる、マーク処理でチェックされる必要があるオブジェクトのリストを管理する
  • 並行GCは、アプリケーションがオブジェクトグラフを変更したことを検出するためにライトバリアを使える