《游戏引擎架构》阅读笔记 第二部分第5章

• 本系列博客为《游戏引擎架构》一书的阅读笔记，旨在精炼相关内容知识点，记录笔记，以及根据目前（2022年）的行业技术制作相关补充总结。
• 本书籍无硬性阅读门槛，但推荐拥有一定线性代数，高等数学以及编程基础，最好为制作过完整的小型游戏demo再来阅读。
• 本系列博客会记录知识点在书中出现的具体位置。并约定（Pa b），其中a为书籍中的页数，b为从上往下数的段落号，如有lastb字样则为从下往上数第b段。
• 本系列博客会约定用【】来区别本人所书写的与书中观点不一致或者未提及的观点，该部分观点受限于个人以及当前时代的视角所限，请谨慎阅读。
• 再次重申，请支持正版。

目录

• 第5章 游戏支持系统
  • 5.1 子系统的启动和终止
  • 5.2 内存管理
  • 5.3 容器
  • 5.4 字符串
  • 5.5 引擎配置

第5章 游戏支持系统

5.1 子系统的启动和终止

• 游戏引擎是复杂软件，由多个互相合作的子系统结合而成。当引擎启动时，必须依次配置及初始化每个子系统。各子系统间的相互依赖关系，隐含地定义了每个子系统所需的启动次序。例如子系统B依赖子系统A，那么在启动B之前，必须先启动A。各子系统的终止通常会采用反向次序，即先终止B，再终止A。(P185 1)

5.2 内存管理

• 内存对效能的影响有两方面：1、动态分配内存。要提升效能，最佳方法是尽量避免动态分配内存，不然也可利用自制的内存分配器来大大减低分配成本。 2、许多时候在现代的CPU上，软件的效能受其内存访问模式(memory access pattern)主宰。我们将看到，把数据置于细小连续的内存块，相比把数据分散至广阔的内存地址，CPU对前者的操作会高效得多。就算采用最高效的算法，并且极小心地编码，若其操作的数据并非高效地编排于内存中，算法的效能也会被搞垮。（P193 1）
• 优化动态内存分配：维持最低限度的堆分配，并且永不在紧凑循环中使用堆分配。 当然，任何游戏引擎都无法完全避免动态内存分配，所以多数游戏引擎会实现一个或多个定制分配器(custom allocator)。定制分配器能享有比操作系统分配器更优的性能特征，原因有二。第一，定制分配器从预分配的内存中完成分配请求（预分配的内存来自malloc ( )、new，或声明为全局变量)。这样，分配过程都在用户模式下执行，完全避免了进入操作系统的上下文切换。第二，通过对定制分配器的使用模式(usage pattern）做出多个假设，定制分配器便可以比通用的堆分配器高效得多。（P194 1）
• 基于堆栈的分配器：许多游戏会以堆栈般的形式分配内存。当载入游戏关卡时，就会为关卡分配内存;关卡载入后，就会很少甚至不会动态分配内存。在玩家完成关卡之际，关卡的数据会被卸下，所有关卡占用的内存也可被释放。对于这类内存分配，非常适合采用堆栈形式的数据结构。（P194 3） 必须注意，使用堆栈分配器时，不能以任意次序释放内存，必须以分配时相反的次序释放内存。有一个方法可简单地实施此限制，这就是完全不容许释放个别的内存块。取而代之，我们提供一个函数，该函数可以把堆栈顶端指针回滚至之前标记了的位置，那么其实际上的意义就是，释放从回滚点至目前堆栈顶端之间的所有内存。（P194 4）
• 池分配器：在游戏引擎编程（及普遍的软件工程）中，常会分配大量同等尺寸的小块内存。例如,我们可能要分配及释放矩阵、迭代器（iterator)、链表中的节点、可渲染的网格实例等。池分配器（pool allocator)是此类分配模式的完美选择。 池分配器的工作方式如下。首先，池分配器会预分配一大块内存，其大小刚好是分配元素的倍数。例如，4×4矩阵池的大小设为64字节的倍数（每矩阵16个元素，再乘以每元素4字节)。池内每个元素会加到一个存放自由元素的链表;换句话说，在对池进行初始化时，自由列表（free list）包含所有元素。池分配器收到分配请求时，就会把自由链表的下一个元素取出，并传回该元素。释放元素之时，只需简单地把元素插回自由链表中。分配和释放都是O(1)的操作。这是因为无论池内有多少个元素，每个操作都只需几个指针运算。（P196 3）
• 含对其功能的分配器：每个变量和数据对象都有对齐要求。8位整数可对齐至任何地址，32位整数或浮点变量则必须4字节对齐，128位SIMD矢量值通常需要16字节对齐。（P197 3）
• 单帧和双缓冲内存分配器：几乎所有游戏都会在游戏循环中分配一些临时用数据。这些数据要么可在循环迭代结束时丢弃，要么可在下一迭代结束时丢弃。很多游戏引擎都支持这两种分配模式，分别称为单帧分配器(single-frame allocator）和双缓冲分配器（double-buffered allocator )。（P199 last） 单帧分配器的主要益处是，分配了的内存永不用手动释放，我们依赖于每帧开始时分器会自动清除所有内存。单帧分配器也极其高效。然而，单帧分配器的最大缺点在于，程员必须有不错的自制能力。程序员需要意识到，从单帧分配器分配的内存块只在目前的书有效。程序员绝不能把指向单帧内存块的指针跨帧使用!
• 动态堆分配的另一问题在于，会随时间产生内存碎片(memory fragmentation)。（P201 last）

