可変長配列
可変長配列のはなしだ。ありがちな実装としては、
struct vararray
{
int size;
int pos;
hoge **buffer;
};
void append( vararray *arr, hoge *obj )
{
if ( pos >= size ) {
char *oldbuf = buffer;
buffer = malloc( sizeof(hoge*) * size * 2 );
memcpy( buffer, oldbuf, sizeof(hoge*) * size );
size *= 2;
free( oldbuf );
}
buffer[pos] = obj;
pos++;
}こんな感じだろう。話をややこしくするためにreallocは使わないとする。（ややこしくしたほうが書いてて楽しいので）
こういう実装と、メモリのフラグメンテーションについて考える。
単純に実装されたアロケータの場合、こいつだと、メモリプールの分断が起きる。単純なアロケータというのは、K&Rに書いてあったアレみたいなやつのことだとしておく。
まず、mallocする前のメモリプールの状況をこんな感じだとしておく。
古いバッファとは、領域拡張する前のbufferの内容だとする。
+------+-----------------------------+---------------------------------- |(何か)| 古いバッファ(N byte) | 使われてない領域 ... +------+-----------------------------+----------------------------------
んで、malloc呼ばれた直後がこんな感じ。
-------+-----------------------------+--------------------------------------+--- |(何か)| 古いバッファ(N byte) | 新しいバッファ(N*2 byte) |使われてない領域 +------+-----------------------------+--------------------------------------+--
んで、コピーして、freeしたあとが、
+------+-----------------------------+--------------------------------------+--- |(何か)| 使われてない領域(N byte) | 新しいバッファ(N*2 byte) |使われてない領域 +------+-----------------------------+--------------------------------------+--
こんな感じ。使われてない領域が分断される。
そこで、次のようにする、というのはどうだろうか。
struct vararray
{
int size;
int pos;
hoge **buffer;
};
void append( vararray *arr, hoge *obj )
{
if ( pos >= size ) {
char *oldbuf = buffer;
char *padding = malloc( sizeof(hoge*) * size );
char *tmp = malloc( sizeof(hoge*) * size );
memcpy( tmp, oldbuf, size * 2 );
free( oldbuf );
free( padding );
buffer = malloc( sizeof(hoge*) * size * 2 );
memcpy( buffer, tmp, size * 2 );
size *= 2;
free( tmp );
}
buffer[pos] = obj;
pos++;
}まず、謎の領域paddingと一時領域tmpの確保。こいつのサイズは古いバッファと同じとする。
-------+-----------------------+------------------------+----------------------+----- |(何か)| oldbuf(N byte) | padding(N byte) | tmp(N byte) | 使われてない領域 +------+-----------------------+------------------------+----------------------+-----
oldbufの内容をtmpにコピーしたあと、oldbufとpaddingの解放
-------+------------------------------------------------+----------------------+----- |(何か)| 使われてない領域(N*2 byte) | tmp(N byte) | 使われてない領域 +------+------------------------------------------------+----------------------+-----
新しい領域の確保
-------+------------------------------------------------+----------------------+----- |(何か)| 新しい領域 (N*2 byte) | tmp(N byte) | 使われてない領域 +------+------------------------------------------------+----------------------+-----
tmp の内容を新しい領域にコピーしたあと、tmpの解放
-------+------------------------------------------------+---------------------------- |(何か)| 新しい領域 (N*2 byte) | 使われてない領域 +------+------------------------------------------------+----------------------------
これで、どう？
一回無駄に領域コピーが発生しちゃうんだけど、まあ、そこらへんは目をつぶる、ということで。そもそも、コピー時間が問題になっちゃうほど大きな領域の場合、上みたいにまるごと領域コピーしちゃうような可変長データ構造を使うほうが悪いのだ。（適当）
でも、今のlibcのアロケータだったら単純な実装してないと思うので、逆に断片化が増えるとか、reallocが賢いので、うまくやってくれるとか、チャンクヘッダがあるので実はうまくいかないだとか、そういうふうに考えなくもないけど、いちおう、ね、思い付いたのでもったいないなぁ、と思って書いた次第。
