【自作ゲームエンジン】#1：LinearAllocator（線形アロケータ）による超高速なメモリ管理手法

目次

1. 概要
2. C++のnewキーワードについて
3. LinearAllocatorとは
4. まとめ
5. メモリ管理の世界はさらに深く

1. 概要

• 本記事では、ゲームエンジン開発において、メモリ割り当てを効率的に管理するための戦略と実装方法について解説します。
• 関連資料：
  • Linear/Arena Allocator - gingerbill.org
  • tobias-stein/BountyHunterDemo
  • ゲームエンジンアーキテクチャ 第3版 - 6.2メモリ管理

2．C++のnewキーワードについて

カスタムメモリシステムを実装する前に、まずはC++の new キーワードによるメモリ割り当ての基本的な仕組みについて復習しておきましょう。

2.1．通常の動的割り当て（不連続なアドレスへの割り当て）

C++でメモリを扱う際、大きく分けてスタック領域とヒープ領域の2種類が存在します。
スタック領域に割り当てられた変数は、宣言されたスコープを抜けると自動的に解放されます。一方、newキーワードを使用してヒープ領域に割り当てられた変数は、自動的には解放されません。

// サンプル構造体
struct GameObject {
    size_t UUID;
    float Position[3];
};

// スタック領域で割り当てられる変数
{
   GameObject monster; // ここでmonster変数を宣言します。
}
// -> スコップを抜けると、monster変数が自動的に開放されます。

// ヒープ領域で割り当てられる変数
{
   GameObject* monster = new GameObject(); // ここでmonster変数を宣言します。
}
// ->　スコップを抜けると、monster変数が自動的に開放されません。（メモリリークの原因になります）

2.2．指定したアドレスへの割り当て（Placement new）

通常のnewを使用すると、OSがRAM上から要求されたサイズに適合する空き領域を検索し、見つかった場所にオブジェクトを作成します。しかし、高パフォーマンスが要求されるゲームエンジンでは、毎回OSに変数のための領域を探させるのは非常に高コストです。
これに対する解決策が、「特定のアドレスを明示的に指定し、その場で即座にオブジェクトを構築する」 方法です。これはC++でPlacement new（配置new）と呼ばれています。
あらかじめ確保したメモリを使い回すため、OSによるメモリ検索の手間（オーバーヘッド）を排除できます。
では、その「特定のアドレス」をどのように管理すればよいでしょうか。以下のサンプルコードをご覧ください。

// サンプル構造体
struct GameObject {
    size_t UUID;
    float Position[3];
};

// 1. 2つのGameObject変数を保存できるメモリ領域を、アライメントを考慮して事前確保
void* specifiedAddress = _aligned_malloc(sizeof(GameObject) * 2, alignof(GameObject));

// 2. オブジェクト1を作成
GameObject* monster = new (specifiedAddress)GameObject();

// 3. 次の利用可能なアドレスをGameObject構造体のサイズでオフセット
uintptr_t playerAddress = reinterpret_cast<uintptr_t>(specifiedAddress) + sizeof(GameObject);
void* voidPtrPlayerAddress = reinterpret_cast<void*>(playerAddress);

// 4. オブジェクト2を作成
GameObject* player = new (voidPtrPlayerAddress)GameObject();

• この手法では、オブジェクトを作成するたびに個別にメモリを要求するのではなく、最初にあらかじめ大きなメモリ領域を確保しておきます。その後は、その領域から必要な分だけを切り出してアプリケーションが自由に使用します。
• つまり、OSへのメモリ要求を1回だけに抑え、エンジン側で高速にメモリを小分けにしていく戦略です。これこそが、今回実装する「Linear Allocator」の基本原理となります。

3．LinearAllocatorとは

Linear（リニア）とは「線形（一方向）」という意味です。その名の通り、メモリを一直線に隙間なく割り当てていく性質を持っています。
それでは、ここから「Linear Allocator」の具体的な設計と実装について詳しく見ていきましょう！

3.1 設計

まずは、「Linear Allocator」の構造を視覚的にイメージするために、以下の図をご覧ください。

