从零开始手敲次世代游戏引擎（十八）

作者netwarm007发表在学习笔记、技术分享标签：

如上一篇预告的，本篇我们对游戏引擎当中的内存管理进行一些初步的探讨。
首先，关于游戏引擎内存管理的必要性，除了为了实现加载远大于物理内存容量的内容（比如开放世界游戏）之外，还有很多性能和调试方面的考虑。关于这方面在参考引用1当中有比较详细且风趣的阐述。
当然参考引用1成文时间是差不多两年以前，很多参数在今天看来已经有了一些变化。比如当代CPU和内存之间的带宽一般在几十个Gbps，而GPU与内存（显存）之间的带宽已经飙升到几百个Gbps的水准。但是这并没有改变内存访问依然远远落后于CPU／GPU计算能力的状况。
而且尤为重要的是，对于游戏引擎（运行时）来说，一切都是数个毫秒（VR游戏要求120fps）到十数个毫秒（60fps），最多也就是33毫秒（30fps）的人生的轮回。在这样的系统当中，每一个毫秒都弥足珍贵，都值得我们去拼。（当然，就如我们前一篇指出的，也并不是所有的处理都需要按照这个节奏去跑）
这也回答了在本系列为什么采用C／C++这种“中级语言”进行编程。因为这是一个在性能／控制力／可维护性上比较理想的折衷点。
这里我补充一下关于malloc／new的知识，为什么说它们比较低效。
我们知道，操作系统的主要功能就是管理计算机系统的各种硬件资源。应用程序需要使用硬件资源到时候，需要向操作系统进行申请。而这种申请的接口，就被称为系统调用。

在近代操作系统当中，出于安全方面的考虑，操作系统与用户程序不是跑在一个级别上的。操作系统拥有所有的特权，而用户程序只是跑在操作系统提供的一个虚拟环境之上。用户程序看到的内存地址并不是真正的物理内存地址，而是一个虚拟的地址空间。这个地址空间是完全为用户程序定制的，不同的用户程序，即使这个地址一样，也不是指向同一个物理内存（或者分页文件）地址。

因此，当我们调用malloc／new进行heap分配的时候，并不是我们的线程直接杀入内核，去领一块内存出来。而是我们提交一个申领申请，放在放申请单的盒子里，然后等。操作系统方面按顺序处理这些申请，处理完了将处理结果放在处理结果盒子里，然后叫我们的号让我们去领。这个过程和我们在生活当中到特权机关去办事很类似。

虽然这些系统API调用看起来都是同步的，但实际上这是一个异步操作，只不过在操作完成之前，我们的线程会被block住，操作完成了，线程unblock，函数返回，看起来就像普通函数调用那样，其实这是一个比较复杂的过程。

而且在这个过程当中的参数传递，一般情况下都会发生拷贝。这是因为操作系统和用户程序分别工作在不同的地址空间，因此直接传递指针（地址）也是没有什么意义的。

因此，提高程序在CPU端的执行效率的一个重要手段，就是要减少系统调用。在程序初始化阶段就一次申领所需的资源，然后自己内部进行分配管理，这就是一种常用的减少系统调用的方法。

参考引用4提供了一种基于块链（block chain）的内存管理方法。我们首先将它引入到我们的引擎当中。这部分属于引擎的核心内容，因此我们将文件创建在Framework/Common下面：

Allocator.hpp

#include <cstddef>
#include <cstdint>

namespace My {

    struct BlockHeader {
        // union-ed with data
        BlockHeader* pNext;
    };

    struct PageHeader {
        PageHeader* pNext;
        BlockHeader* Blocks() {
                return reinterpret_cast<BlockHeader*>(this + 1);
        }
    };

    class Allocator {
        public:
                // debug patterns
                static const uint8_t PATTERN_ALIGN = 0xFC;
                static const uint8_t PATTERN_ALLOC = 0xFD;
                static const uint8_t PATTERN_FREE  = 0xFE;

                Allocator(size_t data_size, size_t page_size, size_t alignment);
                ~Allocator();

                // resets the allocator to a new configuration
                void Reset(size_t data_size, size_t page_size, size_t alignment);

