その18 最低限のカスタムメモリアロケータ
メモリアロケータは、「メモリ欲しいんだけど～」という要求に応えてメモリを分け与えてくれる人です。C言語だとこれはmalloc関数、C++だとnew関数がその役を担ってくれます。カスタムメモリアロケータは、その機能を自前で実装した物を指します。
「え？何でそれを自前で実装するの？」と不思議に思うかもしれません。例えば、コンシューマ機での開発ではおおよそメモリアロケータを換装します。それはメモリ確保と解放の速度、耐久性、詳細なデバッグ情報を得るためと移植性を高めるためです。PC用のゲームを作る場合も、自分がどれだけのメモリを消費しているのか、メモリリークはしていないか、誰がいつどこでメモリを確保したのか、そういうメモリのデバッグ情報を見られるというのか安定したゲーム開発に必要になってきます。そういう情報はライブラリ提供のmalloc、newでは得られないため、メモリアロケータを自前で作る必要にかられるわけです。
メモリアロケータの役目は冒頭に挙げたように極めて極めてシンプルです。では、そんな単純な仕事をしてくれる一番最低限のカスタムメモリアロケータというのはどういう程度の物になるのか？言い方を変えれば「カスタムメモリアロケータには最低限どんな実装が必要になって来るのか？」。この章の目的はその見極めにあります。
① アホアホなメモリアロケータからスタート
メモリをアロケート（割り振り）する。これを考えるにはメモリのイメージがとっても大切です。メモリは言ってみれば「一直線にならんだマス」です：
マス一つが1バイト、そしてその一つ一つに番号が振られています。これが凄まじく広大な長さで40億個くらい繋がっているのがメモリ（32bit仮想メモリ）です。malloc関数を通して「メモリおくれ～」と要求した時、malloc関数はこの広大なメモリ直線の中から要求されたサイズ分を切り取って貸し出してくれます：
malloc関数が返してくれる貸し出しメモリの位置（ox0123456c）が重要で、この範囲がいらなくなったらこの貸し出し位置を「いらなーい」と宣言します。malloc関数で確保したメモリであればfree関数にこのアドレスを渡すと解放してくれます。たったこれだけの事をするのがメモリアロケータです。
どのようなメモリアロケータも自分が管理する大きなメモリブロックが最初に必要です。これはアロケータ内で確保する場合もあれば、外から与えてもらう場合もあります。今は大きなメモリブロックがすでに確保されているとしましょう。広大な土地の一部（でっかいメモリブロック）を手に入れた状態です：
プログラムが実行されるといずれこのでっかい土地の一部を貸し出して欲しいという要求がやってきます。この時、一番簡単なのは左端（メモリブロックの先頭ポインタ）から要求されたサイズだけどんどん切り出して貸していく事です：
残りの貸し出していないメモリブロックは「フリーメモリブロック」と呼ばれます。
この貸し出し過程をプログラムで再現するにはいくつか情報が必要です。まず、でっかいメモリブロックの先頭ポインタの情報は当然必須です。これがあれば一番最初のメモリ要求に応える事ができます。「100バイトを貸して～」と言われたら、先頭ポインタをそのまま返せばいいんです。しかし、そのままだと次の要求には応えられません。上の方法の場合「フリーメモリブロックの先頭ポインタ」を保存し、貸し出す度に更新する必要があります：
貸し出したらフリーメモリブロックポインタ位置を移動、また貸し出したら移動…これを繰り返せば、ほら、もう立派にメモリアロケータの役目の一つ「貸し出し」が出来てしまいました(^-^)。ただ、この使い捨ての権化のようなメモリアロケータの終焉があっという間に訪れる事は目に見えています。どんどん貸し出し要求が来て、フリーメモリブロックが消費されていき、最後には「貸し出し不可」になる…かと思いきや、それもままなりません。なぜなら、このアロケータは借りたメモリブロックサイズすら保存していないからです。恐ろしい事に、フリーとして用意してもらった領域すらはみ出し、世界を壊して終わります…(-_-;
という事で、単にフリーメモリブロックを貰っただけだと、メモリアロケータとして機能させられない事がわかります。ちゃんと機能させるにはアロケータの状態を保存する「管理領域」が絶対に必要になってきます。
② アロケータ管理領域
①のアホアホメモリアロケータは極めて簡単ですがデスマーチなアロケータでした。管理する体制がまるで無かったためです。①のお話で少なくとも、メモリアロケータの管理情報として、
・ 確保しているメモリブロックサイズ
・ フリーメモリブロックへのポインタ
が無いといけない事がわかりました。これらの管理情報は通常最初に確保したフリーメモリブロックの先頭にヘッダー情報として記述します：
管理情報は構造体として定義します。
struct AllocInfo {
unsigned int fullSize; // メモリブロック総サイズ
void* freeMemPtr; // フリーメモリブロックへのポインタ
};
構造体にしておけばアクセスするのも簡単ですし、何か追加の情報（フリーメモリの総量とか）が必要になったとしても拡張が容易です。また、拡張時にsizeof(AllocInfo)でその構造体のサイズを計算できる点も非常に大きいです。
でっかいメモリブロックを最初に貰った時、実際に使える真のフリー領域は、でっかいメモリブロックのサイズからこの管理領域を引いた分となるわけです。これで少なくとも確保メモリをはみ出してまで貸し出すという失態は防げますね。とは言え、①のアホアホアロケータは使い捨て体質ですから、このままではアロケータとして最低限の仕事すらこなせません。使い捨てではなくて持続的にするには、貸し出したメモリを解放して再利用する仕組みが絶対に必要になります。
③ 貸し出しメモリの管理情報
貸し出したメモリを再利用するには2つの大きな方法が取れます。一つは「貸し出した人が責任を持って返してくれる」制度にする方法です。malloc関数で借りたメモリはfree関数を借りた側が呼び出すことで返却しますね。newとdeleteの関係もしかりです。もう一つの方法は「貸した人が監視して回収する」方法です。これは「ガベージコレクション」という名前が付いています。借りた方は必要無くなったらほおっておいて良くて、貸した人が何らかのタイミングで勝手に回収作業をしてくれます。借りた方に責任が無いのでとっても楽なんですが、回収する側の実装は吐く程大変になります。よって今回の最低限のメモリアロケータでは、実装が楽な前者の方法を採用します。
メモリを借りた人が「もういらなくなったので返します～」と返却してくれました。具体的には借りたメモリの先頭ポインタを返却してくれます。しかし、②までのメモリアロケータだと貸したメモリのサイズを誰も覚えていないので解放しようがありません。図で表すと、上の貸し方はこんなざっくりとした状況になっているというわけです：
オレンジの部分のどこを解放するのか、さっぱりわからないですよね(^-^;
では貸し出したメモリサイズを誰に覚えてもらうかですが、これは明らかに「貸したメモリにこっそりくっつけておく」のが簡単です：
オレンジの部分が貸し出す総サイズで、先頭に付いている黄色い部分が貸し出し管理領域となります。今は貸出サイズを格納していますが、この黄色い部分も構造体として定義しておけばそのサイズも自明に求められます。ところで、上のように書くと、
struct MemInfo {
unsigned int size; // 貸し出しメモリサイズ
char mem[100]; // メモリブロック
};
という構造体を作るのかなと勘違いする方もいるかもしれません。構造体内の配列はコンパイル前に決まっていなければならないので、これだと自由にメモリサイズを指定できません。なので：
struct MemInfo {
unsigned int size; // 貸し出しメモリサイズ
char mem[0]; // メモリブロック
};
とサイズゼロの配列を宣言します。そしてこの構造体のすぐ後ろに指定のサイズ分だけメモリブロックがあるという「前提」にしてしまうんです。これで貸し出すメモリのポインタはMemInfo::memとなるわけです。ただ最近のコンパイラだとサイズゼロの配列を作ると怒られるかもしれません。その場合はあきらめて、
struct MemInfo {
unsigned int size; // 貸し出しメモリサイズ
char* getMem() {
return (char*)this + sizeof( MemInfo );
}
};
上のようにgetMemメソッドを用意して間接的にアクセスする仕組みを提供しましょう。
さて、これでアホアホアロケータは貸し出したメモリが返却された時に何バイト解放すれば良いか分かるようになりました。
④ フリーメモリリスト登場
実際に貸し出しポインタが返却されてきたとしましょう。貸し出し管理領域は返却されてきたポインタのすぐ前にあり、そこから貸し出しサイズも得る事ができます。で、解放ですが、試しに貸し出しヘッダー情報を含めゼロとかで埋めるとすると…：
こんな感じで空っぽに出来ます（点線部分）。出来ますが…この領域、もう二度と使えません。なぜなら、誰もこの「解放して空いたメモリの位置とサイズ」を覚えていないからです。
上の点々の範囲は確か貸し出しメモリ管理領域＋要求サイズで、それは元々貸し出しメモリ管理領域にちゃんと情報が格納されていたのでした。そこで、解放する時に更地にするのではなくて、貸し出しメモリ管理領域は残しておきます：
そして、この貸し出し管理領域へのポインタをメモリアロケータの管理領域に保存します：
これでメモリアロケータ自体が再利用可能なメモリを一つキープした状態になります。次にメモリを貸し出す時、例えばまた「100バイト貸して～」と言われたら、未使用のフリーメモリブロックではなくてキープしてある再利用可能メモリを貸し出せば、リサイクルが1回まわる事になります。
では、返却が複数あった時はどうするか？上のメモリアロケートの管理領域だと1個しかフリーメモリをキープできません。これを不特定多数キープするには「フリーメモリリンクリスト」を作るのが一つの手です。フリーメモリリンクリストとは、その名の通りフリーメモリが連結して連なっているリンクリストです。リンクリストを作るには、前後の物と手を繋ぐための「リンクポインタ」が必要です。これは、貸し出したメモリの管理領域に予め追加しておきます。これがあると次の図のように複数のフリーメモリ同士をつなぐ事ができるようになります：
アロケータの管理領域にはリンクの最後尾のフリーメモリへのポインタを覚えておきます。返却されフリーメモリが増える度に、その最後尾フリーメモリに連結してアロケータの最後尾フリーメモリへのポインタを更新すれば、フリーメモリがいくら発生しても大丈夫です。メモリアロケータにおいてこの「フリーメモリリスト」は欠かせない物なのです。
⑤ 一番最初からフリーメモリリンクリストで管理
ところで、④までの段階で「未使用のフリーメモリ」と「再利用のためのフリーメモリリンクリスト」という2つのフリーメモリが存在しているのにお気付きでしょうか？これ、どっちも「フリーメモリ」ですよね。両方を管理するのは冗長なので、未使用のフリーメモリも「再利用のためのフリーメモリリンクリスト」にくっつけてしまいましょう。そうすれば、もはやフリーメモリリンクリストのみで貸し出しの管理ができます。
ただ、そうなりますと最初の方で考えた貸し出し方法が白紙になってしまいます。フリーメモリリンクリストからメモリを貸し出すにはどうしたら良いのでしょうか？
⑥ フリーメモリリンクリストから要求メモリを貸し出す
ここで、一番最初の状態に立ち返りましょう。最初におっきなメモリブロックを貰い、その頭にアロケータの管理領域を作ります。残りの部分がフリーメモリブロックになるのですが、これには最初からフリーメモリリンクリストに登録してしまいます。すると、下図のようなシンプルな状態ができあがります：
メモリを要求されたら、アロケータの管理領域にあるフリーメモリブロックから適したメモリを探し出します。ただ、この「検索」を考えると切りがありませんので、今は単純にリンクリストを線形に辿っていくとします。初期状態ではフリーメモリリストには上のでっかいブロックが一つだけ登録されています。貸し出し時にそのでっかいリストをそのままどーんと渡す…わけはありません(^-^;。
フリーメモリリストから最終的にメモリを貸し出すには、
・ リストからフリーメモリを一つ取り出す
・ そのフリーメモリから要求サイズを切りだせるかチェック
・ 切り出し作業
・ 要求サイズ分の切り出しが出来ない場合、そのまま渡せるかチェック
・ そのまま渡せない場合は次のフリーメモリをリストから取り出す
という作業をしなければなりません。メモリ切り出しの作業、実は地味に面倒くさいのです。
フリーメモリから要求サイズを切りだせる（分割できる）かどうかは、フリーメモリのフリーブロック部分のサイズが「メモリ管理領域サイズ＋要求サイズ」より大きいかで判断できます。ぴったりだったらそのまま貸し出せば良く、未満だったら使えないので次のフリーリストを取り出します：
分割可能な場合、元のフリーリストの後ろに要求分確保します。そして、分割した残りの部分のサイズを再計算し、メモリ管理領域に記録してあるサイズを書き換えます。こうすれば、リンクリストを更新せずに済みます。
これで初期状態のでっかいフリーメモリから適切な大きさに切りだして利用する算段ができました。ここまで来ればもはやアホアホメモリアロケータではありません(^-^)。でも、このメモリアロケータを使い続ける事は出来ないのです。なぜか？
⑦ フリーメモリのマージ
⑥までのメモリアロケータは、フリーメモリリストから要求されたメモリを切り取っては使い、切り取っては使いという作業を繰り返します。という事は、最初の大きなメモリブロックは細切れに分断されてしまいます。問題はその先で、その分断されたメモリはそのサイズ以上にはもうなれません。しかも、分断可能な小さなメモリを要求されるとさらにどんどん細かくなっていってしまいます。結局、長く使っているとフリーメモリリストには沢山あまっているのに適正サイズの物が無いという事態が確実に起こります。
メモリ返却時のかなり多くの場合に、以下のような状況が生じています：
真ん中の返却メモリの前後に大きなフリーメモリがあります。返却メモリをフリーリストに連結する前に、この前後のメモリの使用状況を調べ、それが使用されていないのであれば、それらを一まとめにした大きなフリーメモリブロックとしてまとめる（マージする）と、フリーメモリの細分化を防止できます。
その「前後を調べる」というのは、上の図だと目で判断できるのですが、今の返却メモリが持っているヘッダー情報だと後方しかわかりません（返却メモリのサイズから後方のメモリ管理領域へジャンプできるから）。前方のフリーメモリのメモリ管理領域に戻るには、そのサイズを取得できなければなりません。さてどうするかです…。
一つの方法として、フリーメモリの最後尾にサイズ情報を埋め込んでしまうという手があります：
下にピックアップした要求メモリブロックを含んだ貸し出しメモリの最後尾にくっ付いている青い部分、ここに貸し出しメモリ全体のサイズを格納しておきます。こうすると、メモリ管理領域のすぐ前にある値を使い、前のメモリ管理領域までジャンプできるようになります。
前後のメモリブロックが使用中なのかフリーなのかは、ヘッダー情報内にあるリンクリストに有効な連結ポインタがあるかどうかで判断できます。もしくはメモリ管理領域に使用中か否かのフラグを含めても良いと思います。直後のメモリがフリーの場合、そのメモリをごっそり取り込んでしまえます。直前のメモリがフリーの場合、自分自身が直前のメモリにとりこまれます。マージしたフリーメモリはリンクから外し、最終的に大きくなったフリーメモリを改めてリンクに連結させれば、マージ作業終了です：
マージ作業は少し面倒ではあるのですが、これはメモリアロケータの耐性を保つ上で必須です。
⑧ 残された大きな課題は「適切なフリーメモリの検索」
ここまでで、シンプルなメモリアロケータの基軸はほぼ揃っているのですが、一番重要な所がすっぽり抜けています。それは「貸し出しの際の適切なフリーメモリをどう検索するか？」です。
今回のフリーメモリリンクリストには色々な大きさのフリーメモリが直列に無秩序に繋がっています。もし「2749バイト貸して下さい」と要求された時、このフリーメモリリンクリスト内から適切なフリーメモリを探し出さなければなりません。しかし単純なリンクリストは線形検索になってしまうため検索効率は最悪です。つまり、このメモリアロケータは、機能はするのですが使い続けるてフリーメモリが増えれば増える程遅くなってしまう事がわかります。実は、メモリアロケータを高速化する工夫すべき最大の箇所はこの「適切なフリーメモリの検索」なのです。
その工夫の一つがアルゴリズム編で取り上げているTLSFアロケータです。このアロケータでは、フリーメモリリストを細かいサイズ別に分類して管理する事で、要求されたメモリにベストフィットするフリーメモリをほぼノータイムで検索できるようになっています。これ以外にもいくつものメモリアロケータのタイプがあります。詳しくはWikipediaをご参照ください（Wikipedia: Memory Management: http://en.wikipedia.org/wiki/Memory_management）。
この章では最低限の機能を提供するメモリアロケータに必要な項目を取り上げるのが目的であるためフリーメモリの検索については触れませんが、Web上には色々なアルゴリズムが紹介されていますので、何か一つ取りあげて実装してみると勉強になると思います(^-^)。それにしても、メモリアロケータはやっぱり中々面倒です。「ゲームプログラマにとってメモリアロケータは洗礼である」。諸先輩が仰った言葉は本当にその通りですね。皆さん、精進ですw
