固定長のメモリアロケータ


オブジェクトをヒープメモリ領域に作るとき、以下のように new 演算子を使ってプログラムするよね。

この new 演算子によるヒープメモリの取得は、1つ1つのメモリをシンプルに取得するだけで、ある程度の数のメモリを取得するときのための最適化はされていないので、たくさん実行するときは実はちょっと効率が悪いんだ。例えばサイズが 4 byte の CRObject4 というクラスのオブジェクトを作るときのことを考えよう。このクラスのオブジェクトを new で生成するとき、実際に消費されるのは 4 byteではなく、4 byteから 32 byteくらいのメモリが余計に消費されるんだ。図に書くとこうなるよ。黄緑色の部分が CRObject4 のメモリの 4 byte だけど、濃い緑色の部分も一緒に消費されてしまうんだ。この領域は OS が使用するよ。

そして、使用できるヒープメモリ領域は、FirstFit のアルゴリズムで線形に検索するので、メモリの空き具合(フラグメンテーション)によっては空き領域がすぐに見つからなくて、実行速度が遅くなるんだ。そして delete が呼ばれてメモリを解放するときも単に使っていたメモリを開放するだけじゃなくて、FirstFitの問題にあったように隣り合う空メモリ領域の結合する処理を行なうから、その分、delete も遅くなるよ。
 First Fit

なので new 演算子によるオブジェクトの生成と delete 演算子によるオブジェクトの破棄は、大量に行なうとメモリも無駄に多くなるし、速度も遅くなってしまう可能性があるんだ。だから、大量にオブジェクトを生成したり破棄したりするソフトウェア(たとえばシューティングゲームとか)は、メモリのアロケーションをソフトウェア自身が行なうようにしていることがあるよ。これをメモリアロケーションと言って、そのクラスや実装のことをメモリアロケータと呼ぶよ。

以下はメモリアロケータのサンプルプログラムだよ。これは"Modern C++ Design" (Andrei Alexandrescu 著 ピアソン・エデュケーション)の4章に書いてあるプログラムをベースにコードレジュメのC++の記載方法に合わせて書き直したものだよ。
F11キーでフルスクリーンモード、Escキーで元に戻ります。

メモリアロケータを使用したいクラスへの実装はこうなるよ。
F11キーでフルスクリーンモード、Escキーで元に戻ります。

メモリアロケーションというのは、要するに大きめのサイズのメモリを必要な時に自分で取得しておいて、それを小分けにして使うんだ。そうすれば OS が管理する部分を減らすことができるし、フラグメンテーションによるメモリの探索と結合のオーバヘッドを削減することができるんだ。メモリアロケータを使えば、delete のときの周辺の空きメモリとの結合の処理を行なわずに、単に使用中かそうでないかのフラグだけでよくなるよ。

上のサンプルプログラムを使用したときのメモリのイメージは以下のようになるよ。まず、このメモリアロケータ(FixedAllocator)は m byte の固定長のメモリをアロケーションするよ。Chunk というクラスの m_pData というメンバ変数で、m byte × n 個分のメモリをまとめて取得しているよ。こうやってまとめて取得しておけば、OSが使用する領域(濃い緑色の部分)は1個で済むからメモリ消費量を削減できるんだ。m byte のメモリ領域をブロック、そして ブロック n個分のメモリの塊をチャンクと言って、Chunkクラスが管理するよ。n+1 個以上のメモリが必要になったら、次のチャンクを作るんだ。このチャンクはFixedAllocatorというクラスの中で vector で管理されているよ。

そして、このブロック1つ1つは単方向リストになっているんだ。つまり、50 行目のところで m_pData の中でブロックごとに、ブロックの先頭の 1 byteに整数をセットしているけど、これは次のブロックのインデックスをセットしているんだ。

下の図はブロックのサイズが 4 byteのときのメモリイメージだけど、ブロックの先頭の 1 byte で、そのインデックスを整数で保存しているよ。背景色が白で斜線が入っているところがそれだよ。

