前回のエントリーの続きです。
Flashのガベージコレクションに関する正しい理解
——————–
Flash Player(AVM2)のガベージコレクション(以下 GC)は以下のアルゴリズムを採用しています。
(参照: AS3TuningInsideAVM2JIT.pdf)
* Deferred Reference Counting (DRC)
* Backed by incremental conservative mark/sweep collector
今回は1つめの「遅延参照カウント」について。
「詳説 ActionScript 3.0
」14章のガベージコレクションの説明が”詳説”というよりも”概要”にしかなってなかったので、やっぱりMMgc (TamarinのGC実装)の方を読むしかなさそうです。。
参照カウント
まずは基本のアルゴリズム、参照カウントについて。オブジェクトは自分の被参照数を知っていて、それが0になると回収されます。下の図だと、初期状態(左)ではルートはAとBへの、AはCへのポインタを持っています。つまりAとBはルートから、CはAから参照されていることになります。次にCへの唯一のポインタを持っていたAがそのポインタをBへ更新します(右)。この更新により、Cは参照カウントの値が0になるため回収されます。また、AからBへのポインタが新たに作られたことによってBの参照カウントの値は2に増えています。
※ root はMMgc内ではGCRoot と呼ばれています。AS3における Stage だと思ってくれたらいいです。
上述のクラシックな参照カウントアルゴリズムは、参照カウントが0になると即座に回収されるのですが、FlashのGCはゴミオブジェクトをすぐに回収したりはしません。この事実はもしかしたら、「FlashのGCは参照カウントではない」という理解が一部で広まってしまった原因のひとつかもしれません。
遅延参照カウント (DRC)
クラシックな参照カウントアルゴリズムのデメリットのひとつとして「参照カウントの更新処理が重い」ということが挙げられます。Flashゲームなどでは大量のオブジェクトを作ると思いますが、すべてのオブジェクトの参照カウントを更新するのは大変な作業です。特にルートが持つポインタは頻繁に更新されるので、その部分の負荷は特に大きくなります。FlashのGCではその欠点を解消するために「遅延参照カウント」(以下 DRC)というアルゴリズムが採用されているようです。
DRCではルートからのポインタが変化しても参照カウントの値をすぐには更新しないようにしています。でもこのままでは上手くメモリ管理が行われません。なぜかと言うと、ルートからの参照が反映されないということは、オブジェクトの参照カウントは被参照数を正しく表していないことになるからです。これでは本当はまだ生きているのに参照カウントが0になってしまい、GCがゴミと間違えて回収してしまう可能性があります。
この問題を解決するために、DRCでは Zero Count Table (以下 ZCT) というものを利用しています(MMgc/ZCT.{h, cpp})。これは参照カウントが0になったオブジェクトを記録しておくテーブルで、以下の図のようなイメージです。
ルートからの参照はしばらく反映されないので、参照カウントが0になった時点でそのオブジェクトがゴミであるとは限りません。なのでひとまずテーブルに入れておくわけです。また、FlashのDRCでは全てのオブジェクトの生成時に一度ZCTに入れているようです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// MMgc/RCObject.h // RCObject がAS3におけるオブジェクトのベースになっている // コンストラクタ REALLY_INLINE RCObject() { composite = 1; // composite については後述 GC::GetGC(this)->AddToZCT(this REFCOUNT_PROFILING_ARG(true)); } // デストラクタ REALLY_INLINE ~RCObject() { if (InZCT()) GC::GetGC(this)->RemoveFromZCT(this REFCOUNT_PROFILING_ARG(true)); composite = 0; } // 参照カウントのデクリメント REALLY_INLINE void DecrementRef() { ... // 省略 composite--; if(RefCount() == 0) { GC::GetGC(this)->AddToZCT(this); } ... |
上述のコード内でcompositeというものが出てきましたが、これはその名の通り、参照カウントだけを扱うものではないようです。関連するフィールドを以下に示します。
|
1 2 3 4 5 6 7 8 9 |
static const uint32_t ZCTFLAG = 0x80000000; static const uint32_t STICKYFLAG = 0x40000000; static const uint32_t STACK_PIN = 0x20000000; static const uint32_t STACK_PIN_SHIFT = 29; static const uint32_t RCBITS = 0x000000FF; //参照カウント用に8ビット利用 static const uint32_t ZCT_INDEX = 0x0FFFFF00; static const uint32_t ZCT_CAPACITY = (ZCT_INDEX>>8) + 1; uint32_t composite; |
ここでは RCBITS に注目します。参照カウントアルゴリズムではカウント用にどれくらいのメモリ容量を割くかが問題になってきます。32ビットマシンにおいてオブジェクト毎に32ビット分の領域を用意していたら大量のメモリを消費してしまうため、この辺りは工夫して折り合いをつける必要がありますが、Flashの参照カウントで使われるのはどうやら8ビット分になっています。このように参照カウント用のメモリ容量を節約する手法をSticky参照カウント法と呼ぶそうです。
Flashの場合は参照カウントに使える容量が8ビットなので、1つのオブジェクトに256以上の参照があった場合はオーバーフロー(桁あふれ)することになります。ここで参照カウントのインクリメント部分の実装を見てみます。(以下はデバッグ用の処理などを削除したコードになります)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// 参照カウントのインクリメント REALLY_INLINE void IncrementRef() { REFCOUNT_PROFILING_ONLY( GC::GetGC(this)->policy.signalIncrementRef(); ) if(Sticky() || composite == 0) return; composite++; if((composite&RCBITS) == RCBITS) { composite |= STICKYFLAG; } else if(InZCT()) { GCAssert(RefCount() == 1); GC::GetGC(this)->RemoveFromZCT(this); } } REALLY_INLINE uint32_t RefCount() const { return (composite & RCBITS) - 1; } REALLY_INLINE uint32_t Sticky() const { return composite & STICKYFLAG; } uint32_t InZCT() const { return composite & ZCTFLAG; } |
参照カウント数が既に上限に達してしていたらなにもせずに return し、インクリメントしてオーバーフローしたら STICKYFLAG を立てています。また、参照カウントをインクリメントすると値が0以上になるため、ZCT内にそのオブジェクトがあった場合はそこから取り除いています。
参照カウントがオーバーフローしてしまったら？
参照カウントが8ビットの範囲を超えた場合はカウント処理を行わなくなるので、実際にオブジェクトがゴミになってもGCは回収してくれないことになります。ここで、FlashのGCはDRCのバックアップとしてマーク&スイープ(の変種)を採用しています(Backed by incremental conservative mark/sweep collector)。この辺りの実装はまだちゃんと読んでいないので勘になってしまいますが、このマーク&スイープの支援によって参照カウントがオーバーフローしたオブジェクトを回収してくれていると思われます。
ZCTの処理に話を戻します。
DRCでは参照カウントが0になったオブジェクトはいったんZCTに入れられるということでした。では、このZCTに入ったオブジェクトの回収(reap と呼ばれています)はいつ行われるのかというと、主に新たなメモリ領域を確保する必要がある時です。Flashではメモリが必要になるたびに毎回確保するのではなく、ある程度の大きさの”塊”で一気に確保し、その中から最適な大きさのメモリ領域をオブジェクトに割り当てています。その塊が小さくなってきてメモリが足りなくなった時に、ZCTに入っていたオブジェクトの参照カウントがここで初めて正しく反映されてゴミになるオブジェクトが決定します。これが”遅延”参照カウントです。ゴミになったオブジェクトは回収されてその分のメモリ領域が塊に戻されます。
パーティクルを大量も動かすデモなどでときどきカクッと動作が止まるのは、ZCTの中を全てスキャンしてゴミを回収しているからです。なので、このカクッと止まる時間はZCTの大きさに依存することになるのですが、前述の composite のフィールドにある ZCT_INDEX を見るとその大きさは20ビット(0xFFFFF)になっています。20ビットということは約100万オブジェクト分。”100万パーティクル”なんていうのも見かけましたが、Flashにおいてはなかなか絶妙な数ですね。
遅延参照カウントのメリットとデメリット
DRCのメリットは、ルートからの参照を参照カウントに反映するのを遅らせるため、カウントの増減処理によるオーバーヘッドが少なくなることです。Adobeの報告では約20%も高速化したと書いてありました。デメリットは、DRCでは普通の参照カウントと違ってゴミオブジェクトをまとめて後で回収することになるので、ある程度のまとまった時間がGCに費やされることになり “停止時間” (Stop the World) が発生します。また、循環参照しているオブジェクトの回収もできなくなります。
FlashのDRCではこの欠点を補うためにマーク&スイープによる支援を受けています。このマーク&スイープですが、実装を少し見る限りライトバリア(write-barrier)も使っているようなので、普通の(伝統的な)マーク&スイープではないことがわかります。”White”, “Black”, “Gray”という単語を見かけたのでどうやらオブジェクトの色塗りをしているようです。
ここまでが、遅延参照カウントの説明になります。
——————–
今回は対象がFlashということで、主にデザイナー寄りの方をターゲットにして書きました。スタックやヒープといった言葉を使わず、載せているコードも平易なものに限ったので、どんな処理をしているかは理解できたのではないでしょうか。その分詳細な説明はできなくなってしまいましたが、もしその辺りに興味のあるデザイナーさんがいればMMgcを読んでみるといいと思います。
また、もう1つのアルゴリズムである Backed by incremental conservative mark/sweep collector については思っていたより読むのが大変そうなので、モチベーションが上がったらいつか続きを書きたいと思います。
最後に、
FlashのGCについて調べると(例えば “flash 参照カウント” とかで検索すると)、僕がここで書いた内容とかみ合わない記事が出てきたり、影響力の大きい有名サイトが間違ったことを書いている記事を参考にしていたりします。ただ、僕自身もMMgcを全て読んでから書いたわけではないので、このエントリーも含めて判断は慎重にお願いします。
、とは言いつつも、あんまり難しく考えずに楽しくActionScriptを書くといいんじゃないかなと僕は思っています。