Cメモリ管理パフォーマンス

C 言語の Arena アロケータ

C 言語の小さな arena アロケータを解説する。解決するライフサイクル問題から、動く実装の構造体、アラインメント、realloc の経路まで。

eliasebner.comElias Ebner約 11 分

日本語
中文日本語
コピー

C は非常に低レベルな言語だ。使うメモリを自分で管理できる（というより、半ば強制される）。多くの人が日常のプログラミングで他の言語に移る理由のひとつも、おそらくここにある。本記事では、性能が非常に高く、しかも極めて柔軟なメモリ管理のパラダイムを紹介する。メモリ管理はずっと楽になり、メモリリークの確率も大きく下がる。

聞いたことがある人もいるだろうし、ない人もいるだろう。いずれにせよ、それが arena アロケータだ。

この後で実装の話をするが、その前に arena アロケータとは何かを簡単に説明しておく。

Arena アロケータとは何か？

メモリを管理するとき、たいていの人はこうする。メモリが必要になるたびに malloc でヒープから少しだけ確保する。必要な分だけだ。後になって最初に想定したより多くのメモリが必要だと分かれば、realloc で確保済みのメモリを拡張する。

使い終わったら free を呼び、このメモリはもう不要で、別の用途に回してよいと OS に伝える。

これで悪くはないが、いくつか問題がある。

1.

プログラマは、メモリを使い終わったら解放することを覚えていなければならない。確保がループの中で起きる場合——たとえばゲームなどでは——特に危険だ。この場合、OS はどんどんメモリを確保し続け、そのメモリは決して解放されない。

メモリという資源は無限ではない。どこかの時点でコンピュータはメモリを使い果たし、プログラムは OS によって終了させられる（つまりクラッシュする）。

2.

小さなメモリブロックを大量に確保して解放するのは遅い。

3.

次のような関数があるとする。

i32 *create_array(usize len) {
    i32 *elements = (i32 *)malloc(sizeof(int));
    return elements;
}

では教えてほしい。この関数を呼び出すプログラマは、その内部でメモリ確保が行われていることをどうやって知るのだろうか？　この例では、関数名から何をしているか推測できるかもしれない。だが、いつもそう単純とは限らない。

これは重要な点だ。プログラマは、いつメモリを解放すべきかを知る必要があるからだ。

メモリの解放は自分自身の責任である、とプログラマに意識させなければならない。

私が考慮していない問題はまだあるかもしれないが、ぱっと思いつく主なものは以上だ。

解決策。

登場してもらおう、arena allocator だ。

ほとんどのライフタイム（つまり、あるメモリが解放されるまでどれだけ使われるか）は、いくつかの種類に分類できる。

  1. メモリのライフタイムがプログラム全体と同じ
  2. メモリのライフタイムが、何らかのタスクの完了まで続く（たとえばゲームの 1 フレーム、あるいは 1 回の HTTP リクエストの処理）
  3. メモリのライフタイムが、ある関数のスコープに限られる

こうしたグルーピングでたいていは足りるが、どう区切るかによっては、さらに種類が増えることもある。いずれにせよ、ライフタイムが近いもの（まとめて解放できるもの）を扱うための大きなメモリブロックを、まとめて確保してしまえばよい。

これで、使える大きなメモリの塊が手に入った。その一部を何かのために使うたびに、ポインタを進め、どこまでメモリを使ったか、空きメモリがどこから始まるかを覚えておく。

実装を見れば、この点はもっとはっきりする。

その大きなメモリの中のデータがもう一切不要になったら、まとめて一度に解放してよい（あるいは、このメモリを再利用したいなら、memory arena を初期状態に戻して、先頭から確保し直せばよい）。

これにより、個別のメモリ確保を何度も行う必要がなくなり（思い出してほしい、これらの操作は遅い）、メモリ管理に気を遣う必要もずっと減る。個々の配列が使う小さなメモリの山ではなく、いくつかのメモリの「塊」だけを見ればよくなるからだ。

実装

説明

始める前に。私が C を使うときは、ほぼ必ずコードの先頭でこのファイルをインクルードする。

これはいくつかの組み込み型に typedef を与え、よく使う便利なツールをいくつか提供するだけのものだ。コンパイルを速くするために unity build を使っているので、私は .c ファイルをそのままインクルードしている。