• 構成には三つの大事な部分があります。
  1．メモリブロック: あらかじめ確保しておくメモリの合計サイズのことです（例：24バイト、10MBなど）。
  2．先頭アドレス: 確保したメモリブロックを管理するための、一番最初の位置を示すポインタです。
  3．現在のオフセット（割り当てポインタ）: 次にメモリを切り出せる位置を指すポインタです。これまでにどれだけのメモリを使ってきたかをベースに計算されます。

メリット

この設計の最大の強みは、「現在のオフセット」を見るだけで、次に要求されたメモリを即座に切り出せる点にあります。通常の malloc のように空き領域を探す複雑なサーチが必要ないため、時間計算量は常に $O(1)$（定数時間） という圧倒的な高速化を実現できます。

デメリット

ただし、強力な反面、ひとつだけ大きなトレードオフがあります。
メモリを一方向にバケツリレーのように割り当てていく性質上、「特定のオブジェクトだけを狙って途中で自由に削除する」 ということができません。
メモリを解放したい場合は、オフセットを「先頭アドレス」まで一気に巻き戻す（＝すべてのメモリを丸ごとクリアする）必要があります。
例） フレームごとのメモリ使用するサンプルコード※

void Application::Run() {
    // エンジンのメインループ
    while (true) {
        // 1. フレームの開始時に、前のフレームのメモリを一括クリア
        mLinearAllocator.Clear();
    
        // 2. メモリを切り出してオブジェクトを生成
        void* address = mLinearAllocator.Allocate(sizeof(GameObject), alignof(GameObject));
        GameObject* go = new (address)GameObject();
        go->Position.x += 1.0f;
        // ...
    }
}

※go 変数が指すメモリは、次のフレームが始まった瞬間に問答無用でリセットされます。 そのため、「このオブジェクト、次のフレームでも使い回したいな」というデータをうっかりここに割り当ててしまうと、原因の追いづらいバグの温床になってしまいます。オブジェクトの生存期間には十分に気をつけて設計しましょう！

3.2 実装

カスタムアロケータを効率的に実装する前に、まずはコンピューター（CPU）がどのようにメモリを読み込んでいるのか、その舞台裏を覗いてみましょう。

3.2.1 アドレスアラインメント（境界整合）とは？

CPUがメモリからデータを読み込むとき、実は「1バイトずつ」細かく読み込んでいるわけではありません。通常は 「ワードサイズ」 と呼ばれる単位（32bit環境なら4バイト、64bit環境なら8バイト）ごとにまとめてガツッと読み込んでいます。

このとき、データの開始アドレスがワードサイズの倍数（4の倍数、8の倍数など）にぴったり揃っていない状態を 「ミスアライン（境界未整合）」 と呼びます。

もしアドレスがズレていると、CPUは本来1回で済むはずのメモリ読み込みを 「2回のワードにまたがって」 行わなければならなくなり、余計なステップが増えて処理速度が落ちてしまいます。最悪の場合、特定のハードウェアではクラッシュの原因にもなります。

だからこそ、自作アロケータでメモリを切り出すときは、この「ワードサイズの倍数にアドレスを揃える」というアラインメント規則に従うことが非常に重要なのです。

3.2.2 アラインメント調整関数の作成

では、中途半端なアドレスをアラインメントに適合するアドレスへと綺麗にジャンプさせる関数を作ってみましょう。

アラインメントの計算では、処理を高速化するためにビット演算を利用するのが一般的です。ビット演算が正しく機能するためには、アラインメント値が 必ず「2のべき乗（2, 4, 8, 16, 32...）」 である必要があります。

以下のサンプルコードをご覧ください。

// ==========================================
// CommonDefine.h （共通用の変数・関数を定義するファイル）
// ==========================================

#pragma once

#include <cassert>
#include <cstdint>

// アラインメント値が「2のべき乗」かどうかをチェックする関数
inline bool IsPowerOfTwo(size_t alignment) {
    return (alignment & (alignment - 1)) == 0;
}