                // alloc and free blocks
                void* Allocate();
                void  Free(void* p);
                void  FreeAll();
        private:
#if defined(_DEBUG)
                // fill a free page with debug patterns
                void FillFreePage(PageHeader* pPage);

                // fill a block with debug patterns
                void FillFreeBlock(BlockHeader* pBlock);

                // fill an allocated block with debug patterns
                void FillAllocatedBlock(BlockHeader* pBlock);
#endif

                // gets the next block
                BlockHeader* NextBlock(BlockHeader* pBlock);

                // the page list
                PageHeader* m_pPageList;

                // the free block list
                BlockHeader* m_pFreeList;

                size_t      m_szDataSize;
                size_t      m_szPageSize;
                size_t      m_szAlignmentSize;
                size_t      m_szBlockSize;
                uint32_t    m_nBlocksPerPage;

                // statistics
                uint32_t    m_nPages;
                uint32_t    m_nBlocks;
                uint32_t    m_nFreeBlocks;

                // disable copy & assignment
                Allocator(const Allocator& clone);
                Allocator &operator=(const Allocator &rhs);
    };
}

上面的代码相对于参考引用4的改动主要是下面几个方面：

  1. 根据我们引擎整体的命名风格调整了变量的名字
  2. 使用更为明确的数据类型，比如uint32_t，以及移植性更好的数据类型，如size_t
  3. 添加了必须且跨平台的C++标准头文件
  4. 使用预编译指令将用于调试的代码标出，只在调试版本当中编译这些代码

Allocator.cpp

#include "Allocator.hpp"
#include <cassert>
#include <cstring>

#ifndef ALIGN
#define ALIGN(x, a)         (((x) + ((a) - 1)) & ~((a) - 1))
#endif

using namespace My;

My::Allocator::Allocator(size_t data_size, size_t page_size, size_t alignment)
        : m_pPageList(nullptr), m_pFreeList(nullptr)
{
    Reset(data_size, page_size, alignment);
}

My::Allocator::~Allocator()
{
    FreeAll();
}

void My::Allocator::Reset(size_t data_size, size_t page_size, size_t alignment)
{
    FreeAll();

    m_szDataSize = data_size;
    m_szPageSize = page_size;

    size_t minimal_size = (sizeof(BlockHeader) > m_szDataSize) ? sizeof(BlockHeader) : m_szDataSize;
    // this magic only works when alignment is 2^n, which should general be the case
    // because most CPU/GPU also requires the aligment be in 2^n
    // but still we use a assert to guarantee it
#if defined(_DEBUG)
    assert(alignment > 0 && ((alignment & (alignment-1))) == 0);
#endif
    m_szBlockSize = ALIGN(minimal_size, alignment);

    m_szAlignmentSize = m_szBlockSize - minimal_size;

    m_nBlocksPerPage = (m_szPageSize - sizeof(PageHeader)) / m_szBlockSize;
}

void* My::Allocator::Allocate()
{
    if (!m_pFreeList) {
        // allocate a new page
        PageHeader* pNewPage = reinterpret_cast<PageHeader*>(new uint8_t[m_szPageSize]);
        ++m_nPages;
        m_nBlocks += m_nBlocksPerPage;
        m_nFreeBlocks += m_nBlocksPerPage;

#if defined(_DEBUG)
        FillFreePage(pNewPage);
#endif

        if (m_pPageList) {
            pNewPage->pNext = m_pPageList;
        }

        m_pPageList = pNewPage;

        BlockHeader* pBlock = pNewPage->Blocks();
        // link each block in the page
        for (uint32_t i = 0; i < m_nBlocksPerPage; i++) {
            pBlock->pNext = NextBlock(pBlock);
            pBlock = NextBlock(pBlock);
        }
        pBlock->pNext = nullptr;

        m_pFreeList = pNewPage->Blocks();
    }

    BlockHeader* freeBlock = m_pFreeList;
    m_pFreeList = m_pFreeList->pNext;
    --m_nFreeBlocks;

#if defined(_DEBUG)
    FillAllocatedBlock(freeBlock);
#endif

    return reinterpret_cast<void*>(freeBlock);
}