自分でヘッダを書きたいなら、そうしてもまったく構わない。

// types.c
#ifndef TYPES_C
#define TYPES_C

#include <stddef.h>
#include <stdint.h>

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;

typedef float f32;
typedef double f64;

typedef size_t usize;

#define KiB(x) x * 1024
#define MiB(x) KiB(x) * 1024
#define GiB(x) MiB(x) * 1024

#define MIN(a, b) a < b ? a : b
#define MAX(a, b) a > b ? a : b

#endif // TYPES_C

arena.c

以下が arena の実際の実装だ。

冒頭は include guard（これも unity build のため）で、そのあとに使う libc ヘッダをいくつか読み込む。

#ifndef ARENA_C
#define ARENA_C

#include "types.c"
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// code goes here

#endif // ARENA_C

これが arena 構造体の定義だ。

struct arena {
    void *data;
    usize size;
    usize used;
};

どれだけメモリを使ったかを記録している。同じ目的は別の方法でも達成できる。まだ使っていない領域の先頭を指すポインタを 1 つ持つやり方だ。

size フィールドの役割は、確保時に arena の容量を超えるかどうかを判定することだ（メモリを使いすぎるのはよくある）。

data は arena の先頭位置を直接指す。

ここまでは順調だが、次に新しい arena を作る方法が必要だ。次のとおり。

struct arena_create_out {
    struct arena arena;
    bool success;
};
[[nodiscard]]
struct arena_create_out arena_create(usize size) {
    struct arena_create_out out = {0};
    out.arena.data = malloc(size);
    if (out.arena.data == NULL)
        return out;
    out.arena.size = size;
    out.arena.used = 0;
    out.success = true;
    return out;
}

複数の値を返すとき、私は出力パラメータを使うのが好きではない。回りくどいし、API も直感的でないと感じる。構造体をそのまま返すほうがよい。

次に、arena の中でメモリを確保する方法が必要だ。その前に、このマクロを定義しておく（ファイルの先頭に置いてあるが、実際に必要になるのはここなので、ここで紹介する）。

#define ARENA_ALIGN 8

これはデータをアラインメントするためのものだ。どういうわけか、コンピュータは 8 バイトにアラインメントされたデータのほうをはるかに効率よく扱える。つまり、新しく確保するたびに、その開始位置は 8 の倍数でなければならない。

malloc がこれを処理してくれるが、今は malloc で確保しているのではなく、すでに確保済みのメモリの中から一部を切り出しているだけなので、アクセスを速くするために自分でデータをアラインメントしなければならない。

以下が確保関数だ。

struct arena_alloc_out {
    void *ptr;
    bool success;
};
[[nodiscard]]
struct arena_alloc_out arena_alloc(struct arena *arena, usize size) {
    struct arena_alloc_out out = {0};
    usize alignment = (ARENA_ALIGN - (arena->used % ARENA_ALIGN)) % ARENA_ALIGN;
    out.ptr = arena->data + arena->used + alignment;
    if (out.ptr + size > arena->data + arena->size)
        return out;
    arena->used += size + alignment;
    out.success = true;
    return out;
}

ここでは、次の確保を 8 バイトにアラインメントするために、確保の末尾にどれだけ「パディング」（alignment 変数）を足す必要があるかを計算する。

私は関数の戻り値の型に success フィールドを置くのが習慣で、エラー時はそのまま早期リターンする（= {0} で全ゼロに初期化されるので、success は false になる）。

このやり方が気に入らないなら、API を別の約束事に変えるのは難しくないはずだ。

作業の大半は終わっている。新しいサイズに合わせて割り当てを変える簡単なラッパー関数を書いた。arena の末尾に新しいサイズぶんのメモリを確保し、そこにデータをコピーする。古いデータはそのまま残り、arena を解放するときにまとめて解放される（思い出してほしい。個々の割り当ては解放できず、arena 全体を解放するか、何もしないかのどちらかだ）。

これが実はなくても困らないのだが、コードがきれいになるので載せておく：

