通过合理组织数据利用CPU的缓存机制来加快内存访问速度。
动机
CPU的速度飞速增长，但RAM访问速度却增长迟缓。我们能更快地处理数据，但我们却不能更快地获取数据。为了使CPU进行大量的计算，实际上它需要从主存中取出数据并置入寄存器中。实际上，至今的CPU会花惊人的时间来等待内存。
当代计算机在其芯片内部的内存十分有限。CPU从芯片中读取数据的速度要快于它从主存中读取数据的速度。芯片内存很小，以便嵌入在芯片上，而且由于它使用了更快的内存类型（静态RAM或称“SRAM”），所以更加昂贵。这一小块内存被成为缓存。任何时候当芯片需要RAM中的数据时，它会自动将一整块连续的内存（通常在64到128字节之间）取出来并置入缓存中。这块内存被称为缓存线（cache line）。假如你需要的下一个数据恰巧在这个块中，那么CPU直接从缓存中读取数据，要比命中RAM快多了。成功地在缓存中找到数据被称为一次命中。假如它没有找到数据而需要访问主存，则称之为未命中。
当缓存未命中时，CPU就停止运转——它因为缺少数据而无法执行下一条指令。CPU进行着几百次的循环直到取得数据。我们的任务就是避免这一情况发生。
由于缓存机制的存在，你组织的数据会直接影响性能。代码也是在内存中的，而且需要被载入到CPU中才能够被执行。那些更精通于这课题的人能够为此写出一整本书来。（参考Richard Fabian的Data Oriented Design）
在单线程的基础上，这里只介绍一些基本的技巧。
这些都可以归结为一件简单的事情：不论芯片何时读取多少内存，它都整块地获取缓存线。你能够在缓存线中使用的数据越多，程序就跑得越快。所以优化的目标就是将你的数据结构进行组织，以使需要处理的数据对象在内存中两两相邻。
数据局部性模式
当代CPU带有多级缓存以提高内存访问速度。这一机制加快了对最近访问过的数据的邻近内存的访问速度。通过增加数据局部性并利用这一点可以提高性能——保持数据位于连续的内存中以供程序进行处理。
使用情境
如同多数优化措施，指导我们使用数据局部性模式的第一条准则就是找到出现性能问题的地方。不要在那些代码库里非频繁执行的部分浪费时间，它们不需要本模式。对那些非必要的代码进行优化将使你的人生变得艰难——因为结果总是更加复杂且笨拙。
由于此模式的特殊性，因此你可能还希望确定你的性能问题是否是由缓存未命中引起的，如果不是，那么这个模式也帮不上忙。
有现成的工具来做这些工作（例如Cachegrind）。在正是深入你的数据结构前，花些时间来运行这样一个工具并搞懂那些统计数据的含义（相当复杂！）是值得的。
由于你无法花费大量的时间预先对缓存的使用进行优化，因此是该想想在设计的过程中如何让你的数据结构变得对缓存更加友好。
使用须知
在Cpp中，使用接口则意味着要通过指针或引用来访问对象。而使用指针来进行访问也就是要在内存里来回地跳转，这就会引发本设计模式在极力规避的缓存未命中现象。
为了做到缓存友好，你可能需要牺牲一些之前所做的抽象化。你越是在程序的数据局部性上下工夫，你就越要牺牲继承、接口以及这些手段所带来的好处。这里并没有高招，只有利弊权衡的挑战。而乐趣便在这里。
示例代码
为了让你知道如何下手，我们会对几个最常见的组织数据的方法各做一个简单的实例。我们将在特定的游戏引擎环境下来完成它们，但要牢记，只要符合条件，这一技术在任何情境中都是通用的。
连续的数组
我们从处理一系列游戏实体的游戏循环开始，每个实体通过组件模式被拆解成不同的域：AI、物理、渲染。GameEntity类如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14class GameEntity
{
public:
GameEntity(AIComponent* ai, PhysicsComponent* physics, RenderComponent* render) :
ai_(ai), physics_(physics), render_(render) {}
AIComponent* ai() { return ai_; }
PhysicsComponent* physics() { return physics_; }
RenderComponent* render() { return render_; }
private:
AIComponent* ai_;
PhysicsComponent* physics_;
RenderComponent* render_;
};
每个组件都包含一些相对小量的状态，如一些向量或矩阵，且组件包含一个更新这些状态的方法。在此细节并不重要，我们可以根据这些粗略地设想出如下的组件结构：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class AIComponent
{
public:
void update() {
// Work with and modify state...
}
private:
// Goals,mood, etc...
};
class PhysicsComponent
{
public:
void update() {
// Work with and modify state...
}
private:
// Rigid body, velocity, mass, etc,...
};
class RenderComponent
{
public:
void update() {
// Work with and modify state...
}
private:
// Mesh, textures, shaders, etc ...
};
游戏维护着一个很大的指针数组，它们包含了对游戏世界中所有实体的引用。每次游戏循环我们需要做以下工作:
为所有实体更新AI组件。
为所有实体更新其物理组件。
使用渲染组件对它们进行渲染。
许多游戏实体将这样进行实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16while(!gameOver)
{
for(int i = 0; i < numEntities; i++)
{
entities[i]->ai()->update();
}
for(int i = 0; i < numEntities; i++)
{
entities[i]->physics()->update();
}
for(int i = 0; i < numEntities; i++)
{
entities[i]->render()->render();
}
// Other game loop machinery for timing...
}
在你耳闻CPU缓存机制之前，上面的代码看不出什么毛病。但现在，我想你已经察觉到有些不妥了。这样的代码不仅引起缓存抖动，甚至还将它来回搅成了一团浆糊。看看它都干了些啥吧：
数组存储着指向游戏实体的指针，因此对于数组中的每个元素而言，我们需要遍历这些指针（所指向的内存）——这就引发了缓存未命中。
然后游戏实体又维护着指向组件的指针。再一次缓存未命中。
接着我们更新组件。
现在我们回到步骤1，对游戏里每个实体的每个组件都这么干。
最可怕的是我们不知道这些对象在内存中的布局情况，完全任由内存管理器摆布。由于实体随着时间被分配、释放，因此堆空间会变得随即离散化。
让我们做一些改进吧。首先可以发现的是，我们追踪游戏实体的指针是为了找到这个实体内指向其组件的指针以便于访问这些组件。GameEnitity类本身并没有什么要紧的状态或者方法。游戏循环仅关心这些组件。
为了对这一堆游戏实体以及散乱在地址空间各个角落的组件做改进，我们将从头来过——我们构造一个容纳着各类组件的大数组——存放所有AI组件的一维数组，当然还有存放物理和渲染组件的数组，如下：1
2
3AIComponent* aiComponents = new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents = new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents = new RenderComponents[MAX_ENTITIES];
这里需要强调一下，这些是存储组件的数组而非组件指针的数组。数组里直接包含了所有组件的实际数据，这些数据在内存中逐个字节地进行分布。游戏循环可以直接遍历它们：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19while(!gameOver)
{
// Process AI.
for(int i = 0; i < numEntities; i++)
{
aiComponents[i].update();
}
// Update physics
for(int i = 0; i < numEntities; i++)
{
physicsComponents[i].update();
}
// Draw to screen.
for(int i = 0; i < numEntities; i++)
{
renderComponents[i].render();
}
// Other game loop machinery for timing...
}
我们抛弃了所有指针跟踪，直接对三个连续数组进行遍历来取代在内存中跳跃性的访问。这一方法往空闲的CPU中输入了一块连续的字节。在我的测试中，它为更新循环带来了比之前版本快50倍的速度。
有趣的是，我们这么做并没有放弃太多的封装性。每个组件依然具有自身的数据和方法。我们只是改变了使用它的方式而已。
这也并不意味着我们需要放弃GameEntity类。我们可以将它放在一边，并保持对组件指针的持有。它们只是指向这三个数组而已。
包装数据
假设我们在制作一个粒子系统。顺着上一部分的思路，我们将所有的粒子置入一个大的连续数组中。我们也将它封装成一个管理类来看看：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Particle
{
public:
void update() { /* Gravity, etc.... */ }
// Position, velocity, etc...
};
class ParticleSystem
{
public:
ParticleSystem() : numParticles_(0) {}
void update();
private:
static const int MAX_PARTICLES = 100000;
int numParticles_;
Particle particles_[MAX_PARTICLES];
};
void ParticleSystem:: update()
{
for(int i = 0; i < numParticles_; i++)
{
particles_[i].update();
}
}
但实际上我们并不需要总是更新所有的粒子。粒子系统维护一个固定大小的对象池，但它们并不总是同时被激活而在屏幕上闪烁。1
2
3
4
5
6
7for(int i = 0; i < numParticles_; i++)
{
if (particles_[i].isActive())
{
particles_[i].update();
}
}
懂得底层编程的人也许能看到更多的问题。为所有的粒子执行if判断会引发CPU的分支预测失准和流水线停顿。当代CPU中，单条指令实际上需要好几次时钟周期来完成。为了让CPU保持忙碌，指令被处理成流水线模式以便多条指令可以被并行地处理。
为实现流水线模式，CPU必须猜测哪些指令接下来将会被执行。在顺序结构的代码中这很简单，但在控制流结构中就很麻烦了。当它执行相关的if语句时，它该猜测粒子是处于激活状态继而其调用update()方法呢，还是猜测它未被激活而跳过它呢？
为了回答这个问题，芯片就进行分支预测——它分析前一次你的代码走向，然后猜测这次也该这么做。但要是这些粒子按顺序一个激活一个未激活穿插地排列，那么预测就总是会失败。
当预测失败时，CPU要对先前投机执行的指令进行撤销（流水线清理）并重新执行正确的指令，这样的性能损耗在计算机运转过程中是很常见的，而这也是为什么你有时会看到开发者们在关键代码中避开控制流语句的原因。
从代码我们可以知道，假如粒子并未被激活，那么我们就跳向下一个。这时将该粒子的其他数据加载到缓存中就是一种浪费。
活跃的粒子越少，我们就越多次地在内存中跳转。假如粒子数组太大而活跃的粒子又太少，我们又会抖动缓存。
当我们实际处理的对象并不连续时，将对象存入连续的数组，这个办法就无效了。假如为了这些非活跃的粒子而要在内存中跳来跳去，那么我们就回到了问题的起点。
再看看这小节的标题，我想你可能已经猜到了答案。我们将根据这个标志对粒子进行排序，而不是去判断这些标志。我们总是将那些被激活的粒子维持在列表的前端。假如我们知道它们都处于激活状态，就根本不必去检测标志了。
我们也可以跟踪被激活粒子的数目。这样我们就可以美化一下代码了：1
2
3
4for(int i = 0; i < numActive_; i++)
{
particles[i].update();
}
现在我们不略过任何数据。每次塞进缓存的粒子都是被激活的，也都正是我们要处理的。
当然我可没说你得在每帧对整个粒子集合进行快速排序，这样得不偿失。我们希望时刻保持数组有序。
假设数组已经排好序——并且一开始所有的粒子都处于非激活状态。数组仅当每个粒子被激活或者反激活时处于乱序状态。我们很容易就能对这两种情况来进行处理：当粒子被激活时，我们通过把它与数组中第一个未激活的粒子进行交换来将其移动到所有激活粒子的末端：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26void ParticleSystem::activeParticle(int index)
{
// Shouldn't aleady be active!
assert(index >= numActive_);
// Swap it with the first inacive particle right
// after the active ones.
Particle temp = particles_[numActive_];
particles_[numActive_] = particles_[index];
particles_[index] = temp;
numActive++;
}
void ParticleSystem::deactivateParticle(int index)
{
// Shouldn't aleady be inactive!
assert(index < numActive_);
numActive_--;
// Swap it with the last active particle right
// before the inactive ones.
Particle temp = particles_[numAcitve_];
particles_[numActive_] = particles_[index];
particles_[index] = temp;
}
许多程序员都厌恶在内存中移动数据。把内存里的字节移来移去让人觉得比为指针分配内存开销更大。但当你再加上遍历指针的开销时，会发现我们的直觉有时会失灵。在某些情况下，假如你能保持缓存数据盈满，在内存中移动数据的开销是很小的。
结论就是，我们可以保持粒子依照其激活状态有序排列，而无需保存激活状态本身。这可以通过粒子在数组中的位置和numActive_计数器来确定。这使得我们的粒子结构变小，也就意味着缓存线上能够存储更多数据，从而提高速度。
当然并非完事都能称心如意，我们在此放弃了许多面向对象的思想。Particle类不再控制其自身的状态，你也无法对粒子对象调用诸如activate()之类的方法。
热/冷分解
这是最后一个帮助你将代码变得缓存友好的技术案例。假设我们为某个游戏实体配置了AI组件，其中包含了一些状态：它当前所播放的动画，它当前所走向的目标位置、能量值等，总之这些是它在每帧都要检查和修改的变量。1
2
3
4
5
6
7
8
9class AIComponent
{
public:
void update() { /* ... */ }
private:
Animation* animation_;
double energy_;
Vector goalPos_;
};
而它还存储着一些并非每帧都用到的处理意外的变量。比如存储一些关于当这家伙被开枪打死后掉落宝物的数据。掉落数据仅仅在实体的生命周期结束时才调用，我们将其置于上面的那些状态属性之后：1
2
3
4
5
6
7
8
9
10
11class AIComponent
{
public:
void update() { /* ... */ }
private:
// Previous fields...
LootType drop_;
int minDrops_;
int maxDrops_;
double chanceOfDrop_;
};
假设我们采用前述方法，当更新这些AI组件时，我们遍历一个已经包装好且连续的数组中的数据。然而这些数据中包含着所有的掉落信息。这使得每个组件都变得更庞大，也就导致我们在一条缓存线上能放入的组件更少。我们将引发更多的缓存未命中，因为我们遍历的总内存增加了。对每帧的每个组件，其掉落物品的数据都要被置入缓存，尽管我们根本不会去碰它们。
对此问题的解决办法我们称之为“热/冷分解”。其思路是将我们的数据结构划分为两部分。第一个部分为“热数据”，也就是我们每帧需要用到的数据，另一个部分为“冷数据”，也就是那些并不会被频繁用到的剩余数据。
这里我们的热数据主要是AI组件。它是我们处理的关键，所以我们不希望通过指针来访问它。冷组件可以放到一边，但我们还是需要访问它，所以就为它分配一个指针，如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class AIComponent
{
public:
// Methods...
private:
Animation* animation_;
double energy_;
Vector goalPos_;
LootDrop* loot_;
};
class LootDrop
{
friend class AIComponent;
LootType drop_;
int minDrops_;
int maxDrops_;
double chanceOfDrop_;
};
可以通过维护两个平行的数组分别存放冷热数据，来抛弃这个指针，接着我们可以让两个数组中同一组件的索引保持一致，以便通过热数据数组的索引来访问对应的冷数据。
现在当我们每帧遍历AI组件时，载入到缓存中的那些数据就是我们实际要处理的了（指向冷数据的指针是例外）。
设计决策
这种设计模式更适合叫一种思维模式。它提醒着你，数据的组织方式是游戏性能的一个关键部分。这一块的实际拓展空间很大，你可以让你的数据局部性影响到游戏的整个架构，又或者它只是应用在一些核心的数据结构上。
(Noel Llopis在他的著作中称此为“面向数据的设计模式”，这让很多人开始思考如何在游戏中利用缓存。)
对这一模式的应用，你最需要关心的就是该何时何地地使用它。而随着这个问题我们也会看到一些新的顾虑。
你如何处理多态
我们此前避开了子类继承和虚方法，并假设我们已经将同质的对象都很好地置入了数组，此时我们知道它们每个的尺寸都一样大。然而多态和方法的调用也是非常有用的工具，我们如何在二者之间进行协调？
避开继承
最简单的方法就是避开子类化，或者说至少在你进行缓存优化的地方避开继承。软件工程中也较为排斥重度的继承。
- 安全而容易。你知道自己正在处理什么类，而且显然所有的对象其大小都是一样的。
- 速度更快。方法的动态调用意味着在vtable中寻找实际需要调用的方法，并通过指针来访问实际代码，由于此操作在不同硬件平台呈现很大的性能差异，故动态调用意味着一些开销。（凡事没有绝对，在许多情况下，cpp编译器需要使用间接引用来调用一个虚函数。但在某些情况下，当编译器知道调用者的确切类型时，它会进行非虚拟化来调用正确的方法。非虚拟化在诸如java和JavaScript这类实时编译语言中更为常见。）
- 灵活性差。当然，我们使用动态调用的原因正是在于它能够给予我们强大的对象多态能力，让对象表现出不同的行为。假如你希望游戏中的不同实体拥有各自的渲染风格或者特殊的移动与攻击等表现，那么虚方法正是为此而准备的。若想要避免使用虚方法而做到这一点，那么你可能需要维护一个庞大的switch逻辑块，并很快陷入混乱。
为不同的对象类型使用相互独立的数组
我们使用多态来实现在对象类型未知的情况下调用其行为。换句话说，我们有个装着一堆对象的包，我们需要当一声令下时他们能够各做各的事情。
但这带来的问题时，为什么要从一个龙蛇混杂的背包开始，而不是维护一系列按照类型分放的集合呢？
- 这样的一系列集合让对象紧密地封包。由于每个数组仅包含一个类型的对象，也就不存在填充或者其他古怪了。
- 你可以进行静态地调用分发。你能按照类型将对象划分，也不不再需要多态了。你可以进行常规的、非虚方法调用。
- 你必须时刻追踪这些集合。假如你有许多不同类型的对象，那么维护单独数组集合的开销将是件苦差事。
- 你必须注意每一个类型，由于你要维护每个类型的对象集合，因此无法从这些类型中解耦它们，多态的一个神奇作用就在于它是可扩展的，通过使用接口来进行外部操作，多态将调用这些接口的代码从潜在的那些类型（它们均实现这一接口）中完全地解耦出来。
使用指针集合
假如你不担心缓存，那么这自然是个好办法。你只需维护一个指向基类或接口的指针数组。你可以很好地利用多态性，而且对象的大小也无须一致。
- 这样做灵活性高。只要能适配接口，访问这个集合的代码就能够处理你关心的任何类型的对象。这完全是可扩展的。
- 这样做并不缓存友好。我们在此讨论其他方案的原因就在于解决这样指针间接访问数据的缓存不友好局面。然而请记住，如果这些代码对性能并不苛求，那么使用多态是完全没问题的。
游戏实体是如何定义的
游戏循环直接对组件数组进行迭代，也就是说实体本身是不重要的，当然在游戏的其他模块你还是可能会需要这些概念性的实体。接下来的问题是该如何表现？实体如何跟踪自己的组件？
假如游戏实体通过类中的指针来索引其组件
我们的第一个例子看起来就是如此。这是相对普通的面向对象的办法。你有一个GameEntity类，而它内部有指向其组件的指针。由于它们只是指针，估它们并不知道那些组件在内存中的确切或者它们是如何组织的。
- 你可以将组件存于相邻的数组中。由于游戏并不关心组件的存储，因此你可以将它们组织到一个封包过的数组中来对迭代过程进行优化。
- 对于给定实体，你可以很容易地获取它的组件。只需通过指针访问即可。
- 在内存中移动组件很困难。当组件被启用或禁用时，你可能会希望将这些组件进行移动以保存那些激活的组件总排在数组的前端并彼此相邻。假如你移动一个与实体通过原始指针关联的组件，则可能一不小心破坏了这一指针关联。你必须确保同时对实体的相应指针进行更新。
假如游戏实体通过一系列ID来索引其组件
你可以使用更抽象的表示来取代指针：一个能够检测到指定组件的ID或索引。
ID的实际语义以及索引的过程完全取决于你。可能是简单地为每个组件存储一个唯一ID并进行数组遍历，也可能是在一个哈西表上将ID对组件所在的数组索引进行映射。
- 这更加复杂。 你的ID系统也许无需过度复杂，但总得比直接使用指针要麻烦。你需要实现并调试它，当然用ID记录也需要额外的内存空间。
- 这样做更慢。要想比遍历原始指针速度更快是很难的。通过实体获取其组件的过程将涉及到哈希查找等问题。
- 你需要访问组件管理器。最简单的想法就是用一些抽象的ID来定义组件。你可以通过它来获取实际的组件对象。但为了做到正确索引，你必须让这些ID有办法对应到组件上。这也正是存储你组件数组的那个管理类所要做的。
使用原始指针，假如你有一个游戏实体，你就可以找到其组件。而使用ID的方法，你则需要同时对游戏实体和组件进行注册。
假如游戏实体本身就只是个ID
这是一些新的游戏引擎所采用的风格。一旦你游戏实体的所有行为和状态从主类移动到组件中，那么游戏实体还剩什么呢？结果是剩不了什么，游戏实体唯一做得就是将自己与其组件绑定。它的存在就意味着其AI、物理、渲染组件构成了这个游戏世界中的实体。
这一点很重要，因为组件之间要进行交互。渲染组件需要知道实体位于何处，而这个位置信息就很可能位于其物理组件中。AI希望移动实体，于是它需要对物理组件施加一个力。在一个实体内，需要为每个组件提供一个访问其兄弟组件的办法。
某些聪明人意识到我们所需要的就是个ID。这使得组件能知道它所属的实体是哪个，而不是让实体来确定其组件位置。当AI组件需要其同属实体的物理组件时，它只需访问与自身相同实体ID的那个物理组件即可。
- 你的游戏实体类完全消失了，取而代之的是一个优雅的数值包装。实体变得很小。当你需要传入一个实体的引用时，你只需传入一个数值。
- 实体类本身是空难的。当然这一个方法的弊端是你必须把所有东西都扫出游戏实体。你不再有地方来存放那些非组件构成的实体状态和行为。这样做更加依赖于组件模式。
- 你无须管理其生命周期。由于现在实体只是某些内置类型的值，因此它们无需进行显式的分配或释放。实际上当某个实体的所有组件都销毁时，这个实体也就随之隐式地“消亡了”。
- 检索一个实体的所有组件会很慢。这与前一个方案的问题很类似，但处于相反的一面。为某个实体寻找其组件，你需要一个对象进行ID映射，这个过程会带来开销。
这一次性能方面也存在问题。组件在更新过程中频繁与其兄弟组件交互，于是你需要频繁地检索组件。一个解决方法是将实体的ID对应为其组件所在数组的索引。
假如所有的实体都包含相同的组件集，那么你的组件数组之间是完全平行的。AI组件数组中的第三个组件将与物理组件中的第三个组件对应着同一个实体。
请牢记，这个办法迫使你保持这些数组平行。当你希望对数组进行排序或者按照某种规则进行封包时就很难做到平行了，你的某些实体可能禁用了物理引擎，而其他的实体不可见。在保持他们平行的情况下，你无法兼顾物理组件和渲染组件来同时满足这两种情况。