p20190119a のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
p20190119a へ行く。
- 1 (2019-01-19 (土) 23:46:29)
- 2 (2019-01-20 (日) 00:22:53)
- 3 (2019-01-29 (火) 19:38:18)
- 4 (2019-01-29 (火) 22:20:19)
- 5 (2019-01-30 (水) 08:59:38)

自分用のミニライブラリ#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_rpt()を使えば、メモリの開放し忘れなども探しやすい。

↑

kstr0 : 文字列管理ライブラリ

最初に長さをintで格納するタイプ、大小比較もできる

↑

ktyp : 構造体管理ライブラリ

構造体idからメンバ名と型名とオフセットのリストが与えられる

↑

kobj : オブジェクト管理ライブラリ

メモリ上に構築されたファイルシステム的なもの
オブジェクトidから名前やそのほかの属性を得られる
名前からidを引くことは高速でなくていい、そういう想定