// 元のアドレスから、アラインメントを満たすために「何バイト進めればよいか」を計算する関数
inline size_t GetAddressAdjustment(const void* address, size_t alignment) {
    assert(IsPowerOfTwo(alignment) && "Alignment must be a power of two");

    uintptr_t uAddress = reinterpret_cast<uintptr_t>(address);
    
    // 【ビット演算の魔術：O(1)でアラインメントの調整量を計算】
    //
    //  STEP 1: `uAddress & (alignment - 1)`
    //          現在のアドレスがアラインメント境界から「何バイトはみ出しているか（余り）」を求めます。
    //          (数学的な `uAddress % alignment` と完全に同じ処理を、高速なビット演算で行っています)
    //
    //          【超重要ルール】
    //           このビット演算が「余り」として正しく機能するのは、`alignment` が必ず「2のべき乗（2, 4, 8, 16...）」の時だけです。
    //           2のべき乗から1を引くことで（例: 8-1=7、バイナリで `0000 0111`）、下位ビットを綺麗に抽出するマスクが作れるためです。
    //
    //          - 例(パターンA): `uAddress` = 11, `alignment` = 8 のとき
    //                           11 & (8 - 1) -> 11 & 7 (0000 1011 & 0000 0111) = 3 (3バイトはみ出し)
    //          - 例(パターンB): `uAddress` = 16, `alignment` = 8 のとき
    //                           16 & (8 - 1) -> 16 & 7 (0001 0000 & 0000 0111) = 0 (はみ出しゼロ)
    //
    //  STEP 2: `alignment - STEP1`
    //            次の境界にぴったり辿り着くために「あと何バイト足りないか（不足分）」を計算します。
    //
    //          - 例(パターンA): 8 - 3 = 5 (あと5バイト進めれば、次の8の倍数「16」に届く)
    //          - 例(パターンB): 8 - 0 = 8 (最初から揃っているのに「あと8バイト進めろ」となり、ここではまだバグの状態)
    //
    //  STEP 3: `& (alignment - 1)`
    //            STEP2で発生する「最初からアドレスがぴったり揃っていた場合」のバグを防ぐための例外処理です。
    //            最後にもう一度このマスクを通すことで、綺麗に `0` にリセットしてくれます。
    //
    //          - 例(パターンA): 5 & (8 - 1) -> 5 & 7 (0000 0101 & 0000 0111) = 5 (ズレていた場合は、調整量「5」がそのまま維持される)
    //          - 例(パターンB): 8 & (8 - 1) -> 8 & 7 (0000 1000 & 0000 0111) = 0 (ぴったり揃っていた場合は「0」になる！)
    //
    return (alignment - (uAddress & (alignment - 1))) & (alignment - 1);
}

3.2.3 LinearAllocatorクラスの作成

それでは、いよいよLinearAllocatorの具体的なクラス設計と実装に入っていきましょう！

今回は、将来的に他のメモリ管理戦略もエンジンに組み込めるように、共通の基底クラスであるMemoryAllocatorを作成し、それを継承する形でLinearAllocatorを実装する設計にします。

まずは、ヘッダーファイルの宣言から見てみましょう。

// ==========================================
// MemoryAllocator.h （基底クラス）
// ==========================================

#pragma once

#include <cstddef>

class MemoryAllocator {
public:
    MemoryAllocator() = default;
    MemoryAllocator(size_t memorySize, void* address);
    virtual ~MemoryAllocator() = default;

    // 将来他のアロケータでオーバーライドできるように仮想関数として定義
    virtual void* Allocate(size_t memorySize, size_t alignment) { return nullptr; }
    virtual void* Allocate() { return nullptr; }
    virtual void Free(void* memory) {}
    virtual void Clear();

protected:
    void* mStartAddress;      // 確保したメモリブロックの先頭アドレス
    size_t mMemorySize;       // メモリの合計サイズ
    size_t mUsedMemory;       // 現在までに使用したメモリ量（バイト）
    size_t mAllocationCount;  // 割り当てを行った回数
};

// ==========================================
// LinearAllocator.h （派生クラス）
// ==========================================

#pragam once

#include"MemoryAllocator.h"

