* 自分用のミニライブラリ#2
-(by [[K]], 2019.01.19)
** kerr : エラー終了
-void kerr(const char *f, ...)
void kerr(const char *f, ...)
{
va_list ap;
va_start(ap, f);
vfprintf(stderr, f, ap);
fprintf(stderr, "\n");
va_end(ap);
exit(EXIT_FAILURE);
}
** kppol0 : システムへの解放を考えないシンプルなポインタプール
-Kppol0構造体が必要
-void kppol0_0(Kppol0 *w, int s) : 初期化
-void *kppol0_a(Kppol0 *w)
-void kppol0_f(Kppol0 *w, void *p)
#define KPPOL0_USE 1
typedef struct Kppol0_ {
int s, n;
void *p;
#if (KPPOL0_USE != 0)
int a, u;
#endif
} Kppol0;
void kppol0_0(Kppol0 *w, int s)
{
if (s < (int) sizeof (void *))
s = sizeof (void *);
w->n = 64 * 1024 / s;
w->s = s;
if (w->n < 1)
w->n = 1;
w->p = 0;
#if (KPPOL0_USE != 0)
w->a = w->u = 0;
#endif
}
void kppol0_f(Kppol0 *w, void *p)
{
*(void **) p = w->p;
w->p = p;
#if (KPPOL0_USE != 0)
w->u--;
#endif
}
void *kppol0_a(Kppol0 *w)
{
char *p;
if (w->p == 0) {
int i;
p = malloc(w->n * w->s);
if (p == 0)
kerr("Kppol0: out of memory");
p += w->n * w->s;
for (i = 0; i < w->n; i++) {
p -= w->s;
kppol0_f(w, p);
}
#if (KPPOL0_USE != 0)
w->a += w->n;
w->u += w->n;
#endif
}
p = w->p;
w->p = *(void **) p;
#if (KPPOL0_USE != 0)
w->u++;
#endif
return p;
}
** kmlc0 : システムへの解放を考えないシンプルで高速なmalloc
-Kmlc0構造体が必要
-void kmlc0_0(Kmlc0 *w)
-void *kmlc0_a(Kmlc0 *w, int s)
-void kmlc0_f(Kmlc0 *w, void *p, int s)
-int kmlc0_s1(Kmlc0 *w, int s)
-void *kmlc0_r(Kmlc0 *w, void *p, int s0, int s1)
-void kmlc0_rpt(Kmlc0 *w, FILE *fp)
#define KMLC0_CACHE 1
typedef struct Kmlc0_ {
int n, *t;
Kppol0 *p;
#if (KMLC0_CACHE != 0)
int cs, ci;
#endif
} Kmlc0;
static int kmlc0_t0[] = {
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.
};
void kmlc0_0(Kmlc0 *w)
{
int i;
w->n = sizeof (kmlc0_t0) / sizeof (kmlc0_t0[0]);
w->t = kmlc0_t0;
w->p = malloc(w->n * sizeof (Kppol0));
for (i = 0; i < w->n; i++)
kppol0_0(&w->p[i], w->t[i]);
#if (KMLC0_CACHE != 0)
w->cs = w->ci = 0;
#endif
}
int kmlc0_i(Kmlc0 *w, int s)
{
int a, b, c;
#if (KMLC0_CACHE != 0)
if (w->cs == s) return w->ci;
#endif
a = b = 0;
if (s <= w->t[0]) goto fin;
b = w->n - 1;
if (s > w->t[b])
kerr("kmlc0: too large size: s=%d", s);
#if (KMLC0_CACHE != 0)
if (w->ci - 4 > a && s > w->t[w->ci - 4]) a = w->ci - 4;
if (w->ci + 4 < b && s <= w->t[w->ci + 4]) b = w->ci + 4;
#endif
for (;;) {
c = (b - a) >> 1;
if (c == 0) break;
c += a;
if (w->t[c] < s)
a = c;
else
b = c;
}
fin:
#if (KMLC0_CACHE != 0)
w->cs = s;
w->ci = b;
#endif
return b;
}
void *kmlc0_a(Kmlc0 *w, int s)
{
return kppol0_a(&w->p[kmlc0_i(w, s)]);
}
void kmlc0_f(Kmlc0 *w, void *p, int s)
{
kppol0_f(&w->p[kmlc0_i(w, s)], p);
}
int kmlc0_s1(Kmlc0 *w, int s)
{
return w->t[kmlc0_i(w, s)];
}
void *kmlc0_r(Kmlc0 *w, void *p, int s0, int s1)
{
int i0 = kmlc0_i(w, s0), i1 = kmlc0_i(w, s1);
void *q;
if (i0 == i1) return p;
q = kppol0_a(&w->p[s1]);
memcpy(q, p, s0);
kppol0_f(&w->p[s0], p);
return q;
}
void kmlc0_rpt(Kmlc0 *w, FILE *fp)
{
#if (KPPOL0_USE == 0)
fprintf(fp, "kmlc0_rpt: KPPOL0_USE == 0\n");
#else
int i, a = 0, u = 0;
for (i = 0; i < w->n; i++) {
if (w->p[i].a == 0) continue;
fprintf(fp, "kmlc0_rpt: s=0x%08x u/a=%06d/%06d\n", 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(fp, "kmlc0_rpt: u/a=%d/%d\n", a, u);
#endif
}
-kmlc0_a/fは、速い時のmalloc/freeと比較して''5〜13倍''くらい高速。13倍はcsヒット時。
--遅くなっているときのmalloc/freeと比較したら、さらに倍率は上がる。
--これはつまり一度切り分けたメモリブロックを再結合するコストが相当なものであるということを示している。
--再結合がありがたいのは、メモリを限界まで使うようなプログラムかつ、プログラムの途中でメモリの使い方がガラッと変わるような状況で、そのときは再切り分けが可能なのはとても有効。
--このライブラリでは、メモリを限界まで使い切ることはあまりないだろう、メモリの使い方も大変化はしないだろうという想定で、スピードを稼ぐことを重視した。
-kmlc0はメモリの使用効率も高い。mallocが1ブロック当たり8バイトのオーバーヘッドがあるとして、malloc(8)を8192回やったとすれば128KBが必要となるが、kmlc0_a(8)を8192回なら64KB+8バイトで済むため、最大で''約2倍''のメモリ効率となる。これはメモリのサイズをユーザに管理させているため。
-しかもkmlc0_rpt()を使えば、メモリの開放し忘れなども探しやすい。
** kstr0 : 文字列管理ライブラリ
-最初に長さをintで格納するタイプ、大小比較もできる
----
** ktyp : 構造体管理ライブラリ
-構造体idからメンバ名と型名とオフセットのリストが与えられる
** kobj : オブジェクト管理ライブラリ
-メモリ上に構築されたファイルシステム的なもの
-オブジェクトidから名前やそのほかの属性を得られる
-名前からidを引くことは高速でなくていい、そういう想定
![[K Wiki]](k.jpg "[K Wiki]")