struct arena_realloc_out {
    void *ptr;
    bool success;
};
[[nodiscard]]
struct arena_realloc_out arena_realloc(struct arena *arena, usize new_size, void *src, usize old_size) {
    struct arena_realloc_out out = {0};
    struct arena_alloc_out alloc_out = arena_alloc(arena, new_size);
    if (!alloc_out.success)
        return out;

    out.ptr = memcpy(alloc_out.ptr, src, MIN(old_size, new_size));
    out.success = true;
    return out;
}

新しいサイズが古いサイズより小さい場合、末尾の部分は切り捨てられる。また、realloc は各ポインタがどの割り当てサイズに対応するかを内部で把握しているので、古いサイズを渡す必要はなく、新しいサイズだけを渡せばよい。

われわれの arena 実装は割り当てサイズを一切記録しないので、この関数には古いサイズを別途渡すしかない。arena の利用者は、各割り当てのサイズを自分で把握しておくべきだ。

これも実装はできるが、単純さを保ちたかった。

続く2つの関数は小さなラッパーで、便利だから置いてあるだけで必須ではない：

void arena_clear(struct arena *arena) { arena->used = 0; }

void arena_free(struct arena *arena) { free(arena->data); }

私の実装はここまでだ。

使用例

自分の用途向けに書いた簡単な文字列ライブラリがある。そこには2つの概念がある。string view と owned string だ。

owned string は NUL で終端し、owns そのデータ（つまり、確保と解放が必要ということ）。これは owned string を直接書き換えられることも意味する。

string view はデータを見るだけなので、直接書き換えることはできない。同じデータに対して複数の string view が存在しうるので、書き換えれば他の文字列が予期せず変わってしまう。逆に、あるデータ領域に対して owned string は1つだけであるべきだ。

肝心なのは、string view を owned string に変換する方法が必要だということだ。そのためには新しい owned string を作り（つまりメモリを確保し）、データをコピーする必要がある。これも、この owned string への変更が、それを参照しているかもしれない他の string view に影響しないようにするためだ。

さらに、owned string の末尾には NUL 終端文字を付ける（他のレガシーな C API と互換にするため）。

そのために、関数に arena アロケータを渡し、その arena からメモリを確保する：

struct str_view {
    const u8 *data;
    usize len;
};

struct str_owned {
    u8 *data;
    usize len;
};

struct str_view_to_str_owned_out {
    struct str_owned str;
    bool success;
};
[[nodiscard]]
struct str_view_to_str_owned_out str_view_to_str_owned(
    struct arena *arena,
    struct str_view s
) {
    struct str_view_to_str_owned_out out = {0};
    struct arena_alloc_out alloc_out = arena_alloc(arena, s.len + 1);
    if (!alloc_out.success)
        return out;
    out.str.data = alloc_out.ptr;
    memcpy(out.str.data, s.data, s.len);
    out.str.len = s.len;
    out.str.data[out.str.len] = 0;
    out.success = true;
    return out;
}

これには2つの利点がある：

  1. 呼び出し側は、この関数がメモリを確保することがすぐにわかる（最初の引数が arena ポインタだから）
  2. 呼び出し側が、どこでメモリを確保するか（つまりどのライフタイムで確保するか）を決められる。

2点目について、呼び出し側は対応する arena を渡すことでライフタイムを決めるので、メモリの解放を直接気にする必要はない。ライフタイムが終わり、arena が破棄される（またはクリアされる）ときに、メモリは自然と解放される。そのタイミングは、プログラムの終了時（この場合、メモリの解放はそもそも不要で、OS が処理してくれる）でもよいし、関数の終了時でもよいし、呼び出し側がこのメモリはもう不要だと確信したときでもよい。

結び

最近 arena を自分のプログラミング習慣に取り入れ始めたが、正直なところ、その効果にはとても満足している。自分の文字列ライブラリも arena に移行したし、君も arena からかなり恩恵を受けられると思う。

開発体験の向上は大きいときも小さいときもあるが、プログラマとしてこの道具を手に入れるのは間違いなく純粋な得だと断言できる。

自分を専門家だとは思っていないし、この実装も個人的な用途のために自分で書いたものにすぎない。完璧とは言えないが、入門的な紹介としては十分だろう。

いつもどおり、質問やフィードバック、アイデアがあればメールで連絡してほしい：

info@eliasebner.com

出典: eliasebner.com← ホームへ戻る