class LinearAllocator : public MemoryAllocator {
public:
    LinearAllocator() = default;
    LinearAllocator(size_t memorySize, void* address);
    ~LinearAllocator() override = default;

    // LinearAllocator用に処理をオーバーライド
    void* Allocate(size_t memorySize, size_t alignment) override;
    void Free(void* memory) override;
};

3.2.4 各メンバー関数の実装

続いて、ソースファイル（.cpp）の実装部分を見ていきます。

// ==========================================
// MemoryAllocator.cpp
// ==========================================

#include"MemoryAllocator.h"

MemoryAllocator::MemoryAllocator(size_t memorySize, void* address) 
    : mMemorySize(memorySize), mStartAddress(address), mUsedMemory(0), mAllocationCount(0) 
{
}

void MemoryAllocator::Clear() {
    // オフセットと割り当て回数をリセットするだけで、一括解放が完了！
    mUsedMemory = 0;
    mAllocationCount = 0;
}

// ==========================================
// LinearAllocator.cpp
// ==========================================
#include"LinearAllocator.h"
#include"CommonDefine.h"
#include <cassert>
#include <cstdint>

LinearAllocator::LinearAllocator(size_t memorySize, void* address) 
    : MemoryAllocator(memorySize, address) 
{
}

void* LinearAllocator::Allocate(size_t memorySize, size_t alignment) {
    if (memorySize == 0) {
        return nullptr;
    }

    // ポインタ計算をスムーズに行うため、void*とuintptr_tの共用体を用意
    union {
        void* asVoidPtrAddress;
        uintptr_t asUintPtrAddress;
    };

    // 現在の割り当て可能な位置（先頭アドレス + 使用済みサイズ）を計算
    asVoidPtrAddress = mStartAddress;
    asUintPtrAddress += mUsedMemory;

    // 前の節で作った関数を使い、アラインメントに必要な調整量を計算
    uintptr_t adjustment = GetAddressAdjustment(asVoidPtrAddress, alignment);

    // 【境界チェック】全体のメモリサイズを超えてしまわないか確認
    if (mUsedMemory + memorySize + adjustment > mMemorySize) {
        return nullptr; // メモリ不足（バッファオーバーフロー防止）
    }

    // アラインメントを考慮した正しいアドレスへ進める
    asUintPtrAddress += adjustment;

    // 使用済みメモリサイズを更新（要求サイズ + アラインメント調整分）
    mUsedMemory += memorySize + adjustment;
    mAllocationCount += 1;

    // アラインメント調整済みの切り出し先ポインタを返す
    return asVoidPtrAddress;
}

void LinearAllocator::Free(void* memory) {
    // 設計のセクションで説明した通り、LinearAllocatorは個別のメモリ解放をサポートしません
    assert(false && "LinearAllocator does not support individual free operations.");
}

• 実際にAllocate関数が呼ばれたとき、メモリブロックの内部がどう変化するのかを図にしてみました。青色の部分が、新しく要求されて切り出されたメモリです。割り当てが終わると、現在のオフセットがその分だけ右に進み、次の割り当てに備えます。

3.3 パフォーマンステスト

自作したアロケータが、通常の new キーワードによる動的割り当てと比べて実際にどれほど高速なのか、ベンチマークテストを実施して性能を検証してみましょう！

テストシナリオ
今回は、ゲームループを模した以下のようなシナリオで計測を行います。

1. 1フレーム内で、一気に10,000個の GameObject を生成する。
2. 生成した各オブジェクトに対して、簡単なロジック（座標の更新など）を実行する。
3. 次のフレームに進む前に、そのフレームで生成したオブジェクトをすべて削除する。
4. この一連の処理を1,000フレーム繰り返し、合計の処理時間（ミリ秒）を計測する。

それでは、それぞれの実装コードを見ていきましょう。

3.3.1. 通常のnew / deleteによる割り当て

まずは、一般的なヒープ割り当てを行うコードです。オブジェクトを個別に new し、フレームの最後で1つずつ delete していきます。

// ==========================================
// Main.cpp
// ==========================================