チャンクは最初の状態ではブロックが1つもアロケートされていないから、上の図の Chunk x の状態になっていて、このときは次のブロックのインデックスがセットされているんだ。そして new が呼ばれてChunk::Allocate が実行されると m_firstAvailableBlock には 0 が指定されているから、先頭のブロックがCRObject4オブジェクトのためにアロケートされるけど、アロケートが終わると 65行目でやっているように次のインデックスを m_firstAvailableBlock にセットするんだ。こうすると、Chunkクラスは次に new が呼ばれて Chunk::Allocate を実行するときに 次にアロケートするブロックがすぐにわかるんだ。そして delete が呼ばれて Chunk::Deallocate が呼ばれたときは今度は88行目でやっているように解放するブロックの先頭の 1 byteに、そのときの m_firstAvailableBlock を入れて、m_firstAvailableBlock には解放されたばかりのブロックのインデックスをセットするんだ。こうすると Chunk::Deallocate すると単方向リストが1つ伸びるんだ。CRObject4 が delete される順番はユーザが決めるから、プログラムが進むと Chunk 2 のように歯抜けのような形になるけど、そのときも単方向リストは飛び飛びになっているよ。こうやって単方向リストにしておくことによって、new が呼ばれたときに次のブロックを高速に返すことができるんだ。

ちなみに Chunk 2 の状態は例えば256個のすべてのブロックがアロケートされた後、252、254、0 の順番でブロックが解放されるとこうなるよ。

そして FixedAllocator クラスは、メモリの取得と解放が行なわれる最中は m_allocChunk と m_deallocChunk にそれぞれ最後にブロックが取得されたチャンクと解放されたチャンクを記録しておいているよね(131行目と175行目)。これは、次回 new が実行されたときは前回取得したチャンクならすぐに空のブロックがある確率が高いのと、次回 delete されたときは前回解放されたブロックがあるチャンク上のものだろうという仮定で高速化を狙っているんだ。これは特に解放の方はうまくいくケースとうまくいかないケースがあるよ。なぜなら、deleteするオブジェクトはランダムの可能性だってあるから、その時はその過程はまったく成り立たなくなってしまうよ。そうなると 164行目の for ループで線形検索することになるけど、これはとても遅いので改善の余地があるね。

そしてこのメモリアロケータは、318、319、335、336行目で new と delete をオーバライドして CRObject16 クラスと CRObject32 クラスに実装されているよ。CRObject16とCRObject32は、8byteのdouble型の変数と仮想関数を持っているからそれぞれのクラスのメモリサイズは16byteと32byteになるよ(このマシンは64bitのCPUだから仮想関数の関数ポインタのサイズは 8 byteだよ)。




メモリアロケータは比較的、短いコードでほぼ狙い通りにメモリを削減できるし、高速化もできるけれども、オブジェクトのメモリサイズ、ソフトウェアが使用されるときに生成および破棄されるオブジェクトの数、そして生成と破棄のパタンから、ブロックの数やメモリアロケータの仕組みをチューニングする必要があるよ。つまり万能なメモリアロケータというのは難しいんだ。例えば "Modern C++ Design" では、SmallObject という小さなサイズのクラスを主な対象にしているようで、1 byte 単位でブロックを作れることがメリットとして書かれているけれど、4 byte とか 8 byte 以上のサイズの場合は 1 byte の中にインデックスを書く必要もなくなるし、1万個以上のオブジェクトが生成されるようなソフトウェアの場合はブロックのサイズは 256個だとちょっと少なすぎるよ。今回の問題はそのチューニング作業を行なう必要があるよ。





初めての方へ:このページは、このサイトで用意しているプログラミング問題の解答と解説のページです。このサイトではブラウザ上からプログラミングができます。会員登録(無料)して、プログラミングしてみませんか?
新規登録



ログイン
メールアドレス:

パスワード:



パスワード紛失

新規登録