読者です 読者をやめる 読者になる 読者になる

メモリのフラグメンテーションとGC - GC Advent Calendar

Garbage Collection Advent Calendarの13日目の記事です(よくぞここまで…)。

フラグメンテーションの話。GC Handbookには以下の2種類のfragmentationがあることが記されています。

  1. external fragmentation
  2. internal fragmentation

それぞれ見てみましょう。

external fragmentation

external fragmentationはみなさんがよく知ってるやつだと思います。
シンプルなfreelistによるメモリアロケータ(K&R mallocとか)をずーっと使い続けていると、そのうちにfragmentationが発生して、以下の図のように小さな領域が飛び飛びに空いた状態になる可能性があります。

こうなると合計の空き領域は要求サイズを満たすものの、実際には外側に渡せるサイズはとても小さなものになってしまいます。
外向きからの要求に対し、利用できるスペースがなくなってしまうため、external fragmentation(外部フラグメンテーション)と呼ばれます。

internal fragmentation

それじゃあ、ということで小崎さんのglibc mallocの資料にも登場しますが、要求サイズによって分類する戦略が考えられます。
これはどのくらいのサイズ粒度で分類するか、というところが調整のポイントです。
以下の図のように、あまりに大きな粒度で分類すると要求サイズによっては無駄な部分がでてしまうのです(要求サイズをもっとも近いサイズに丸めるため)。

内部的に無駄な領域がでてしまいますね。このようなチリも積もれば山になってしまいます。
これがinternal fragmentationというものです。

ふらぐめんてーしょんのない、むてきのあろけーたあ!

じゃあメモリアロケータでフラグメンテーションをなくすことができるのでしょうか?
実はメモリアロケータでは「完全にフラグメンテーションを除去できない」ということがわかっています。
ユーザが要求するメモリのサイズとその順番は事前に知ることはできませんし、もしわかったとしてもそれを効率良くアロケーションするのはNP-hardなのだそうです(Storage allocation is NP-hard

そこで颯爽とGCさん!!

メモリアロケータ単体だとフラグメンテーションを除去できませんが、すでにご存知の通りGCのCopyingやMark-compactを併用することでフラグメンテーションを解消することができます。
メモリアロケータを言語処理系が自前で作る利点はこういうところにもあると言えます。
参照局所性もアップしますしね。

malloc/freeみたいなメモリアロケータではCompactionといったことはできません(基本的には)。割り当ててたメモリのアドレスが変わったら大変ですからね(^_^;)

ただし、CopyingやMark-Compactなどで除去するのは大抵がexternal fragmentationです。
まあ、copyingがあれば、Segregated-fits allocationではなくてfree-list allocationで充分なのかなという気がしますねえ。