#include <chrono>
#include <iostream>
#include <vector>

// 前述のGameObject構造体が定義されている前提
struct GameObject {
    size_t UUID;
    float Position[3];
};

int main() {
    const int OBJECT_COUNT = 10000;
    std::vector<GameObject*> objectList(OBJECT_COUNT);
    double totalTimeMilliseconds = 0.0;
    
    const int MAX_FRAME = 1000;
    int currentFrame = 0;
    
    while (currentFrame < MAX_FRAME) {
        auto startTime = std::chrono::high_resolution_clock::now();
        
        // 1. オブジェクトの生成とロジック実行
        for (int idx = 0; idx < OBJECT_COUNT; ++idx) {
            GameObject* go = new GameObject(); // 個別のヒープ割り当て
            go->UUID = idx;
            go->Position[1] -= 1.0f;
            objectList[idx] = go;
        }
    
        // 2. フレームの最後で個別に解放
        for (GameObject* go : objectList) {
            delete go;
        }
        objectList.clear();
        
        auto endTime = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime).count();
        totalTimeMilliseconds += static_cast<double>(duration) / 1000.0; 
        
        currentFrame += 1;
    }

    std::cout << "【Standard new/delete】Total time: " << totalTimeMilliseconds << " ms\n";
    
    return 0;
}

3.3.2. LinearAllocatorによる割り当て

続いて、今回作成したLinearAllocatorを使用するコードです。最初にあらかじめ10MBのメモリを一括確保しておき、フレーム内ではそこから高速に切り出します。また、個別のdeleteは行わず、フレームの最後でClear()を1回呼ぶだけで解放を完了させます。

// ==========================================
// Main.cpp
// ==========================================

#include "LinearAllocator.h"
#include <chrono>
#include <iostream>
#include <vector>

struct GameObject {
    size_t UUID;
    float Position[3];
};

int main() {
    const int OBJECT_COUNT = 10000;
    std::vector<GameObject*> objectList(OBJECT_COUNT);
    double totalTimeMilliseconds = 0.0;

    // 10MBのメモリ領域をあらかじめ一括確保
    const size_t MEMORY_SIZE = 1024 * 1024 * 10; 
    void* memoryAddress = malloc(MEMORY_SIZE);
    
    LinearAllocator allocator(MEMORY_SIZE, memoryAddress);
    
    const int MAX_FRAME = 1000;
    int currentFrame = 0;
    
    while (currentFrame < MAX_FRAME) {
        auto startTime = std::chrono::high_resolution_clock::now();
        
        // 1. アロケータからの切り出しと「Placement new」によるオブジェクト生成
        for (int idx = 0; idx < OBJECT_COUNT; ++idx) {
            void* memory = allocator.Allocate(sizeof(GameObject), alignof(GameObject));
            // 確保したメモリ上にオブジェクトを構築
            GameObject* go = new (memory)GameObject();
            go->UUID = idx;
            go->Position[1] -= 1.0f;
            objectList[idx] = go;
        }
        
        // 2. フレームの最後で、アロケータのオフセットを一括リセット！
        allocator.Clear();
        objectList.clear();
        
        auto endTime = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime).count();
        totalTimeMilliseconds += static_cast<double>(duration) / 1000.0; 
        
        currentFrame += 1;
    }

    std::cout << "【Linear Allocator】Total time: " << totalTimeMilliseconds << " ms\n";
    
    // アプリケーション終了時に大元のメモリを解放
    free(memoryAddress);
    
    return 0;
}

3.3.3 パフォーマンス評価と考察

x64の「Releaseモード」でビルドした実行ファイル（.exe）を走らせ、5回計測した結果は以下の通りです。

【計測環境】

• CPU: 13th Gen Intel(R) Core(TM) i7-13620H (16 CPUs) ~ 2.4GHz
• RAM: 16GB

計測回数	標準の new / delete	自作 LinearAllocator
1回目	297.106 ms	27.419 ms
2回目	303.553 ms	26.240 ms
3回目	300.961 ms	25.887 ms
4回目	307.908 ms	26.706 ms
5回目	302.499 ms	25.406 ms
平均値	302.405 ms	26.332 ms

