* kclib1のページ#5
-(by [[K]], 2019.04.16)
** (9) KMalloc
-KPtrPoolを100個以上使って実現した、シンプルだけど高速なmalloc/freeもどきです。
-KPtrPoolを使っているので、freeしたメモリは前後の未使用メモリと結合されることはありません。むしろそれをやらないからこそ高速なのです。→''ベンチーマーク(a)～(c)''
-サイズは、 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, ...のように飛び飛びになっています。
--シンプルな方法としては、4, 8, 16, 32, 64, 128, ... みたいに倍々にすることだったのですが、これだと1025バイトを要求した時に2048バイトの領域を渡すことになり、約50%のメモリが利用されないことになります。それはメモリ効率が良くないと思いました。
--だからKMallocでは2倍の間を4つに刻んでいます。これで最も効率が悪い時でも、ロス率は20%で済みます。またメモリサイズの近いものはある程度同一視しないと、メモリの再利用が進みません。メモリブロックの再結合をしないKMallocでは、再利用が進まないとメモリ不足に追い込まれるので、やはり8分割や16分割はやり過ぎになってしまうと思われます。
--ロス率20%はワーストケースで、平均はおそらく10%になるでしょう。だからほとんど問題にならないと私は考えています。
-freeするときにもサイズを指定しなければけないという手間はありますが、その代わりメモリ使用効率は高いです。小さいメモリをたくさん確保してもメタデータのためにメモリ消費がうんと増えてしまうということはありません。→''ベンチーマーク(d)～(e)''
--free時にサイズ指定する手間よりも、それで得られる性能向上の方が得だと考えてこの仕様にしています。
-「この場面でmalloc/freeを使うのはためらいがあるなー」と思うことがよくある私ですが（性能低下などが怖い）、KMallocならいつでも気軽に使える感じです。
-[Q]速くなることは、セキュリティ面からどんな意味があるのか？
--[A]速くなれば浮いた時間でセキュリティチェックを充実させる余地が生まれます。実にいいことです。
-[Q]メモリをfreeしたときに再結合しないことで何か問題はないのか？
--[A]小さなメモリブロックをたくさん使って解放した後に、大きなメモリブロックを使おうとしてもメモリ不足で失敗する可能性があります。・・・しかし近年のコンピュータのメモリ積載量は私にとっては十分すぎるもので、私のプログラミングスタイルなら、KMallocでもメモリ不足に悩まされることはまず起こらない気がします。メモリがたくさんあっても使いこなせていない私ですが、それを活用して高速化してくれるのがKMallocであるとも言えます。
--別の論点としては、KMallocはそもそも完璧を目指していません。だから問題点がいくつあっても関係ないのです。簡単な仕組みでmalloc/freeもどきを作れたので、この程度で十分な範囲でのみ使っていけばいいと思っています。再結合が必要な場面ではKMallocなんか使わずに素直にmalloc/freeすればいいのです。用途に応じて使い分けることもプログラマの腕前だと思っています。
----
-void KMalloc_init()
--内部ワークエリアを初期化します。最初に一度だけ呼ぶ必要があります。
-int KMalloc_index(int s)
--サイズから、何番目のKPtrPoolを使えばいいのかを計算します。
-void *KMalloc_alloc(int s)
--mallocです。
-void KMalloc_free(int s, void *p)
--freeです。
-void *KMalloc_realloc(int s0, int s1, void *p)
--reallocです。
-void KMalloc_report(void *fp)
--メモリの使用状況を報告します。デバッグ用です。
----
-[効果]論より証拠で簡単なベンチマークを取ったので書いておきます。
--(a) まず標準関数のmalloc/freeを使った、以下のプログラムの実行時間を測定しました。「1万回のmalloc&free」を1万回繰り返したときの時間を測っています。最初に10回ほど余計に回していますが、その間は時間を測りません。こうすることで初期のあまり速くない処理時間を混ぜずにトップスピードを測っています。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int i, j, **a = malloc(10000 * sizeof (int *));
clock_t t0 = 0, t1;
for (j = -10; j < 10000; j++) {
if (j == 0) t0 = clock();
for (i = 0; i < 10000; i++)
a[i] = malloc(256 * sizeof (int));
for (i = 0; i < 10000; i++)
free(a[i]);
}
t1 = clock();
printf("time: %.3f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}
---シンプルすぎてツッコミどころがない感じですが、 Core i7-2600 3.40GHz で測定したところ''35.188秒''でした。まあそんなものだろうなという感じです。
--(b) 次にKMallocを使ってみます。大きな違いは、freeするときにもサイズを指定しなければいけないところでしょうか。KMallocではメモリ管理のメタデータをあえて持たないので、freeするときにもサイズを教えてやらなければいけないのです。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "kclib1.h"
int main()
{
int i, j, **a = malloc(10000 * sizeof (int *));
clock_t t0 = 0, t1;
KMalloc_init();
for (j = -10; j < 10000; j++) {
if (j == 0) t0 = clock();
for (i = 0; i < 10000; i++)
a[i] = KMalloc_alloc(256 * sizeof (int));
for (i = 0; i < 10000; i++)
KMalloc_free(256 * sizeof (int), a[i]);
}
t1 = clock();
printf("time: %.3f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}
---これでどのくらい速くなるのかなと思ったのですが、 Core i7-2600 3.40GHz で測定したところ''2.812秒''でした。これは我ながらすごいです。初めは何かの間違いじゃないかと思ったほどです。''12.5倍''くらい高速になっています。
--(c) さらに一歩進んで、KPtrPoolを直接使ってみます。KMallocでは同じサイズを何度もalloc/freeするのであれば、KPtrPoolを直接使って高速化してくれということになっています。だからそうしてみたわけです。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "kclib1.h"
int main()
{
int i, j, **a = malloc(10000 * sizeof (int *));
clock_t t0 = 0, t1;
KMalloc_init();
KPtrPool *pool = KMalloc_work->p + KMalloc_index(256 * sizeof (int));
for (j = -10; j < 10000; j++) {
if (j == 0) t0 = clock();
for (i = 0; i < 10000; i++)
a[i] = KPtrPool_alloc(pool);
for (i = 0; i < 10000; i++)
KPtrPool_free(pool, a[i]);
}
t1 = clock();
printf("time: %.3f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}
---これを実行すると、 Core i7-2600 3.40GHz で測定したところ''1.903秒''でした。
---ちなみにまだ速くする余地はあって、それは「今どのサイズのメモリブロックがいくつ使われているか」の集計機能をOFFにすることです（デフォルトではデバッグ支援のためにONにしてあります）。本家のmalloc/freeにはそんな機能は無いことですし、だからそれを同等にそろえて比較するのなら、このモードで比較する意味はあるでしょう。・・・そうすると、''1.882秒''になります。これは実に''18.7倍''くらい速いことになります。
--(d) 今度はメモリ効率の確認です。まずは以下のプログラムを実行してみました。
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, *p;
char tmp[10000];
printf("[phase1] continue? (y/ctrl-c):");
scanf("%s", tmp);
for (i = 0; i < 1000000; i++) {
p = malloc(sizeof (int));
*p = i;
}
printf("[phase2] continue? (y/ctrl-c):");
scanf("%s", tmp);
return 0;
}
---これを実行すると、最初の消費メモリは356KBで、次の時点では16,312KBになっていました。つまり15,956KBほど消費メモリが増えたということです。どうやら1回のmallocで''16バイト''ずつ消費しているようです。そもそもmallocは16バイトアラインするというルールもありましたよね、確か。
--(e) これに対して以下のプログラムだとどうでしょうか？
#include <stdio.h>
#include "kclib1.h"
int main()
{
int i, *p;
char tmp[10000];
KMalloc_init();
printf("[phase1] continue? (y/ctrl-c):");
scanf("%s", tmp);
for (i = 0; i < 1000000; i++) {
p = KMalloc_alloc(sizeof (int));
*p = i;
}
printf("[phase2] continue? (y/ctrl-c):");
scanf("%s", tmp);
return 0;
}
---これを実行すると、最初の消費メモリは420KBで、ライブラリのワークエリアの分だけ消費メモリが増えていますが、次の時点では4,656KBで済みます。だから1回のmallocで''4バイト''ずつ消費しているのです。まあsizeof (int)が4バイトなので、当然と言えば当然の結果です。KMallocは4バイトのメモリに対しては4バイトのアラインは保証しますが、16バイトアラインは保証しないのです。
----
-[内部実装]
typedef struct KMalloc0_ {
int n, *t;
int n;
KPtrPool *p;
} KMalloc0;
----
-[内部実装]
#include "kclib1.h"
#include <string.h>
#include <stdio.h>
int KMalloc_t[27 * 4] = {
0x4, 0x8, 0xc, 0x10,
0x14, 0x18, 0x1c, 0x20,
0x28, 0x30, 0x38, 0x40,
0x50, 0x60, 0x70, 0x80,
0xa0, 0xc0, 0xe0, 0x100,
0x140, 0x180, 0x1c0, 0x200,
0x280, 0x300, 0x380, 0x400,
0x500, 0x600, 0x700, 0x800,
0xa00, 0xc00, 0xe00, 0x1000,
0x1400, 0x1800, 0x1c00, 0x2000,
0x2800, 0x3000, 0x3800, 0x4000,
0x5000, 0x6000, 0x7000, 0x8000,
0xa000, 0xc000, 0xe000, 0x10000,
0x14000, 0x18000, 0x1c000, 0x20000,
0x28000, 0x30000, 0x38000, 0x40000,
0x50000, 0x60000, 0x70000, 0x80000,
0xa0000, 0xc0000, 0xe0000, 0x100000, // 1MB.
0x140000, 0x180000, 0x1c0000, 0x200000,
0x280000, 0x300000, 0x380000, 0x400000,
0x500000, 0x600000, 0x700000, 0x800000,
0xa00000, 0xc00000, 0xe00000, 0x1000000, // 16MB.
0x1400000, 0x1800000, 0x1c00000, 0x2000000,
0x2800000, 0x3000000, 0x3800000, 0x4000000,
0x5000000, 0x6000000, 0x7000000, 0x8000000,
0xa000000, 0xc000000, 0xe000000, 0x10000000, // 256MB.
0x14000000, 0x18000000, 0x1c000000, 0x20000000,
0x28000000, 0x30000000, 0x38000000, 0x40000000 // 1GB.
};
void KMalloc0_init(KMalloc0 *w, void *f, void *opt)
{
int i;
void *(*func)(void *, int);
w->n = sizeof (KMalloc_t) / sizeof (KMalloc_t[0]);
func = f;
w->p = func(opt, w->n * sizeof (KPtrPool));
for (i = 0; i < w->n; i++)
KPtrPool_init(w->p + i, KMalloc_t[i], f, opt);
}
int KMalloc0_index(KMalloc0 *w, int s)
{
(void) w;
return KMalloc_index(s);
}
int KMalloc_index(int s)
{
int a, i;
if (s < 0x10) {
if (s > 0)
return (s - 1) >> 2;
return 0;
}
if (s > 0x40000000)
kerrorExit("KMalloc: too large size: s=%d", s);
#if 0 // 普通の書きかた.
a = kgetmsb32(s) - 1;
i = kpopcnt32(a) * 4 - 13;
s += a >> 2;
a++;
if ((s & (a >> 1)) != 0) i += 2;
if ((s & (a >> 2)) != 0) i++;
#else // インライン展開して高速に.
// a = kgetmsb32(s) - 1;
a = s >> 1;
a |= a >> 1;
a |= a >> 2;
a |= a >> 4;
a |= a >> 8;
a |= a >> 16;
// i = kpopcnt32(a);
i = a - (a >> 1 & 0x55555555U);
i = (i & 0x33333333U) + (i >> 2 & 0x33333333U);
i = (i + (i >> 4)) & 0x0f0f0f0fU;
i = (i * 0x01010101U) >> 24;
s += a >> 2;
s >>= i - 2;
i = i * 4 + s - 17;
#endif
return i;
}
void *KMalloc0_alloc(KMalloc0 *w, int s)
{
return KPtrPool_alloc(w->p + KMalloc_index(s));
}
void KMalloc0_free(KMalloc0 *w, int s, void *p)
{
if (s == -2) { // destructor.
do {
int (*f)(void *);
f = *((void **) p);
s = f(p);
} while (s == -2);
}
if (s >= 0)
KPtrPool_free(w->p + KMalloc_index(s), p);
}
void *KMalloc0_realloc(KMalloc0 *w, int s0, int s1, void *p)
{
void *q;
int i0 = KMalloc_index(s0), i1 = KMalloc_index(s1), s;
if (i0 == i1) return p;
s = s0;
if (s0 > s1)
s = s1;
q = KPtrPool_alloc(w->p + i1);
if (s > 0)
memcpy(q, p, s);
KPtrPool_free(w->p + i0, p);
return q;
}
void KMalloc0_report(KMalloc0 *w, void *fp)
{
#if (KPTRPOOL_REPORT == 0)
fprintf((FILE *) fp, "KMalloc_report: KPTRPOOL_REPORT == 0\n");
#else
int i, a = 0, u = 0;
for (i = 0; i < w->n; i++) {
if (w->p[i].a == 0) continue;
fprintf((FILE *) fp, "KMalloc_report: i=%02d s=0x%08x u/a=%06d/%06d\n", i, w->p[i].s, w->p[i].u, w->p[i].a);
a += w->p[i].a * w->p[i].s;
u += w->p[i].u * w->p[i].s;
}
fprintf((FILE *) fp, "KMalloc_report: u/a=%d/%d\n", u, a);
#endif
}
KMalloc0 KMalloc_work[1];
void KMalloc_init()
{
KMalloc0_init(KMalloc_work, KPtrPool_f_malloc, 0);
}
void *KMalloc_alloc(int s)
{
return KPtrPool_alloc(KMalloc_work->p + KMalloc_index(s));
}
void KMalloc_free(int s, void *p)
{
if (s >= 0)
KPtrPool_free(KMalloc_work->p + KMalloc_index(s), p);
else
KMalloc0_free(KMalloc_work, s, p);
}
void *KMalloc_realloc(int s0, int s1, void *p)
{
return KMalloc0_realloc(KMalloc_work, s0, s1, p);
}
void KMalloc_report(void *fp)
{
KMalloc0_report(KMalloc_work, fp);
}
--168行あります。kclib1の中では結構長い方です。
* こめんと欄
#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
