AMemMan （メモリ管理）
(0)
- 標準関数のmalloc/free/realloc/callocがあまり使いやすくない気がするので、自分で作ってみました。
(1)
- [自動開放#1]
- 当たり前ですが、メモリを確保したら使い終わった後に開放しなければいけません。しかしたまに煩雑になってやり忘れます。そうするとそれはメモリリークになります。
p0 = malloc(size0);
p1 = malloc(size1);
p2 = malloc(size2);
...
free(p2);
free(p1);
free(p0);
- 上記は簡単な例で、これで間違えるようではプログラミングの適性がないのではと疑われるレベルですが、しかしmallocが並んでいなくて、mallocするかしないかが条件によって異なるとかになってくると、だんだんfreeし忘れのリスクが出てきます。
- もしこれがこう書けるようになったらいいと思いました。
p0 = malloc_autoRelease(size0);
p1 = malloc_autoRelease(size1);
p2 = malloc_autoRelease(size2);
...
release();
- これはmallocしたときにその情報が記録され、release()ではその情報をもとに正しい順序で（＝登録とは逆順で）解放します。こういう仕組みがあれば気を張ってなくてもメモリリークはしません。プログラムを改造してmallocが増えても大丈夫でしょう。
- [自動開放#2]
- メモリ開放だけではなく、オブジェクトのデストラクタ呼び出しなどもやり忘れる可能性があります（それを全部自動でうまくやってくれるのがC++なのですが）。だからデストラクタの自動呼出し機能も付けました。
p0 = malloc_autoRelease(size0);
p1 = newObject_autoRelease(...);
...
release();
- さらに、自動管理の範囲も設定したいです。
void myFunc()
{
ARP *pool = newAutoReleasePool();
p0 = malloc_autoRelease(pool, size0);
p1 = newObject_autoRelease(pool, ...);
...
releaseARP(pool);
}
- こうすればmyFuncを呼ぶ前にautoReleaseしたものは、releaseARP(pool)では解放されません。つまり自動開放プールは複数つくることができて、malloc時にどのプールに登録するか選べるのです。
- [メモリ確保・解放のアルゴリズム選択]
- 標準のmalloc/freeは汎用的に作られてはいますが、使われ方によっては十分な性能がでません。つまりあまり速くない場合があるのです。そんな場合、確保や解放のアルゴリズムが別のmalloc/freeを使えば、十分な性能が出るようになります（分かりやすいようにあとでベンチマーク例を示します）。
- 一つのアプリの中に複数のmallocアルゴリズムが共存できます。標準のmalloc/freeをそのまま使うだけのアルゴリズムA、別のアルゴリズムB、さらに別のアルゴリズムCがあったとして、Bはメモリが足りなくなるたびにAに追加のメモリを要求して、自分の管理下にあるメモリだけを管理すればいいのです。Cも足りなくなればAからメモリをもらえばいいのです。そしてBやCは管理が終わったメモリをAに返します。・・・こうして複数のメモリ管理アルゴリズムが競合せずに共存することになります。
- [統合]
- それでこのメモリ管理アルゴリズムの選択と自動開放プールの両方を統合して、AMというクラスを作りました。もとはAMemManという名前でしたが、使用頻度が非常に高く、短い名前の方が便利だということになってこうなりました。
- これにより、たとえば二分木アルゴリズムのように適宜mallocやfreeをするライブラリは、オブジェクト生成時にAMのポインタを渡すことになりました。そうしないとどうやってmalloc/freeしたらいいか指定できなくなるからです。これらのクラスライブラリは、AMのポインタを自分のオブジェクト内に覚えておいて、必要に応じて使います。だからメソッド関数を呼び出す際に指定する必要はありません。
- この構造になるとデバッグがやりやすいです。デバッグ対象に渡すAMには、例えば「合計容量が1MBを超えたらわざとout-of-memory（＝NULL）を返すようにする」のような小細工を簡単に入れられます。malloc/freeのログを取らせることもできます。malloc/freeに不整合がないか厳密に確認することもできます。こうして、メモリ不足になった時の挙動の確認や、メモリリークをどこで起こしているかの調査など、色々なことができます。
- [メモリリーク検出]
- ADbgLvを1以上にしておけば、AM_dst()したときに開放し忘れのメモリがないか確認するようになります。これが思っていたよりも便利で、いつも使うようになりました。
(2)
- (2-1)例えばこういうコードは、標準のmalloc/freeの苦手なパターンです。
void func21()
{
int i, j, n = 1024 * 1024, **a = malloc(n * sizeof (int *)), *t;
aXorShift32_seed(0); // 乱数を同じseedで初期化.
for (i = 0; i < n; i++)
a[i] = malloc(64);
for (i = 0; i < n; i++) { // a[i]をシャッフルする.
j = aXorShift32() & (n - 1);
t = a[i]; a[i] = a[j]; a[j] = t;
}
for (i = 0; i < n; i++)
free(a[i]); // ランダムな順番で開放される.
free(a);
}
- (2-2)これに対してこういうコードを書くことができます。
void func22(AM *m2, AM *m)
// m2は64バイトの確保・解放のみに特化したメモリ管理アルゴリズムを想定.
{
int i, j, n = 1024 * 1024, **a = AM_alc(m, 0, n * sizeof (int *)), *t;
aXorShift32_seed(0);
for (i = 0; i < n; i++)
a[i] = AM_alc(m2, 0, 64);
for (i = 0; i < n; i++) {
j = aXorShift32() & (n - 1);
t = a[i]; a[i] = a[j]; a[j] = t;
}
for (i = 0; i < n; i++)
AM_fre(m2, a[i], 64);
AM_fre(m, a, n * sizeof (int *));
}
// void *AM_alc(AM *m, int flag, AInt siz) : flagを1にすると、autoRelease指定になる. 2にするとcalloc相当になる. 3だと両方.
// void AM_fre(AM *m, void *p, AInt siz) : AM_fre()では、解放するときにもsizを指定するというルールになっている(面倒を増やしてすみません).
- (2-3)速度の比較
| func21() | 0.228秒 | mallocとfree |
| func22(am0, am0) | 0.233秒 | am0はmalloc/freeをそのまま使うだけのアルゴリズム、オーバーヘッドが増えた分だけ少し遅い |
| func22(m2, am0) | 0.076秒 | m2は64バイトのメモリを高速に管理できるアルゴリズム、func21よりも3.0倍速い結果になった |
(3) ver.1.10 [2024.09.20] (321行)
AClass(AM) {
void *alc, *fre, *rlc, *arp, *rls, *dst, *p0, *p1; AInt n, total;
};
#if 1 // AMap11関係の範囲を示すためのif.
AClass(AMap11) {
void *add, *del, *sch, *dst;
AInt n1, n, flags;
AM *m;
};
void AMap11_add(AMap11 *w, void *k, void *v);
int AMap11_del(AMap11 *w, void *k);
void *AMap11_sch(AMap11 *w, void *k, void *v0);
void AMap11_dst(AMap11 *w);
#endif
#if 1 // クラス汎用エラー処理関係の範囲を示すためのif.
#if (ADbgLv >= 1)
extern AM *amDbg;
extern AMap11 *AMapLst11_opn(int f, AM *m);
AStatic AMap11 *(*aDbg_namMapOpn0)(int, AM *) = AMapLst11_opn; // デフォルト関数.
#endif
AInlineStatic void aDbgSetNam(AMap11 **map, void *w, const char *n)
{
#if (ADbgLv >= 1)
if (*map == 0)
*map = aDbg_namMapOpn0(0, amDbg);
AMap11_add(*map, w, (void *) n);
#endif
}
AStatic void aClassErr(AMap11 **map, void *w, const char *fnc, const char *f, va_list ap)
{
#if (ADbgLv >= 1)
if (*map == 0)
*map = aDbg_namMapOpn0(0, amDbg);
fprintf(stderr, "\n%s(%s): ", fnc, (char *) AMap11_sch(*map, w, ""));
#else
fprintf(stderr, "\n%s: ", fnc);
#endif
vfprintf(stderr, f, ap);
fprintf(stderr, "\n");
exit(1);
}
#endif
AStatic AMap11 *AM_dbgNam = 0;
AInlineStatic void AM_dbgSetNam(AM *w, const char *n) { aDbgSetNam(&AM_dbgNam, w, n); }
AStatic void AM_err(AM *w, const char *fnc, const char *f,...) { va_list ap; va_start(ap, f); aClassErr(&AM_dbgNam, w, fnc, f, ap); va_end(ap); }
AInlineStatic void AM_arp(AM *w, void *f, void *v0, void *v1, void *v2)
{
void (*arp)(void *, void *, void *, void *, void *);
arp = w->arp; arp(w, f, v0, v1, v2);
}
AInlineStatic void AM_fre(AM *w, void *p, AInt sz)
{
if (p != 0) {
void (*fre)(void *, void *, AInt);
fre = w->fre; fre(w, p, sz);
}
}
AStatic void *AM_alc(AM *w, int f, AInt sz)
// f= 1:arp, 2:clr, 4:err
{
void *(*alc)(void *, AInt);
alc = w->alc; void *p = alc(w, sz); // nやtotalは下位が管理する.
if (p == 0) {
if ((f & 4) == 0) AM_err(w, "AM_alc", "out of memory");
return 0;
}
if ((f & 2) != 0) memset(p, 0, sz);
if ((f & 1) != 0) AM_arp(w, w->fre, w, p, (void *) sz);
return p;
}
AStatic void *AM_rlc(AM *w, AInt f, void *p, AInt sz0, AInt sz1)
{
void *(*rlc)(void *, void *, AInt, AInt);
rlc = w->rlc; p = rlc(w, p, sz0, sz1);
if (p == 0) {
if ((f & 4) == 0) AM_err(w, "AM_rlc", "out of memory");
return 0;
}
if ((f & 2) != 0 && sz0 < sz1) memset(((char *) p) + sz0, 0, sz1 - sz0);
// rlcはarpに対応しない.
return p;
}
AInlineStatic void AM_rls(AM *w) { void (*rls)(void *); rls = w->rls; rls(w); }
AInlineStatic void AM_dst(AM *w) { void (*dst)(void *); dst = w->dst; dst(w); }
AInlineStatic void *AM0_alc(AM *w, AInt sz)
{
void *p = malloc(sz);
#if (ADbgLv >= 1)
if (p != 0) { w->n++; w->total += sz; }
#endif
return p;
}
AInlineStatic void AM0_fre(AM *w, void *p, AInt sz)
{
free(p);
#if (ADbgLv >= 1)
w->n--; w->total -= sz;
#endif
}
AInlineStatic void *AM0_rlc(AM *w, void *p, AInt sz0, AInt sz1)
{
void *q = realloc(p, sz1);
#if (ADbgLv >= 1)
if (q != 0) {
if (p != 0) { w->n--; w->total -= sz0; }
w->n++; w->total += sz1;
}
#endif
return q;
}
AClass(AM0_Sub) { void *f, *v0, *v1, *v2, *n; };
AInlineStatic void AM0_arp(AM *w, void *f, void *v0, void *v1, void *v2)
{
AM0_Sub *s = AM_alc(w, 0, sizeof (AM0_Sub));
s->f = f;
s->v0 = v0;
s->v1 = v1;
s->v2 = v2;
s->n = w->p0;
w->p0 = s;
}
AStatic void AM0_rls(AM *w)
{
void (*f)(void *, void *, void *);
void *v0, *v1, *v2;
AM0_Sub *s, *n;
for (s = w->p0; s != 0; s = n) {
f = s->f;
v0 = s->v0;
v1 = s->v1;
v2 = s->v2;
n = s->n;
AM_fre(w, s, sizeof (AM0_Sub)); // 逆順にこだわるので、Subのfreの方が先.
f(v0, v1, v2);
}
w->p0 = 0;
}
AInlineStatic void AM0_dst(AM *w)
{
AM_rls(w);
#if (ADbgLv >= 1)
if (w->n != 0 || w->total != 0) AM_err(w, "AM0_dst", "error(n=%d, total=%d)", w->n, w->total);
AMap11_del(AM_dbgNam, w);
#endif
}
AStatic AM am0[1] = { AM0_alc, AM0_fre, AM0_rlc, AM0_arp, AM0_rls, AM0_dst, 0, 0, 0, 0 };
#if (ADbgLv >= 1)
AStatic AM am0d[1] = { AM0_alc, AM0_fre, AM0_rlc, AM0_arp, AM0_rls, AM0_dst, 0, 0, 0, 0 }, *amDbg = am0d;
#endif
AInlineStatic void *AM1_alc(AM *w, AInt sz)
{
AM *v = w->p1;
void *(*alc)(void *, AInt);
alc = v->alc; void *p = alc(v, sz);
#if (ADbgLv >= 1)
if (p != 0) { w->n++; w->total += sz; }
#endif
return p;
}
AInlineStatic void AM1_fre(AM *w, void *p, AInt sz)
{
AM *v = w->p1;
void (*fre)(void *, void *, AInt);
fre = v->fre; fre(v, p, sz);
#if (ADbgLv >= 1)
w->n--; w->total -= sz;
#endif
}
AInlineStatic void *AM1_rlc(AM *w, void *p, AInt sz0, AInt sz1)
{
AM *v = w->p1;
void *(*rlc)(void *, void *, AInt, AInt);
rlc = v->rlc; void *q = rlc(v, p, sz0, sz1);
#if (ADbgLv >= 1)
if (q != 0) {
if (p != 0) { w->n--; w->total -= sz0; }
w->n++; w->total += sz1;
}
#endif
return q;
}
AStatic AM *AM1_opn(int f, AM *m)
{
AM *w = AM_alc(m, f, sizeof (AM));
if (w == 0) return 0;
w->alc = AM1_alc;
w->fre = AM1_fre;
w->rlc = AM1_rlc;
w->arp = AM0_arp;
w->rls = AM0_rls;
w->dst = AM0_dst;
w->n = w->total = 0;
w->p0 = 0;
w->p1 = m;
if ((f & 1) != 0) AM_arp(m, AM0_dst, w, 0, 0);
return w;
}
AClass(AM2) {
void *alc, *fre, *rlc, *arp, *rls, *dst, *p0, *p1; AInt n, total;
AInt sz, nn, *p2;
};
AInlineStatic void AM2_fre(AM2 *w, void *p, AInt sz)
{
*(void **) p = w->p2; w->p2 = p;
#if (ADbgLv >= 1)
w->n--; w->total -= w->sz;
#endif
}
AStatic int AM2_alcSub(AM2 *w)
{
char *p = AM_alc(w->p1, 5, w->sz * w->nn);
if (p == 0) return 1;
AInt i;
#if (ADbgLv >= 1)
w->n += w->nn; w->total += w->nn * w->sz;
#endif
for (i = (w->nn - 1) * w->sz; i >= 0; i -= w->sz)
AM2_fre(w, p + i, 0);
return 0;
}
AInlineStatic void *AM2_alc(AM2 *w, AInt sz)
{
if (w->p2 == 0 && AM2_alcSub(w) != 0) return 0;
void *p = w->p2; w->p2 = *(void **) p;
#if (ADbgLv >= 1)
w->n++; w->total += w->sz;
#endif
return p;
}
AInlineStatic void *AM2_rlc(AM2 *w, void *p, AInt sz0, AInt sz1) { return p; }
AInlineStatic void AM2_dst(AM *w)
{
AM *w1 = w->p1, *m = w1->p1;
AM_rls(w);
#if (ADbgLv >= 1)
if (w->n != 0 || w->total != 0) AM_err(w, "AM2_dst", "error(n=%d, total=%d)", w->n, w->total);
AMap11_del(AM_dbgNam, w);
#endif
AM_dst(w1);
AM_fre(m, w1, sizeof (AM));
}
AStatic AM *AM2_opn(int f, AM *m, AInt sz, AInt nn)
{
AM2 *w2 = AM_alc(m, f, sizeof (AM2));
if (w2 == 0) return 0;
AM *w1 = AM1_opn(f & 4, m);
if (w1 == 0) {
if ((f & 1) == 0) AM_fre(m, w2, sizeof (AM2));
return 0;
}
w2->alc = AM2_alc;
w2->fre = AM2_fre;
w2->rlc = AM2_rlc;
w2->arp = AM0_arp;
w2->rls = AM0_rls;
w2->dst = AM2_dst;
w2->n = w2->total = 0;
w2->p0 = 0;
w2->p1 = w1;
w2->p2 = 0;
w2->sz = sz;
w2->nn = nn;
if ((f & 1) != 0) AM_arp(m, AM2_dst, w2, 0, 0);
return (AM *) w2;
}
AStatic char *AM_spf(AM *m, const char *f, ...)
{
char s[64 * 1024];
va_list ap;
va_start(ap, f);
AInt i = vsprintf(s, f, ap);
if (i < 0) i = 0;
char *t = AM_alc(m, 1, i + 1);
s[i] = 0;
strcpy(t, s);
return t;
}
AStatic char *AM_strcpy(AM *m, const char *s)
{
AInt i = strlen(s);
char *t = AM_alc(m, 1, i + 1);
strcpy(t, s);
return t;
}
- 上記のプログラムは以下の3つのアルゴリズムを提供します。
- AM0 : malloc/freeををそのまま使うだけのアルゴリズム。
- AM1 : alc, fre, rlcについては親に丸投げする。主にAutoReleasePoolを範囲を設定したいときに使う。
- AM2 : AM2オブジェクト生成時に決めたサイズのメモリしか管理できない代わりに、非常に高速なアルゴリズム。親からもらったメモリは、AM2オブジェクトのデストラクタを呼ぶまで返さない。
- 3文字略語の説明：
| alc | allocate |
| fre | free |
| rlc | reallocate |
| arp | append to release pool |
| rls | release |
| dst | destructor |
| opn | open |
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
