内存管理
内存对游戏效能的影响主要两方面：
-
使用
new或者malloc()进行动态内存分配，很慢效能很低。应当避免动态内存分配，或者写一个内存分配器。 -
在现代CPU上，内存分配模式会大大影响效能。尽量把数据置于连续内存块，避免分散存储。
（Creedon:尽量使用数组而非链表）
《游戏引擎原理实践》推荐的内存管理方式
Cheng：内存管理必要性：
Cheng：一是要加快内存分配速度，有效利用内存。二是处理内存泄露问题。
Cheng：内存泄露的处理包括找到没有释放的指针，找到野指针，找到导致内存不断增长的原因。
Cheng：直接用
new分配内存有很多隐患，到项目中期可能时不时会出现系统崩溃和内存占用逐渐增加的问题。
（Cheng）new操作符重载：
Cheng：如果重载了全局的
new就意味着后续所有用到new的地方都是重载过的，如果类内重载的话，只有继承这个类的才用重载的new。
Cheng：建议使用重载全局的new。
//成员函数的形式重载new操作符
void * className::operator new( size_t size ){
//TODO:
}
//全局形式重载new操作符
void * operator new( size_t size ){
//TODO:
}
（Cheng）用宏封装new/delete：
Cheng：为了使用统一使用全局内存分配，可以使用宏封装。
#define MY_NEW new
#define MY_DELETE delete
o 优化内存分配
动态内存分配的低效性：
通过new/delete或者malloc()/free()动态分配又称堆分配。
- 动态内存分配低效的原因：
- 堆分配器是通用的，它必须处理任何大小的分配请求，从1字节到1000兆字节。所以需要大量的管理开销。
- 堆分配器在大多数操作系统中需要上下文切换，即从用户模式切换至内核模式处理请求，再切换回原来的程序，耗费了非常多的时间。
- 解决问题的经验法则是：
- 维持最低限度的堆分配，永不在紧凑循环中使用堆分配。
- 实现自定义的分配器。
自定义分配器的高效性：
- 自定义的分配器性能更高的原因：
- 自定义分配器从预分配的内存(
new/malloc或者全局变量)中完成分配请求，避分配过程在用户模式下。 - 通过对自定义分配器的使用模式(usage pattern)做出多个假设，自定义分配器便可以比通用的堆分配器高效得多。
o 几种分配器
栈分配器：
我们要分配一大块连续内存，可以使用new、malloc或者声明全局字节数组(最后的方法，实际上会从可执行文件的BSS段里分配内存)。另外要安排一个指针指向堆栈顶端，指针以下的内存是已分配的，指针以上的内存是未分配的。
对于每个分配请求，仅需把指针往上移动请求的字节数量。堆栈分配器可以使用marker来释放/回滚。
还有一种分配器称为双端堆栈分配器。即一块内存供两个堆栈分配器使用，一个从底向上分配，一个从顶往下分配。
池分配器：
软件工程中常常会分配大量同等尺寸的小块内存。例如矩阵、迭代器、渲染网格实例等。池分配器(pool allocator)是这类分配模式首选。
池分配器工作方式：分配一大块内存，大小刚好是分配元素的倍数。池内的每个元素会被加到一个存放自由元素的链表，初始化时自由链表包含所有元素。
可以使用静态链表。（静态链表可以用索引来替代指针去指示next元素）
自动对齐的分配器：
每个变量和数据对象都有对其要求。（对齐对于cpu读写很重要）内存分配器必须传回对齐的内存块。
实现功能很简单：在分配内存时，分配多于请求长度的内存。再将内存调整至适当的对齐，返回对齐后的内存地址。
在大多数实现中，额外分配的字节数等于对齐字节数。例如要分配16字节对齐的内存，就额外多分配16字节。
最差的情况只需移动15字节。额外分配16字节的原因是使用相同的计算方式，加速代码。代价是每次分配浪费1字节。
多出的1字节可以利用来存储释放内存所需的额外信息。
计算偏移量的方法：首先用掩码按位与未对齐内存地址来计算错位(misalignment)的字节数，然后用期望的对齐减去该值，就是调整偏移量。
掩码等于对齐减去1。（例如16字节掩码就是(16-1)=15=0x0000000F）
要释放原本分配的内存，需要存储一些元信息至额外分配的内存，释放内存时用来把调整后的地址转换为原本的地址。（最小的调整量为1字节，这一个字节足够储存偏移量，我们可以将偏移量存储值调整后的地址的前一个字节）
void* allocateAligned(size_t size_bytes, size_t alignment)
{
ASSERT(alignment >= 1);
ASSERT(alignment <= 128);
ASSERT((alignment & (alignment - 1)) == 0); // pwr of 2
// Determine total amount of memory to allocate.
size_t expandedSize_bytes = size_bytes + alignment;
// Allocate unaligned block & convert address to uintptr_t.
uintptr_t rawAddress = reinterpret_cast<uintptr_t>(
allocateUnaligned(expandedSize_bytes));
// Calculate the adjustment by masking off the lower bits
// of the address, to determine how "misaligned" it is.
size_t mask = (alignment - 1);
uintptr_t misalignment = (rawAddress & mask);
ptrdiff_t adjustment = alignment - misalignment;
// Calculate the adjusted address.
uintptr_t alignedAddress = rawAddress + adjustment;
// Store the adjustment in the byte immediately
// preceding the adjusted address.
ASSERT(adjustment < 256);
//储存地址调整
U8* pAlignedMem = reinterpret_cast<U8*>(alignedAddress);
pAlignedMem[-1] = static_cast<U8>(adjustment);
return static_cast<void*>(pAlignedMem);
}
//allocateUnaligned()函数和相关的freeAligned / freeUnaligned()函数实现略
单帧/双缓冲内存分配器：
几乎所有游戏都会在游戏循环中分配一些临时数据。要么在本次循环结束时丢弃，要么在下一次循环结束时丢弃。称为单帧单帧分配器/双缓冲分配器。
- 单帧分配器
要实现单帧分配器，先预留一块内存，以简单堆栈分配器管理。在每帧开始时都把堆栈的顶端指针重置带内存块的底端地址。
单帧分配器优点是分配了的内存永不用手动释放，每帧开始时会自动清除所有内存。
注意单帧分配器的内存只在目前帧有效，绝不能跨帧使用。
- 双缓冲分配器
双缓冲分配器容许在第i帧分配的内存用于第(i+1)帧。实现方法时建立两个相同尺寸的单帧堆栈分配器，每帧交替使用。
伪代码：
class DoubleBufferAllocator
{
uint32_t m_curStack;
StackAllocator m_Stack[2];
public:
void swapBuffers(){
m_curStack = (uint32_t)!m_curStack;
}
void cleanCurrentBuffer(){
m_Stack[m_curStack].clear();
}
void * alloc(uint32_t mBytes){
return m_Stack[m_curStack].alloc(nBytes);
}
//...
}
//声明
DoubleBufferAllocator dba;
//游戏主循环
while(true){
//...
dba.swapBuffers();
dba.cleanCurrentBuffer();
//...
}
o 内存碎片
动态内存分配的另一个问题是内存碎片。当不断分配和释放堆内存，随着时间推移会产生很多内存碎片。
内存碎片问题是就算有足够的自由内存，分配请求依然可能失败。对于支持虚拟内存的操作系统来说，内存碎片不是大问题，但是由于其开销，很多游戏引擎不会使用虚拟内存。
使用堆栈分配器和池分配器避免内存碎片：
堆栈分配器完全避免了内存碎片，因为内存是连续的并且以反次序释放。
池分配器也没有内存碎片问题。虽然会产生物理上的内存碎片，但是它的内存块是一样大的，不会因为缺乏足够大的连续内存块而分配失败。
碎片整理和重定位：
如果要以随机次序来分配释放不同大小的内存，那么不适用于堆栈分配器和池分配器，可以对堆进行定期碎片整理。
碎片整理方法是把内存从高位移至地位，即所有的自由内存碎片被浮动到高位合并成一块连续空间。问题是移动了已分配内存块，指向这些内存的指针会失效，必须逐一重定位。遗憾的是C/C++不支持搜寻所有指向某地址范围的指针。
要在游戏引擎支持碎片整理，必须手动维护所有指针，在重定位时正确更新指针。
另一个选择是舍弃指针，使用智能指针(smart pointer)或者句柄(handle)。
- 智能指针是包含封装了一个指针的细小的类，它的实际行为几乎和普通指针完全相同。可以编写代码让所有智能指针把自己加进一个全局链表，要移动某块内存时，扫描链表更新指向该块内存的智能指针。
- 句柄通常实现为索引，索引指向句柄表内的元素，每个元素储存指针。移动某块内存时，扫描句柄表并自动修改相应的指针。
重定位的另一难题时有些内存块不能重定向，例如某些不使用智能指针或者句柄的第三方库。最好的办法是设置一个位于可重定向范围外的特别缓冲区。另一个可选选择是干脆容许一些内存块不能重定向，如果这种内存块数量少体积小，重定向系统仍可运行地很好。
分摊碎片整理成本：
碎片整理要复制内存块，所以操作过程可能很慢。可以把碎片整理分摊至多个帧来进行，每帧容许移动N次内存块。此方法一般只对细小内存块有效。
JasonGregory: 在顽皮狗的游戏引擎中这不是问题。因为重定向只用于游戏对象，而游戏对象通常很小，不会超过数千字节。
o CPU缓存 和 缓存一致性
CPU读写主内存的速度很缓慢，通常需要几千个周期。但是读写寄存器很快，通常需要数十个周期，有时甚至只需要1个周期。现代CPU都会采用高速缓存，CPU读写缓存的速度比主内存快得多。
当首次读取某块主内存时，该内存小块会载入高速缓存，称为缓存线(cache line)。再次读取内存时，如果数据已经在缓存中，则可以直接从缓存载入寄存器，比从内存读取快得多。只有请求的数据不在缓存中的时候才从内存存取，称为缓存命中失败(cache miss)。
写数据到内存时候。使用到的缓存写入设计有write-through-cache式缓存（数据写入缓存时会立即同时写入主内存）和write-back式缓存（不会立即写入主内存）。
※缓存一致性：
baike:高速缓冲存储器一致性（Cache coherence），也称缓存一致性，高速缓存间一致性。是指在采用层次结构存储系统的计算机系统中，保证高速缓冲存储器中数据与主存储器中数据相同机制。
baike:在一个系统中，当许多不同的设备共享一个共同存储器资源，在高速缓存中的数据不一致，就会产生问题。这个问题在有数个CPU的多处理机系统中特别容易出现。
一级缓存和二级缓存：
最开始的缓存位于主板上，并且容量很小。后来发展出了更快的缓存，直接置于CPU芯片上。这样就产生了两种缓存：CPU上的一级缓存(L1)和主板上的二级缓存(L2)。到后来L2缓存也移到了CPU芯片上。
多级缓存的出现使内存存取规则更为复杂，数据先从主内存到L2缓存，再从L2缓存到L1缓存，最后才到达CPU。存取速度主内存比L2慢，而L2又比L1慢。
有一种很差的缓存命中失败称为load-hit-store。即CPU在往内存地址写入数据后又读取该地址，此时要等待缓存写回数据至主内存，造成CPU流水线停顿。
指令缓存和数据缓存：
数据和代码都会置于缓存内。指令缓存(i-cache)会预载即将执行的机器码，而数据缓存(d-cache)用来加速数据读写。大多数处理器会在物理上分开两种缓存。
程序变慢可能是数据缓存命中失败，也可能是指令缓存命中失败。
避免数据缓存命中失败：
最好把数据放进连续的内存块中(避免经常在内存中跳来跳去)，并且顺序访问这些数据(避免在连续内存块中跳来跳去)，就可以把数据缓存命中失败降至最低。
避免指令缓存命中失败：
已知编译器和链接器的几条规律：
- 单个函数的机器码通常置于连续内存内，一般不会把一个函数分开在中间放另一个函数。（内联函数除外）
- 按照函数在编译单元源代码中的出现次序排列内存布局。
- 同一个翻译单元内的函数总是置于连续内存中，不会被分开然后插入其他编译单元的代码。
避免指令缓存命中失败：
- 高性能代码的体积(机器码指令数)越小越好。
- 性能关键代码段避免调用函数，若要调用函数，就把函数置于最接近调用函数的地方，最好是紧挨前后，不要把函数置于另一翻译单元。
- 审慎使用内联函数。内联小型函数能增进效能，然而过多的内联函数会增大代码体积使性能关键代码(特别是循环)不能完全装进缓存中。