图片 - 《游戏引擎架构》阅读笔记 第二部分第5章

• 使用堆栈和/或池分配器，可以避免一些内存碎片带来的问题。堆栈分配器完全避免了内存碎片的产生。这是由于，用堆栈分配器分配到的内存块总是连续的，并且内存块必然以反向次序释放。 池分配器也无内存碎片问题。虽然实际上池会产生碎片，但这些碎片不会像一般的提前引发内存不足的情况。向池分配器做分配请求时，不会因缺乏足够大的连续内块，而造成分配失败，因为池内所有内存块是完全一样大的。（P203 1）

图片 1 - 《游戏引擎架构》阅读笔记 第二部分第5章

• 碎片整理及重定位我们移动了已分配的内存块，若有指针指向这些内存块，移动内存便会使这些指针失效。因此程序员要手动维护指针，在重定位时正确更新指针;另一个选择是，舍弃指针，取而代之，使用更容易重定位时修改的构件，例如智能指针(smart pointer）或句柄(handle)。（P203 last） 分摊碎片整理成本：因为碎片整理要复制内存块，所以其操作过程可能很慢。然而，我们无须一次性把碎片完全整理。取而代之，我们可以把碎片整理成本分摊（amortize）至多个帧。我们容许每帧进行多达N次内存块移动，N是个小数目，如8或16。若游戏以每秒30帧运行，那么每帧会持续1/30s (33ms)。这样，堆通常能在少于1s内完全整理所有碎片，而不会对游戏帧率产生明显影响7。只要分配及释放的次数低于碎片整理的移动次数，那么堆就会经常保持接近完全整理的状态。（P205）
• 要了解内存存取模式为何影响效能，我们须先了解现代处理器如何读/写内存。存取主系统内存是缓慢的操作，通常需要几千个处理器周期才能完成。和CPU里的寄存器相比,存取寄存器只需数十个周期，甚至有时只需要一个周期。为了降低读/写主内存的平均时间，现代处理器会采用高速的内存缓存（ cache)。 缓存是一种特殊的内存，CPU读/写缓存的速度比主内存快得多。内存缓存的基本概念是这样的，当首次读取某区域的主内存，该内存小块会载入高速缓存。这个内存块单位称为缓存线(cache line)，缓存线通常介乎8至512字节，具体值视微处理器架构而定。若后来再读取内存，而该数据已在缓存中，那么数据就可以直接从缓存载入寄存器，这比读取主内存快得多。仅当要求的数据不在缓存中，才必须存取主内存。这种情况名为缓存命中失败( cache miss）。每当出现缓存命中失败，程序便要被逼暂停，等待缓存线自主内存更新后才能继续运行。（P205 3）
• 一、二级缓存：缓存直接置于CPU芯片上。产生了两种缓存:在CPU芯片上的一级(level 1，Ll)缓存、在主板上的二级（level 2，L2）缓存。（P206 2） 【三级缓存：传送门】
• 指令缓存和数据缓存：指令缓存(instruction cache，I-cache）会预载即将执行的机器码，而数据缓存(data cache，D-cache）则用来加速自主内存读/写数据。大多数处理器会在物理上独立分开这两种缓存。因此，程序变慢，有可能因为指令缓存命中失败，或是数据缓存命中失败。（P206 last）
• 避免缓存命中失败：避免数据缓存命中失败的最佳办法就是，把数据编排进连续的内存块中，尺寸越小越好，并且要顺序访问这些数据。这样便可以把数据缓存命中失败的次数减至最少。当数据是连续的(即不会经常在内存中“跳来跳去”)，那么单次命中失败便会把尽可能最多的相关数据载入单个缓存线。若数据量少，更有可能塞进单个缓存线(或最少数量的缓存线)。并且，当顺序存取数据时（即不会在连续的内存块中“跳来跳去”)，便能造成最少次缓存命中失败，因为CPU不需要把相同区域的内存重载入缓存线。 链接器通用规则：1、单个函数的机器码几乎总是置于连续的内存。绝大多数情况下，链接器不会把一个函数切开，并在中间放置另一个函数。(内联函数除外，这点之后再解释。) 2、编译器和链接器按函数在翻译单元源代码（.cpp文件）中的出现次序排列内存布局。因此，位于一个翻译单元内的函数总是置于连续内存中。即链接器永不会把已编译的翻译单元切开，中间加插其他翻译单元的代码。
• 解决方案：1、高效能代码的体积越小越好，体积以机器码指令数目为单位。(编译器和链接器会负责把函数置于连续内存。) 2、在性能关键的代码段落中，避免调用函数。3、若要调用某函数，就把该函数置于最接近调用函数的地方，最好是紧接调用函数的前后，而不要把该函数置于另一翻译单元（因为这样会完全无法控制两个函数的距离)。3、审慎地使用内联函数。内联小型函数能增进效能。然而过多的内联会增大代码体积,使性能关键代码再不能完全装进缓存。假设有一个处理大量数据的紧凑循环，若循环内的代码不能完全装进缓存，每个循环迭代便会产生至少两次指令缓存命中失败。遇到这种情况，最好重新思考算法及其代码实现，看看能否减少关键循环中的代码量。（P207）

5.3 容器

• 游戏程序员使用各式各样的集合型数据结构，也称为容器（container）或集合( collection)。各种容器的任务都一样——安置及管理0至多个数据元素。然而，细节上各种容器的运作方式有很大差异，每种容器也各有优缺点。常见的容器数据类型包括但肯定不限于以下所列：数组、动态数组、链表、堆栈、队列、双端队列、优先队列、树、二叉查找树、二叉堆、字典、集合（容器无重复元素）、图、有向非循环图。（P208 1）
• 二叉查找树(binary search tree，BST):二叉查找树中的每个节点最多含两个子节点。由于节点按预先定义的方式排列，任何时候都可以按该排列方式遍历整棵树。二叉查找树有多种类型，包括红黑树（red-black tree)、伸展树（splay tree)、AVL树(AVL tree）。 二叉堆(binary heap):采用完全（或接近完全）二叉树的数据结构，通常使用（静态或动态）数组储存。根节点必然是堆中最大(或最小）的元素。二叉堆一般用来实现优先队列。
• 容器操作：插入、移除、顺序访问/迭代、随机访问、查找、排序。
• 迭代器：迭代器是一种细小的类，它“知道”如何高效地访问某类容器中的元素。迭代器像是数组索引或指针—每次它都会指向容器中某个元素，可以移至下一个元素，并能用某方式表示是否已访问容器中所有元素。（P219 last）
• 算法复杂度：P211
• 链表：P216
• 字典和散列表：P222

5.4 字符串

• 字符串使用问题：1、如何存储和管理字符串 2、字符串的本地化（P255）
• 字符串散列标识符：把字符串散列(hash）是好方案。散列函数能把字符串映射至半唯一整数。字符串散列码能如整数般比较，因此其比较操作很迅速。若把实际的字符串存于散列表，那么就可以凭散列码取回原来的字符串。这在调试时非常有用，并且可以把字符串显示在屏幕上或写入日志文件中。游戏程序员常使用字符串标识符(string id)一词指这种散列字符串。（P277 last2） 方法：1、把每个SID（任何字符串）的宏直接翻译为相对的散列值。

5.5 引擎配置

• 读/写选项：可配置选项可简单实现为全局变量或单例中的成员变量。然而，可配置选项必须供用户配置，并储存至硬盘、记忆卡(memory card）或其他储存媒体，使往后游戏能重读这些选项，否则这些配置选项的用途不大。以下是一些简单读/写可配置选项的方法:1、本地配置文件 2、经压缩二进制文件 3、Windows注册表 4、命令行选项 5、环境变量 6、线上用户设定档