Skip to content

Instantly share code, notes, and snippets.

@omasanori
Created December 20, 2012 05:42
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save omasanori/4343185 to your computer and use it in GitHub Desktop.
20th article on Garbage Collection Advent Calendar 2012

PyPyのGCに挑戦した……けど……な話

これはGarbage Collection Advent Calendar 2012の20日目の文書として @omasanori がPyPyのGCを解説する……はずでしたが、期日までに理解しきれませんでした。すみません。

そこで、ここでは私が現時点でどこまで理解できたか、これからどこを読んでいくか、という途中経過を記すことにします。GC初心者視点なのでGC上級者には物足りない文章になっていると思います。

はじめに

PyPyはRestricted Python (RPython)と呼ばれるPythonのサブセットを中心としたインタプリタ実装ツールキットと、それを利用したPythonの処理系です。Pythonの処理系としての印象が強いですが、RPythonとツールキットの部分は他のインタプリタを実装するために利用することも可能です。

なぜPyPyを選んだかというと、『Rubyによる本気のGC』でPyPyのGCについて触れられていたのが一番大きな理由です。このスライドを読む前の私もPyPyにRPythonというインタプリタを書くための言語があることは知っていましたが、ひょっとしたらGCはインタプリタの一部ではなくランタイムライブラリとしてBoehm GCか何かとリンクしているんじゃないかと勝手に想像していました。

これはいつか読みたいなあ、でも何か目標がないとダレるなあと迷っていたら、件のスライドの作者がGCのアドベントカレンダーを企画していたので、このアドベントカレンダー用の文章を書くことを目標に読み進めていました。

PyPyは複数のGC実装を提供しており、私が今回挑戦したのはpypy/rpython/memory/gc/marksweep.pyです。これは素朴なマークスイープGCで、高速化のために様々な工夫をしているminimark.pyと比べると1/3程度のコード量なので読み始めるには適切な題材だと考えました。。

コードリーディングの対象となるPyPyのリビジョンは59169です。これはmarksweep.pyが存在する最後のリビジョンで、現在はソースツリーから削除されています。インターネットに接続されていれば、次のコマンドで目的のソースツリーが得られます。

$ hg clone http://bitbucket.org/pypy/pypy pypy $ hg update -r 59169

marksweep.pyで定義されているMarkSweepGCが今回の主役です。

ヘッダ

まず、オブジェクトの先頭にマークビットなどの情報を入れるためのヘッダを探したところ、それはあっさり見つかりました。marksweep.pyの27行目から34行目がヘッダを定義しています。

    HDR = lltype.ForwardReference()
    HDRPTR = lltype.Ptr(HDR)
    # need to maintain a linked list of malloced objects, since we used the
    # systems allocator and can't walk the heap
    HDR.become(lltype.Struct('header', ('typeid16', llgroup.HALFWORD),
                                       ('mark', lltype.Bool),
                                       ('flags', lltype.Char),
                                       ('next', HDRPTR)))

ここで頻出するlltypepypy.rpython.lltypesystem.lltypeモジュールのことで、バックエンドの型(例えばC言語の型)と対応する型を提供します。このRPythonコードから次のような構造体をイメージすることはそう難しくありません。

struct header {
	uint16_t typeid16;
	bool mark;
	char flags;
	struct header *next;
};

ソースコードのコメントにもあるように、このヘッダは単方向リンクリストになっており、次のオブジェクトのヘッダを指すようになっています。MarkSweepGCでは自前のヒープを用意せずにシステムのメモリアロケータを直接利用するので、不要になったオブジェクトを回収するためにルートから到達できないオブジェクトも何らかの形で追跡できなければなりません。この実装ではヘッダを使って追跡するためのしくみを用意しています。

