動態記憶體管理

malloc、free函式或是C++的new、delete運算符是常見的動態分配記憶體的手段，也被稱之為堆分配(heap allocation)，是效率不高的一種做法。簡而言之，在近代的作業系統上，應用程式通常是運作在用戶模式(User mode)上面的，而上述分配記憶體的方法需要切換至內核模式(Kernel mode)處理完請求後再切換回去，而這是一個耗費時間的方法。然而遊戲引擎無法避免動態記憶體分配。因此實現一個定製的分配器，預先分配記憶體後，我們便能在User mode執行記憶體的分配了。

Stack Allocator

Stack Allocator是一個相對容易實現的分配器，預先使用malloc()或是new來分配一大塊的連續記憶體空間。使用一個指針來指向Stack的頂端，指針以下是以分配的記憶體空間，以上則是仍然未分配的。以下是Stack Allocator的範例概念。

class StackAllocator
{
public:
    // Stack的標記 表示當前的頂端
    // 使用者只能往回上一個刻度的標記，而非Stack任意位置。
    typedef U32 Marker;
    
    // 初始話並建構一個Stack Allocator
    StackAllocator(U32 stackSize_bytes);
    
    // 給定一個記憶體大小，並從頂端分配
    void* alloc(U32 size_bytes);
    
    //取得頂端標記
    Marker getMarker();
    
    // 回到上一個標記
    void freeToMarker(Marker marker);
    
    // 清空整個Stack
    void clear();
};

Pool Allocator

Pool Allocator 的特色是是分配大量同等的尺寸的記憶體空間。用於矩陣、迭代器(iterator)、可渲染的網格實例等等...

單幀與雙緩衝記憶體分配器

在遊戲循環中，有時候需要分配一些臨時使用的數據，或許是在循環結束後再釋放又或許在一幀的結束時即可釋放，而多數遊戲引擎都會支持這兩種分配器，單幀分配器(single-frame allocator)和雙緩衝分配器(double-buffered allocator)

單幀分配器

分配給一幀循環時使用的記憶體空間，在每幀的開始時重新清空分配器。其中的好處是分配的記憶體空間不需要手動釋放，在下一幀開始時會自動清除，效率也屬於高效。而缺點就在於，若是將指向單幀分配器的指針跨幀使用將會產生不可預期的錯誤，這點還需要稍加注意。而以下是概念的範例。

StackAllocator g_singleFrameAllocator;

while(true)
{
    // 幀開始時清除緩衝區
    g_singleFrameAllocator.clear();
    //...
    
    //分配記憶體空間給單幀分配器
    void* p = g_singleFrameAllocator.alloc(nBytes);
    
    // ...
}

雙緩衝分配器

雙緩衝分配器使第i幀的記憶體空間能使用於第i+1幀。範例如下。

class DoubleBufferedAllocator
{
    U32            M_curStack;
    stackAllocator m_stack[2];
public:
    void swapBuffer()
    {
        m_curStack = !m_curStack;
    }
    
    void clearCurrentBuffer()
    {
        m_stack[m_curStack].clear();
    }
    
    void* alloc(U32 mBytes)
    {
        return m_stack[m_curStack].alloc(nBytes);
    }
    
    //...
}
DoubleBufferedAllocator g_doubleBuffAllocator;

while(true)
{   
    //交換雙緩衝分配器的緩衝區
    g_doubleBuffAllocator.swapBuffers();
    
    //清空、初始化現在的緩衝區
    g_doubleBuffAllocator.clearCurrentBuffer();
    
    // ...
    
    //分配現在的記憶體空間，前一幀的數據不被影響
    void p = g_doubleBuffAllocator.alloc(nBytes);
}

記憶體碎片

動態記憶體的分配還有另外一個問題，隨著釋放與分配會逐漸產生如下圖的記憶體碎片(memory fragmentation)。

而記憶體碎片將會導致如下的狀況發生，當你今天要求一個128KB的記憶體空間分配的請求，或許分配器中有兩個64KB、或是更為細小，但仍有足夠空間的情況，但由於並非連續記憶體空間最後將導致請求的失敗。不過實際上，上面所介紹的 Stack Allocator 與 Pool Allocator 是可以避免記憶體碎片的狀況發生的。Stack Allocator分配的記憶體空間總是連續的，並且只能依反向順序一個一個釋放記憶體、而Pool Allocator所分配的記憶體空間都是一樣大的，可以避免上述情況發生。但若是有需要分配及釋放不指定空間大小的對象，在釋放時也希望以任何的順序進行時，Stack Allocator 與 Pool Allocator明顯的是無法完成我們的需求，在這種情況下就需要避免記憶體碎片的方法了。

碎片的整理與重定位

整理碎片的概念並不複雜，既然造成碎片的原因是因為會有許多分散、大小不一的"洞"，那我們便移動記憶體空間將洞都集合在一起便行了。但棘手的事情是，還需要去處理因為移動記憶體空間所產生的問題，例如若是有指標指向這些記憶體空間，需要對指標進行重定位(relocation)的動作。

分攤碎片整理成本

在整理碎片的過程中，我們需要複製記憶體空間，而過程操作是緩慢的。因此我們可以將碎片整理分攤在多個幀之間，使得遊戲的幀率並不會受到明顯的影響。

後記

在寫這篇之前我對記憶體管理有點沒什麼認識，直到重新爬了一些文章後才重新又思考了一下這裡的概念。才驚覺它的重要之處，或許假日後找時間繼續翻閱這部分的文章吧，如果還有想看關於記憶體管理系統的可以參考這篇文章。

昨天好像有說原本還打算講些Containner、Log、I/O之類的部分。但筆者想了想，在實作時我會使用一些第三方函式庫去完成這部分的功能，那我們就留到那時候再一起說吧! 明天就讓我們進入下一部分組件吧!