kclib1_0005
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* kclib1のページ#5
-(by [[K]], 2019.04.16)
** (9) KMalloc
-KPtrPoolを100個以上使って実現した、シンプルだけど高速なm...
-KPtrPoolを使っているので、freeしたメモリは前後の未使用メ...
-サイズは、 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64,...
--シンプルな方法としては、4, 8, 16, 32, 64, 128, ... みた...
--だからKMallocでは2倍の間を4つに刻んでいます。これで最も...
--ロス率20%はワーストケースで、平均はおそらく10%になるで...
-freeするときにもサイズを指定しなければけないという手間は...
--free時にサイズ指定する手間よりも、それで得られる性能向...
-「この場面でmalloc/freeを使うのはためらいがあるなー」と...
-[Q]速くなることは、セキュリティ面からどんな意味があるの...
--[A]速くなれば浮いた時間でセキュリティチェックを充実させ...
-[Q]メモリをfreeしたときに再結合しないことで何か問題はな...
--[A]小さなメモリブロックをたくさん使って解放した後に、大...
--別の論点としては、KMallocはそもそも完璧を目指していませ...
----
-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を使った、以下のプログラム...
#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) / CLO...
return 0;
}
---シンプルすぎてツッコミどころがない感じですが、 Core i7...
--(b) 次に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) / CLO...
return 0;
}
---これでどのくらい速くなるのかなと思ったのですが、 Core ...
--(c) さらに一歩進んで、KPtrPoolを直接使ってみます。KMall...
#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...
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) / CLO...
return 0;
}
---これを実行すると、 Core i7-2600 3.40GHz で測定したとこ...
---ちなみにまだ速くする余地はあって、それは「今どのサイズ...
--(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で、次の時点...
--(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で、ライブラ...
----
-[内部実装]
typedef struct KMalloc0_ {
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...
{
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_R...
#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...
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\...
#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_inde...
}
void KMalloc_free(int s, void *p)
{
if (s >= 0)
KPtrPool_free(KMalloc_work->p + KMalloc_index(s)...
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
終了行:
* kclib1のページ#5
-(by [[K]], 2019.04.16)
** (9) KMalloc
-KPtrPoolを100個以上使って実現した、シンプルだけど高速なm...
-KPtrPoolを使っているので、freeしたメモリは前後の未使用メ...
-サイズは、 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64,...
--シンプルな方法としては、4, 8, 16, 32, 64, 128, ... みた...
--だからKMallocでは2倍の間を4つに刻んでいます。これで最も...
--ロス率20%はワーストケースで、平均はおそらく10%になるで...
-freeするときにもサイズを指定しなければけないという手間は...
--free時にサイズ指定する手間よりも、それで得られる性能向...
-「この場面でmalloc/freeを使うのはためらいがあるなー」と...
-[Q]速くなることは、セキュリティ面からどんな意味があるの...
--[A]速くなれば浮いた時間でセキュリティチェックを充実させ...
-[Q]メモリをfreeしたときに再結合しないことで何か問題はな...
--[A]小さなメモリブロックをたくさん使って解放した後に、大...
--別の論点としては、KMallocはそもそも完璧を目指していませ...
----
-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を使った、以下のプログラム...
#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) / CLO...
return 0;
}
---シンプルすぎてツッコミどころがない感じですが、 Core i7...
--(b) 次に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) / CLO...
return 0;
}
---これでどのくらい速くなるのかなと思ったのですが、 Core ...
--(c) さらに一歩進んで、KPtrPoolを直接使ってみます。KMall...
#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...
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) / CLO...
return 0;
}
---これを実行すると、 Core i7-2600 3.40GHz で測定したとこ...
---ちなみにまだ速くする余地はあって、それは「今どのサイズ...
--(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で、次の時点...
--(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で、ライブラ...
----
-[内部実装]
typedef struct KMalloc0_ {
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...
{
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_R...
#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...
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\...
#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_inde...
}
void KMalloc_free(int s, void *p)
{
if (s >= 0)
KPtrPool_free(KMalloc_work->p + KMalloc_index(s)...
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]")