この直後にはプールを定義しています。

    POOL = lltype.GcStruct('gc_pool')
    POOLPTR = lltype.Ptr(POOL)

    POOLNODE = lltype.ForwardReference()
    POOLNODEPTR = lltype.Ptr(POOLNODE)
    POOLNODE.become(lltype.Struct('gc_pool_node', ('linkedlist', HDRPTR),
                                                  ('nextnode', POOLNODEPTR)))

セットアップ

MarkSweepGC.setupではいくつかのフィールドを設定していますが、GCの動作を読み解く上で特に重要なのは60行目から80行目です。コメントを除いて引用します。

        self.malloced_objects = lltype.nullptr(self.HDR)
        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
        self.objects_with_weak_pointers = lltype.nullptr(self.HDR)
        self.curpool = lltype.nullptr(self.POOL)
        self.poolnodes = lltype.nullptr(self.POOLNODE)

lltype.nullptrは見た目通り、渡された型のポインタを表すオブジェクトのNULLポインタ表現を返す関数です。

ここで、ファイナライザ(デストラクタ)を持つオブジェクトと弱参照を内部に持つオブジェクト(弱参照されているオブジェクトではない)は特別扱いされていることがわかります。ちなみにPythonでファイナライザを持つためにはクラスに__del__メソッドを定義します。

オブジェクトの割り当て

オブジェクトの割り当ては特に変わった部分もなく、とても読みやすいコードになっています。割り当てるためのメソッドにはいくつかのバリエーションがありますが、ここではmalloc_fixedsizeを取り上げます。107行目から122行目を以下に引用します。

        result = raw_malloc(tot_size)
        if not result:
            raise memoryError
        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
        hdr.typeid16 = typeid16
        hdr.mark = False
        hdr.flags = '\x00'
        if has_finalizer:
            hdr.next = self.malloced_objects_with_finalizer
            self.malloced_objects_with_finalizer = hdr
        elif contains_weakptr:
            hdr.next = self.objects_with_weak_pointers
            self.objects_with_weak_pointers = hdr
        else:
            hdr.next = self.malloced_objects
            self.malloced_objects = hdr

メモリを割り当て、ヘッダのフィールドに値を設定して、適切なリンクリストの先頭にオブジェクトを連結しています。割り当てたメモリをヘッダにキャストする部分はまるでC言語で書かれたコードのようです。

オブジェクトの回収

MarkSweepGCではマークとスイープは両方ともcollectメソッドでまとめて処理されます。collectメソッドは236行もの長さで、marksweep.pyの約42%はこのメソッドで占められています。処理は次のステップに分かれています。

  • ルートから参照されているオブジェクトをマークスタックに置く
  • ファイナライザの中から参照されているオブジェクトをマークスタックに置く
  • マークスタックに置かれたオブジェクトとそれらに参照されているオブジェクトをマークする
  • 弱参照の参照先がマークされていない場合は参照を無効にする
  • ファイナライザのない不要なオブジェクトを回収する
  • ファイナライザのある不要なオブジェクトのファイナライザを実行して、そのオブジェクトをself.malloced_objectsに連結する

マークは再帰関数ではなくスタックとループで書かれています。GCに対する関心の高いRubyistの方は今年の10月にCRubyのGCがマークの再帰をやめた件を思い出すかもしれません。スタックはGCの対象にならないオブジェクトであり、GCを経由せずに解放されます。

まだ理解できていないのはどこか

  • プールはどこで使われているのか
  • ルートがどこにあるのか
  • GCHeaderBuilderなどとどのようにして連携しているのか
  • lltypesystemの大部分
    • 特にAddressOffsetなど、llmemoryモジュールのクラスはGCと関連が深いので要攻略

おわりに

勢いで登録したものの、しっかり完結している他の方と違って完結させることができず申し訳ありません。

当初の目標は中途半端に終わってしまったものの、まだ理解できていない部分が残っているため、これからもPyPyのGCを読んでいきます。年末年始はPCをネットに繋げない環境で過ごす予定なので、他のタスクと共に少しずつ読み進めていこうかと思います。

良いお年を。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment