C Academy · レッスン

シンプルなバンプアロケーター

Q: 「シンプルなバンプアロケーター」で何を学びますか？

メモリを順番に割り当てます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

メモリを順番に割り当てます。

「シンプルなバンプアロケーター」はCoddyKit上の無料C Academyレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

バンプアロケータの考え方

バンプ（またはアリーナ）アロケータは、最も単純な設計です。1つの大きなバッファと、1つのオフセットだけを管理します。割り当てのたびに現在のオフセットを返し、その後、要求されたサイズ分だけオフセットを「進めます」。

ブロックごとのメタデータも検索処理もありません。割り当ては基本的にポインタの加算1回で済むため、非常に高速です。

静的なバッキングバッファ

自己完結した例にするため、アロケータの基盤としてOSのヒープではなく静的配列を使います。sbrkやmmapを使わないため、どこでもコンパイルして実行できます。

この配列から、固定サイズのバイトプールを分割して利用します。

#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

中核となるbump関数

割り当てでは、十分な空きが残っているかを確認し、開始位置を記録してオフセットを進め、開始ポインタを返します。要求によってプールがあふれる場合はNULLを返します。

このあふれのチェックが、バンプアロケータが提供する唯一の安全策です。

void *bump_alloc(size_t size) {
    if (offset + size > POOL_SIZE)
        return NULL;            /* out of pool */
    void *p = &pool[offset];
    offset += size;
    return p;
}

完全に実行できるバンプアロケータ

完全なプログラムを見てみましょう。プールから2つの整数と短い文字列を割り当てて出力し、アロケータが動作することを確認します。

本物のmallocと比べて、必要なコードがどれほど少ないかに注目してください。

#include <stdio.h>
#include <stddef.h>
#include <string.h>

#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

void *bump_alloc(size_t size) {
    if (offset + size > POOL_SIZE) return NULL;
    void *p = &pool[offset];
    offset += size;
    return p;
}

int main(void) {
    int *a = bump_alloc(sizeof(int));
    int *b = bump_alloc(sizeof(int));
    char *s = bump_alloc(6);
    *a = 10; *b = 32;
    strcpy(s, "hi");
    printf("%d %d %s\n", *a, *b, s);
    printf("used = %zu\n", offset);
    return 0;
}

個別には解放できない

注意点は、バンプアロケータでは個別の割り当てを解放できないことです。メタデータがないため、再利用のためにあるブロックの終わりと次のブロックの始まりを把握できません。

オフセットを0に戻して、アリーナ全体を一度にリセットすることしかできません。

void bump_reset(void) {
    offset = 0;   /* frees everything at once */
}

リセットが便利な理由

この全か無かのモデルは、フェーズ単位の処理に最適です。リクエストやフレーム中に多くのオブジェクトを割り当て、フェーズが終わったらアリーナをリセットします。

ゲームエンジンやコンパイラがアリーナを多用するのは、リセットがO(1)で実行でき、何千もの個別の解放を追跡せずに済むためです。

/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
    void *tmp = bump_alloc(128);
    /* ... use tmp this frame ... */
    bump_reset();   /* reclaim instantly */
}

残り容量の追跡

残り容量を公開すると便利です。これは単純に、プールサイズから現在のオフセットを引いた値です。

呼び出し側はこの値を使って、追加要求の前にフラッシュするか、容量を拡張するかを判断できます。

size_t bump_remaining(void) {
    return POOL_SIZE - offset;
}

実行可能なリセットのデモ

このプログラムはプールの一部を使用し、使用状況を表示してからリセットします。その後、オフセットがゼロに戻り、領域を再利用できることを示します。

#include <stdio.h>
#include <stddef.h>

#define POOL_SIZE 256
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

void *bump_alloc(size_t s){ if(offset+s>POOL_SIZE) return NULL; void *p=&pool[offset]; offset+=s; return p; }
void bump_reset(void){ offset = 0; }

int main(void) {
    bump_alloc(100);
    printf("after alloc: used=%zu\n", offset);
    bump_reset();
    printf("after reset: used=%zu\n", offset);
    return 0;
}

バンプアロケータにおけるアラインメント

バイト単位でそのままバンプすると、アラインメントされていないポインタが返ることがあります。安全のため、ポインタを返す前にオフセットをアラインメント境界まで切り上げます。

計算方法については後で詳しく扱いますが、パディングが自動的に追加されないため、アラインメントが最も重要になるのがバンプアロケータです。

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);   /* a must be power of 2 */
}

アラインメント対応バンプアロケータ

これまでの要素を組み合わせ、各アロケーションの前にオフセットをアラインメントします。これにより、返されるすべてのポインタが一般的な任意の型に適したものになります。

代わりに、パディングバイトによる小さな内部フラグメンテーションが発生します。

#define ALIGN 16
void *bump_aligned(size_t size) {
    offset = align_up(offset, ALIGN);
    if (offset + size > POOL_SIZE) return NULL;
    void *p = &pool[offset];
    offset += size;
    return p;
}

長所と限界

バンプアロケータは非常に高速で、仕組みも極めて単純です。オブジェクトごとのオーバーヘッドもありません。オブジェクトの寿命が共通している場合に最適です。

弱点は、個々のオブジェクトを細かく解放できないことです。寿命が異なる場合は、次のレッスンで扱うフリーリスト方式が必要になります。

クイックチェック

バンプアロケータがどのようにメモリを回収するか考えてみましょう。

まとめ

バンプアロケータは、バッファ内の1つのオフセットを進めることでメモリを割り当てます。そのため、アロケーションのコストはポインタ加算と同程度です。

速度と単純さのために個別解放を行わず、メモリは完全なリセットによってのみ回収します。返されるポインタをすべての型で有効にするため、オフセットをアラインメントしてください。

よくある質問

「シンプルなバンプアロケーター」レッスンは無料ですか？

はい。「シンプルなバンプアロケーター」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「シンプルなバンプアロケーター」で何を学びますか？

メモリを順番に割り当てます。ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン2/4です。

「シンプルなバンプアロケーター」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← C Academyに戻る