Chapter 17 数据局部性
通过合理组织数据利用CPU缓存机制来加快内存访问速度。
数据局部性:多级缓存加快了最近访问过的数据的邻近内存的访问速度,保持数据位于连续的内存中可以提高性能。
找到出现性能问题的地方,不要把时间浪费在非频繁执行的代码上。
为了做到缓存友好,可能会牺牲继承、接口等这些手段带来的好处。
连续数组:
1 AIComponent* aiComponents =
2 new AIComponent[MAX_ENTITIES];
3 PhysicsComponent* physicsComponents =
4 new PhysicsComponent[MAX_ENTITIES];
5 RenderComponent* renderComponents =
6 new RenderComponent[MAX_ENTITIES];
7
8 while (!gameOver)
9 {
10 // Process AI.
11 for (int i = 0; i < numEntities; i++)
12 {
13 aiComponents[i].update();
14 }
15
16 // Update physics.
17 for (int i = 0; i < numEntities; i++)
18 {
19 physicsComponents[i].update();
20 }
21
22 // Draw to screen.
23 for (int i = 0; i < numEntities; i++)
24 {
25 renderComponents[i].render();
26 }
27
28 // Other game loop machinery for timing...
29
30 }
相比GameEntity里几个指针指向对应component的方案,这个方案提高了每帧执行游戏循环时的缓存命中。
包装数据:
1 void ParticleSystem::update()
2 {
3 for (int i = 0; i < numParticles_; i++)
4 {
5 if (particles_[i].isActive())
6 {
7 particles_[i].update();
8 }
9 }
10 }
更新所有粒子,之前的判断引发CPU预测失准和流水线停顿。
解决方案是跟踪被激活粒子的数目:
- 当粒子被激活时将它与第一个未激活粒子交换位置;
- 当粒子被灭时将它与最后那个激活的粒子交换位置。
1 for (int i = 0; i < numActive_; i++)
2 {
3 particles[i].update();
4 }
5
6
7 void ParticleSystem::activateParticle(int index)
8 {
9 // Shouldn't already be active!
10 assert(index >= numActive_);
11
12 // Swap it with the first inactive particle
13 // right after the active ones.
14 Particle temp = particles_[numActive_];
15 particles_[numActive_] = particles_[index];
16 particles_[index] = temp;
17
18 // Now there's one more.
19 numActive_++;
20
21 }
22
23 void ParticleSystem::deactivateParticle(int index)
24 {
25 // Shouldn't already be inactive!
26 assert(index < numActive_);
27
28 // There's one fewer.
29 numActive_--;
30
31 // Swap it with the last active particle
32 // right before the inactive ones.
33 Particle temp = particles_[numActive_];
34 particles_[numActive_] = particles_[index];
35 particles_[index] = temp;
36
37 }
冷热分解:
将数据结构分解为冷热两部分:
- 热数据 每帧需要用到的数据;
- 冷数据 不会被频繁使用的数据(分配一个指针塞下)
1 class AIComponent
2 {
3
4 public:
5 // Methods...
6
7 private:
8 Animation* animation_;
9 double energy_;
10 Vector goalPos_;
11
12 LootDrop* loot_;
13
14 };
15
16 class LootDrop
17 {
18 friend class AIComponent;
19
20 LootType drop_;
21 int minDrops_;
22 int maxDrops_;
23 double chanceOfDrop_;
24
25 };
Chapter 18 脏标记模式
将工作推迟到必要时进行以避免不必要的工作。
衍生数据由原始数据经过一些代价高昂的操作确定。用一个脏标记跟踪衍生数据是否与原始数据同步,同步时使用缓存数据,不同步时则重新计算衍生数据并清除标记。
脏标记模式增加了代码复杂性:
- 用代码复杂性换取性能的优化;
- 太慢的计算不行,如一帧内处理不完的;
- 必须保证每次状态改动都设置标记(单一API封装)。
Example:
矩阵计算
1 class Transform
2 {
3
4 public:
5 static Transform origin();
6
7 Transform combine(Transform& other);
8
9 };
GraphNode(初始化dirty_为true)
1 class GraphNode
2 {
3
4 public:
5 GraphNode(Mesh* mesh)
6 : mesh_(mesh),
7 local_(Transform::origin()),
8 dirty_(true)
9 {}
10
11 void renderMesh(Mesh* mesh, Transform transform);
12
13 // Other methods...
14
15 private:
16 Transform world_;
17 bool dirty_;
18
19 Transform local_;
20 Mesh* mesh_;
21
22 GraphNode* children_[MAX_CHILDREN];
23 int numChildren_;
24
25 };
设置Transform并设置dirty
1 void GraphNode::setTransform(Transform local)
2 {
3 local_ = local;
4 dirty_ = true;
5 }
渲染:
1 void GraphNode::render(T