void My::Allocator::Free(void* p)
{
    BlockHeader* block = reinterpret_cast<BlockHeader*>(p);

#if defined(_DEBUG)
    FillFreeBlock(block);
#endif

    block->pNext = m_pFreeList;
    m_pFreeList = block;
    ++m_nFreeBlocks;
}

void My::Allocator::FreeAll()
{
    PageHeader* pPage = m_pPageList;
    while(pPage) {
        PageHeader* _p = pPage;
        pPage = pPage->pNext;

        delete[] reinterpret_cast<uint8_t*>(_p);
    }

    m_pPageList = nullptr;
    m_pFreeList = nullptr;

    m_nPages        = 0;
    m_nBlocks       = 0;
    m_nFreeBlocks   = 0;
}

#if defined(_DEBUG)
void My::Allocator::FillFreePage(PageHeader *pPage)
{
    // page header
    pPage->pNext = nullptr;
 
    // blocks
    BlockHeader *pBlock = pPage->Blocks();
    for (uint32_t i = 0; i < m_nBlocksPerPage; i++)
    {
        FillFreeBlock(pBlock);
        pBlock = NextBlock(pBlock);
    }
}
 
void My::Allocator::FillFreeBlock(BlockHeader *pBlock)
{
    // block header + data
    std::memset(pBlock, PATTERN_FREE, m_szBlockSize - m_szAlignmentSize);
 
    // alignment
    std::memset(reinterpret_cast<uint8_t*>(pBlock) + m_szBlockSize - m_szAlignmentSize, 
                PATTERN_ALIGN, m_szAlignmentSize);
}
 
void My::Allocator::FillAllocatedBlock(BlockHeader *pBlock)
{
    // block header + data
    std::memset(pBlock, PATTERN_ALLOC, m_szBlockSize - m_szAlignmentSize);
 
    // alignment
    std::memset(reinterpret_cast<uint8_t*>(pBlock) + m_szBlockSize - m_szAlignmentSize, 
                PATTERN_ALIGN, m_szAlignmentSize);
}
#endif
My::BlockHeader* My::Allocator::NextBlock(BlockHeader *pBlock)
{
    return reinterpret_cast<BlockHeader *>(reinterpret_cast<uint8_t*>(pBlock) + m_szBlockSize);
}

上面的代码相对于参考引用4的改动主要是下面几个方面：

  1. 反映了头文件当中的变化
  2. 使用了更为高效的对齐计算算法（有前提条件，具体见代码注释）

好了。接下来我们修改我们的CMakeLists.txt，加入新文件

C:UsersTim.AzureADSourceReposGameEngineFromScratch>gvim FrameworkCommonCMakeLists.txt
add_library(Common
Allocator.cpp
BaseApplication.cpp
GraphicsManager.cpp
main.cpp
)

然后我们就可以尝试编译看看，是否可以通过。具体的编译过程在文章5已经详细叙述过了，这里就不赘述。

但是事实上我们会需要不止一种的Memory Allocator。因为我们的程序当中会使用的对象有着不同的尺寸，我们无法使用一种固定的Block Size来满足各种各样的分配尺寸需求。因为如果Block Size过小，显然无法满足需要；如果过大，则是浪费。参考引用5当中也谈到了这一点。

此外，我们某些buffer是给CPU使用，有些是给GPU使用，有些是给两者使用。有些只需要高速地读，比如贴图；有些需要高速的写，比如Rendering Target；有些则需要保证同步，比如Fence。我们需要实现这些控制。

并且，如上一篇所述，我们的各个模块将采用一种异步并行的方式执行各自的任务。近代CPU都是多核的，我们需要充分地利用这个特性，就需要多线程。但是目前我们的Allocator还不是线程安全的。线程安全的代码需要一种排他锁定的机制，但是这种机制又往往是低效和容易带来死锁问题的。我们需要平衡这些问题。

我们将在后文继续讨论这些问题并改善我们的内存管理代码。

参考引用

  1. Writing a Game Engine from Scratch – Part 2: Memory
  2. Gallery of Processor Cache Effects
  3. Game Engine Architecture
  4. Memory Management part 1 of 3: The Allocator | Ming-Lun “Allen” Chou
  5. Memory Management part 2 of 3: C-Style Interface | Ming-Lun “Allen” Chou

本作品采用知识共享署名 4.0 国际许可协议进行许可。

留下评论