結果から言えること
スコアが示す通り、私たちが作成したカスタムアロケータは、標準の new キーワードによる割り当てに比べて約11倍以上という圧倒的なハイスピードで動作していることが確認できました！

もちろん、実際の実行速度はテストを実行するマシンのスペックや、一度に要求するメモリサイズ、オブジェクトの構造といった様々な要因によって変動します。しかし、どのような環境であっても「標準のヒープ割り当てより遥かに高速である」という事実は変わりません。

実際の本番環境に導入する前には、ハードウェアの特性やフレームごとの割り当てる要求サイズといった他の要素も慎重に検討する必要があります。

ですが、少なくとも「毎フレーム大量に生成して使い捨てるような一時的なメモリ管理においては、LinearAllocatorは標準のnewよりも圧倒的に有利である」という強力な選択肢を、私たちは自らの手で手に入れることができました。

4. まとめ

今回は、自作ゲームエンジン開発における強力な最適化手法の第一歩として、「Linear Allocator（線形アロケータ）」 の設計と実装、そしてベンチマークテストまでを解説しました。

標準の new/delete と比較して約11倍以上高速という驚異的な結果を目の当たりにし、低レイヤのメモリ管理がいかにゲームのパフォーマンスに直結するかを体感していただけたかと思います。

設計・実装時の重要ポイント

自作アロケータを設計する際に、絶対に忘れてはいけない重要なポイントを振り返っておきましょう。

1. 2のべき乗アラインメント（境界整合）の徹底
   CPUが最も心地よくメモリを読み込めるよう、アドレス調整関数ではビット演算の魔術を使いました。このトリックは、アラインメント値が必ず「2のべき乗（2, 4, 8, 16...）」であるときのみ正しく機能する、低レイヤならではの最適化です。
2. オブジェクトのライフサイクルの意識
   一瞬でメモリを初期化できる Clear() は非常に強力ですが、次のフレームをまたいで生存させたいデータをうっかりここに割り当ててしまうと、原因の追いづらいバグの温床になります。「毎フレーム使い捨てる一時メモリ」に用途を絞ることが成功の鍵です。
3. 個別の開放はサポートしない
   構造がシンプルのため、特定のオブジェクトだけを選んで削除することはできません。安全ガードとして、Free() メソッドには assert(false) を仕込み、開発中に間違った呼び出しを即座に検知できるように設計しました。
4. 割り当てるオブジェクトのサイズは自由（混在OK）
   「Linear Allocator」はポインタをただ前進させるだけのシンプルな構造であるため、「異なるサイズや異なる型のオブジェクト」を好きな順番で交互に割り当てることが可能です。今回は解説をシンプルにするために GameObject という単一の型だけを使ってテストを行いましたが、実際にはサイズ違いの構造体や文字列データなども、アラインメントさえ合わせれば同じメモリブロック内にスキマなく自由に詰め込むことができます。

5. メモリ管理の世界はさらに深く

LinearAllocatorは非常に高速で強力ですが、「個別にメモリを解放できない」「ライフサイクルが1フレーム以内に縛られる」という大きな制限がありました。実際のゲーム開発では、同じサイズの弾丸（ブレット）を大量に生成・削除したいシチュエーションが山ほどあります。

そこで次回は、LinearAllocatorの弱点を克服するさらに高度な2つのカスタムアロケータについて解説していく予定です！

• StackAllocator（スタックアロケータ）
  Linearの「一方向にしか進めない」という性質をベースにしつつ、マーカー（位置情報）を保存しておくことで、「特定のポイントまでメモリの状態を巻き戻す（LIFO：後入れ先出し）」ことができるアロケータです。
• PoolAllocator（プールアロケータ）
  あらかじめ「同じサイズ（型）のメモリブロック」を大量に準備しておくアロケータです。サイズが均一であるため、Linearでは不可能だった「任意のタイミングでの個別解放」を可能にします。

それでは、次回でお会いしましょう！
ここまで読んでいただき、ありがとうございました！