游戏引擎基础组件——内存管理
图片来自网络，如有侵权，请联系作者删除
在3D游戏引擎中，通常都会有一个内存管理器来控制内存的分配和回收操作。为什么呢？因为相对于CPU计算速度来说，内存与CPU之间的传输速度实在是太慢了，更可怕的是如果直接使用系统的分配内存接口（比如new），还涉及到CPU上下文的切换，这个更加慢得可怕，到底有多慢，看看下面的数字就就知道了：
我的CPU主频是3.6GHz，也就是每个指令执行的时间为0.26ns。内存每次寻址所需要的时间是100ns，是CPU执行一次指令所需要时间的385倍，一次 CPU 上下文切换（系统调用）需要大约 1500ns，也就是1.5us，是CPU执行一次指令所需时间的5769倍。从人类感知的角度上看，如果说CPU执行一次指令的时间为1s，那么CPU上下文切换一次大概就需要1.6小时，我都可以睡一觉了！
游戏是个软实时系统，它要求我们必须至少每秒做30次刷新，这样才能保证基本的体验，注意，只是基本。对VR来说，要求更为严苛，至少需要每秒刷新120次才不会有眩晕感，每秒120次是什么概念？每一帧的逻辑计算+渲染的时间只有8.33ms，每一毫秒都值得我们拼劲全力去争取！
本文做了一个内存管理器类（MemoryManager）和一个分配器类（Allocator）的雏形。MemoryManager类是用户的交互接口，所有的内存分配和回收操作都是通过MemoryManager类提供的方法来执行的。Allocator类是真正保有内存块的类，它是一种分配策略的抽象，每一个Allocator实例都表示一种分配策略。MemoryManager类保存不同的Allocator来满足不同的内存分配需求，这也是MemoryManager的核心职责之一。
Allocator（分配器）
就像前文所说的，Allocator是真正保有向操作系统申请的内存块的对象，每一种Allocator都对应着一种分配策略。思路是：将内存块分为页（Page）和块（Block）两个单位。一页内存都包含多个块，当这一页内存被用完了，就再向系统申请一页内存。页与页之间，块与块之间采用链表的方式来连接，方便分配与回收。而页本身不作为分配的单位，它只是我们为了节省时间，提前向系统申请的内存的尺寸。
接下来，我们着手实现这个分配器。我们的块是用链表的结构串联起来的，所以一个块头结构必不可少：
struct BlockHeader {
BlockHeader* pNext; // 指向下一个块头处
};
同样，页的组织方式与块类似，所以页头的结构也不能缺：
struct PageHeader {
PageHeader* pNext；
BlockHeader* BlockStart() {
return reinterpret_cast<BlockHeader*>(this + 1); // PageHeader之后就是块的起始位置
}
};
PageHeader结构体比BlockHeader多出一个方法，用于获取这一页的第一个块的地址，就是PageHeader这个结构体之后的位置。
具体的分配器类，对外至少需要3个接口：分配内存块、释放内存块、重置分配器。
对每一个分配器类来说，它的页尺寸有多大，块尺寸有多大，对齐的方式是什么样子的，这些都是固定的，通过重置操作来设置。除此之外，因为要对齐，所以每一个块里有多少是实际能使用的尺寸，有多少是对齐补足的尺寸，这些都要有明确的记录。基于这些思考，我们可以给分配器添加这些属性：
private:
uint32_t m_BlockSize; // 块的尺寸
uint32_t m_PageSize; // 页的尺寸
uint32_t m_BlockCountPerPage; // 每页的块数
uint32_t m_AlignmentSize; // 对齐尺寸
重置操作，本质上已经把这个Allocator变成了“另一个”Allocator，所以需要释放当前的所有内存，然后设置参数。设置过程中，我们要加一些限制：1、Block的尺寸必须大于等于BlockHeader的尺寸。2、每个Page必须至少包含一个块。这两条限制一加，我们就需要对输入的参数进行检查与修正。
#ifndef ALIGN
#define ALIGN(n, a) (((n) + (a - 1)) & ~((a) - 1)) // 获取对齐的最小值
#endif
// 重置分配器
void Panda::Allocator::Reset(uint32_t inPageSize, uint32_t inBlockSize, uint32_t inAlignment) {
FreeAll();
// 块的大小必须大于块头的大小，并且需要对齐
size_t minBlockSize = inBlockSize > sizeof(BlockHeader)? inBlockSize : sizeof(BlockHeader);
m_BlockSize = ALIGN(minBlockSize, inAlignment);
m_AlignmentSize = m_BlockSize - minBlockSize;
// 一页至少一个块
m_PageSize = inPageSize > (m_BlockSize + sizeof (PageHeader))? inPageSize : (m_BlockSize + sizeof(PageHeader));
m_BlockCountPerPage = (m_PageSize - sizeof(PageHeader)) / m_BlockSize;
}
分配内存块的思路是：从当前保存的空余块列表中拿一个块出来返回，如果当前没有空余的块了，那么就分配一页，将这一页上的所有块保存到空余块列表中，然后取第一块返回。
为此，先添加类的成员：空余块列表、空余块数、页列表、当前已分配的页数。
BlockHeader* m_pFreeBlockList; // 空余块列表
uint32_t m_nFreeBlockCount; // 空余的块数
PageHeader* m_pPageList; // 页列表
uint32_t m_nPageCount; // 页数
然后是具体的分配函数：
void* Panda::Allocator::Allocate() {
if (m_pFreeList == nullptr) {
// 分配一页内存
PageHeader* pNewPage = reinterpret_cast<PageHeader*>(new uint8_t[m_PageSize]);
m_FreeBlockCount += m_BlockCountPerPage;
m_BlockCount += m_BlockCountPerPage;
m_PageCount++;
pNewPage->pNext = m_pPageList;
m_pPageList = pNewPage;
// 将所有内存块串联起来
BlockHeader* pBlockStart = m_pPageList->BlockStart();
m_pFreeBlockList = pBlockStart;
for (int i = 0; i < m_nBlockCountPerPage; ++i) {
pBlockStart->pNext = NextBlock(pBlockStart);
pBlockStart = pBlockStart->pNext;
}
pBlockStart->pNext = nullptr;
}
// 取一块内存返回
BlockHeader* pBlock = m_pFreeBlockList;
m_pFreeBlockList = m_pFreeBlockList->pNext;
m_FreeBlockCount--;
return reinterpret_cast<void*>(pBlock);
}
分配函数用到了通过Block的指针获取下一个块地址的函数，这个函数是这样实现的：将当前的Block指针强制转换成指向uint8_t的指针，然后偏移m_BlockSize，在将得到的指针强制转成BlockHeader返回。
Panda::BlockHeader* Panda::Allocator::NextBlock(BlockHeader* pCurrentBlock) {
return reinterpret_cast<BlockHeader*>( reinterpret_cast<uint8_t*> (pCurrentBlock) + m_nBlockSize);
}
最后是释放内存，这个操作非常简单，只要把传入的指针重新加回空余块列表就行了：
void Panda::Allocator::Free(void* p)
{
BlockHeader* pHeader = reinterpret_cast<BlockHeader*>(p);
pHeader->pNext = m_pFreeBlockList;
m_pFreeBlockList = pHeader;
m_FreeBlockCount++;
}
最后，补足Reset函数中调用的FreeAll函数。释放所有内存需要一页一页地删除分配的内存块，直到所有的内存块都删除，并且重置相关属性：
void Panda::Allocator::FreeAll()
{
PageHeader* pFree = m_pPageList;
while (pFree) {
PageHeader* pTemp = pFree;
pFree = pFree->pNext;
delete[] reinterpret_cast<uint8_t*>(pTemp);
}
// 只重置这两个属性因为这两个属性是要用于判断的，其他的都是保存作用
m_pPageList = nullptr;
m_pFreeBlockList = nullptr;
}
内存管理的最重要工作是什么？内存分配的策略。管理一系列的内存分配器，收到分配内存请求的时候选择适当的分配器分配内存，然后提供一个回收内存的接口。
我们采用的策略是事先初始化一堆分配不同尺寸内存分配器（因为我们不知道用户想要多大的内存），在接到分配内存的请求时，根据需要分配内存的大小，选择合适的内存分配器分配内存并返回。
static const uint32_t k_BlockSizes[] = {
// 4字节增加
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48,
52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96,
// 32字节增加
128, 160, 192, 224, 256, 288, 320, 352, 384,
416, 448, 480, 512, 576, 608, 640,
// 64字节增加
704, 768, 832, 896, 960, 1024
};
static const uint32_t k_PageSize = 8192; // 页尺寸
static const uint32_t k_Alignment = 4; // 对齐值
static const uint32_t k_BlockSizeCount = sizeof (k_BlockSizes) / sizeof (k_BlockSizes[0]); // 预配置的分配器数量
static const uint32_t k_MaxBlockSize = k_BlockSizes[k_BlockSizeCount - 1]; // 预配置的分配器分配的最大内存数
一个分配器的数组，一张查询表。0~最大尺寸之间的所有尺寸都可以分配，什么尺寸用什么分配器则是由查询表决定的。
private:
static Allocator* m_pAllocators;
static uint32_t* m_pLookUpTable;
初始化函数需要做两件事，1是创建分配器，并且将分配器全部初始化。2是初始化查询表，我们有k_BlockSizeCount个分配器，但是我们要支持1024B以下所有大小的分配，那么如果需要分配一个490B空间的内存，该用哪个分配器呢？答案是512字节的分配器。这很好理解，512B分配器是超过490B，并且最接近490B的分配器。查询表的作用就是当我输入490B的时候，我得到的是一个512B的分配器。
bool MemoryManager::Initialize() {
static bool s_bInitialized = false;
if (!s_bInitialized)
{
// 初始化分配器
m_pAllocators = new Allocator[k_BlockSizeCount];
for (size_t i = 0; i < k_BlockSizeCount; ++i)
{
m_pAllocators[i].Reset(k_BlockSizes[i], k_PageSize, k_Alignment);
}
// 初始化查询表
m_pLookUpTable = new uint32_t[k_MaxBlockSize + 1];
size_t j = 0;
for (size_t i = 0; i <= k_MaxBlockSize; ++i)
{
if (i > k_BlockSizes[j])
{
++j;
}
m_pLookUpTable[i] = j;
}
s_bInitialized = true;
}
return true;
}
内存管理器的核心功能，分配与释放内存，有了查询表之后，分配和释放的过程变得非常简单。如果分配/释放的内存过大，那么就用原生的c方法来分配/释放。
void* MemoryManager::Allocate(size_t inSize)
{
Allocator* pAlloc = LookUpAllocator(inSize);
if (pAlloc)
return pAlloc->Allocate();
else
return malloc(inSize);
}
void MemoryManager::Free(void* p, size_t inSize)
{
Allocator* pAlloc = LookUpAllocator(inSize);
if (pAlloc)
pAlloc->Free(p);
else
free(p);
}
为了方便使用，提供一个New和一个Delete模板函数，这里可以用语法糖（骚操作）的方法来实现Delete函数
public:
// C++11的新机制，可变参数模板
template<typename T, typename... Arguments>
T* New(Arguments... parameters)
{
return new (Allocate(sizeof(T)))T(parameters...);
}
template<typename T>
void Delete(T* p)
{
p->~T();
Free(reinterpret_cast<void*>(p), sizeof(T));
}
这样，关于内存管理的核心功能就全部完成了，剩下的就是一些组合到引擎之中，构造函数，析构函数，禁用拷贝构造函数和赋值操作符之类的操作了。具体的代码我就不贴出来了，如果有疑问，可以参考这里：branch_MemoryManager
总结
相对而言，这个雏形还是非常简单的。其他的分配策略比如顺序分配，实现方式就和这篇文章里的不同了，顺序分配并不把内存分块，而是保有一个头部结构和一个尾部结构来指明当前有多少内存是可用的，需要分配的时候，分配出去的内存也需要有一个头部结构和一个尾部结构，这当然会造成浪费（本文的实现中没有尾部结构，头部结构也是作为分配内存的一部分返回的。因为我们的大小是固定的，没有再保存相关信息的必要。），但是这也更加灵活（不需要那么多分配器了）。更详细的实现方案，请参考下面列出的参考资料五。
参考资料
一、让 CPU 告诉你硬盘和网络到底有多慢
二、从零开始手敲次世代引擎（十九）
三、Memory Management part 2 of 3: C-Style Interface
四、Memory Management(Wiki)
五、3D游戏引擎设计
