数据局部性

意图

利用 CPU 缓存，通过合理安排数据来加速内存访问。（Game Programming Patterns — data-locality）

机制

现代 CPU 用缓存加速内存访问，访问刚访问过的内存附近会快得多。利用这一点的办法是提高数据局部性：把数据按处理顺序放在连续内存里。（Game Programming Patterns — data-locality）

CPU 从内存读一个字节时，会自动取回一整块相邻内存（通常 64 到 128 字节），放进缓存，这一块叫缓存行 (cache line)。下一个要用的字节恰好在这块里就是缓存命中，否则是缓存未命中，要等主存。（Game Programming Patterns — data-locality）

动机部分的要点（Game Programming Patterns — data-locality）：

• CPU 越来越快，RAM 却远远跟不上，从 RAM 取一个字节可能要数百个周期。作者用仓库作比喻：会计（CPU）一分钟处理完一箱文件，仓库管理员（总线）却要一整天才送来一箱；改为每次把整托盘相邻的箱子都运来放在办公室角落（缓存），下一箱恰好在托盘上就只要一秒。
• 一次缓存未命中相当于在循环里插了一个 sleepFor500Cycles()。作者写了两个计算完全相同、只是缓存未命中次数不同的程序，慢的那个慢了五十倍。由此得出：数据的组织方式直接影响性能，性能不只是代码的属性。
• 隐含前提是单线程：多个线程修改相邻数据时，反而应该让它们落在不同缓存行上，否则多个核要为同一缓存行做昂贵的同步。

书中的三个手段（Game Programming Patterns — data-locality）：

1. 连续数组代替指针追逐：原来是一组 GameEntity*，每个实体再用指针指向自己的 AI、物理、渲染组件，更新时在内存里到处跳。改成三个分别存放 AI、物理、渲染组件的连续数组，游戏循环直接顺序遍历。作者测试中，这一改动让更新循环快了五十倍。封装其实没丢多少：每个组件仍然拥有自己的数据和方法；GameEntity 也可以保留，它的指针只是改为指向这些数组，供需要传递“概念上的实体”的代码使用，只是性能关键的循环绕过它直接访问数据。一个提示：新代码里的 -> 少多了，想提高局部性就找可以去掉的间接访问。
2. 打包数据 (packed data)：粒子系统里，让活跃粒子始终排在数组前部，循环只遍历前 numActive_ 个；激活时与第一个非活跃粒子交换，停用时与最后一个活跃粒子交换，从而保持有序，而不是每帧排序。对比逐个检查 isActive() 的写法：每次检查都把整个粒子拉进缓存，非活跃的就白载入了，还可能引起分支预测失败和流水线冲刷。保持有序还有个好处：粒子里不再需要活跃标志，对象更小，一条缓存行装得更多。代价是失去一点面向对象：Particle 不知道自己的下标，无法自己 activate()，必须通过 ParticleSystem；作者认为二者本就是分在两个类里的同一个概念。直觉上移动内存比赋值指针“重”，但算上跟随指针的开销，有时移动反而更便宜（仍要先做性能分析）。ParticleSystem 本身也是为单一类型定制的 对象池。
3. 冷热分离 (hot/cold splitting)：AI 组件里每帧都要用的数据（当前动画、目标位置、能量）是“热”的，掉落物数据很少用，是“冷”的。把冷数据拆到旁边单独存放，热组件里只留一个指向它的指针，这样每帧载入缓存的都是有用的字节（除了那一个指针；也可以用热、冷两个并行数组按相同下标对应，连指针都省掉）。

下图对比两种布局：左边每个实体要跟随指针去找分散在堆上的组件，右边同类组件连续存放，循环顺序读取。

flowchart LR
  subgraph "指针追逐"
    E1[Entity 1] --> a1[AI*] & p1[Physics*]
    E2[Entity 2] --> a2[AI*] & p2[Physics*]
  end
  subgraph "连续数组"
    AA["AI 数组：AI1 AI2 AI3 …"]
    PA["Physics 数组：P1 P2 P3 …"]
  end

右边的布局让每次缓存行载入都带来下几个要处理的对象，左边则几乎每次访问都可能未命中。

何时使用

和多数优化一样，先确认有性能问题，并且问题确实由缓存未命中引起，否则没有帮助；优化不需要优化的代码只会让结果更复杂、更不灵活。简单的计时插桩看不出缓存问题，需要能报告缓存未命中次数和位置的性能分析器（免费选项如 Cachegrind，它在模拟的 CPU 与缓存层次上运行程序）。尽管不该过早花大量时间做缓存优化，在整个设计过程中仍要想着数据结构是否缓存友好。（Game Programming Patterns — data-locality）

取舍与坑

• 抽象的代价：C++ 里用接口就意味着通过指针或引用访问对象，而指针跳转正是要避免的缓存未命中。越围绕数据局部性设计，就越要放弃继承、接口及其好处，没有银弹。（Game Programming Patterns — data-locality）
• 虚方法调用也要查虚表再跟随指针，同样可能未命中。（Game Programming Patterns — data-locality）
• 冷热的边界在真实游戏里很少那么清楚：有的字段只在某种模式或关卡某部分才用。这类优化介于“黑魔法”和“无底洞”之间，很容易陷进去无休止地挪数据测速度，需要经验判断该在哪里花力气。（Game Programming Patterns — data-locality）

设计决策（Game Programming Patterns — data-locality）

代码草图（C++）

按书中示例整理：

// 1. 连续数组：数组里是组件本身，不是指针
AIComponent* aiComponents = new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents = new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents = new RenderComponent[MAX_ENTITIES];

while (!gameOver) {
  for (int i = 0; i < numEntities; i++) aiComponents[i].update();       // 处理 AI
  for (int i = 0; i < numEntities; i++) physicsComponents[i].update();  // 更新物理
  for (int i = 0; i < numEntities; i++) renderComponents[i].render();   // 绘制
  // 其他计时用的游戏循环机制……
}

// 2. 打包数据：活跃粒子保持在前部
void ParticleSystem::activateParticle(int index) {
  assert(index >= numActive_);                 // 不应已经活跃
  Particle temp = particles_[numActive_];      // 与紧跟活跃区的第一个非活跃粒子交换
  particles_[numActive_] = particles_[index];
  particles_[index] = temp;
  numActive_++;
}

void ParticleSystem::deactivateParticle(int index) {
  assert(index < numActive_);                  // 不应已经非活跃
  numActive_--;
  Particle temp = particles_[numActive_];      // 与最后一个活跃粒子交换
  particles_[numActive_] = particles_[index];
  particles_[index] = temp;
}

// update 只遍历活跃区，无需检查标志
for (int i = 0; i < numActive_; i++) particles[i].update();

// 3. 冷热分离
class AIComponent {
public:
  // 方法……
private:
  Animation* animation_;   // 热数据：每帧使用
  double energy_;
  Vector goalPos_;
  LootDrop* loot_;         // 冷数据放在旁边
};

class LootDrop {
  friend class AIComponent;
  LootType drop_;
  int minDrops_;
  int maxDrops_;
  double chanceOfDrop_;
};

UE 与理论页中的对应

• MassEntity → MassEntity 数据导向框架：实体只是一个 ID 加一组片段，组成相同的实体归入同一原型 (Archetype)，并按内存块 (Chunk) 连续存放；无状态处理器通过实体查询成批遍历匹配的块，官方说这样能保证同原型片段的读取性能最佳。这正是上表中“实体本身只是一个 ID”加“同类数据连续存放”的组合。
• 内存层次与缓存友好 → 多线程渲染与任务系统：该页（RTR4 第 18 章）讲了内存墙、空间局部性与时间局部性，以及“缓存访问模式可造成数量级的性能差异”，可以作为本模式的硬件背景。
• Nystrom 推荐的入门读物是 Tony Albrecht 的《Pitfalls of Object-Oriented Programming》和 Noel Llopis 关于数据导向设计 (data-oriented design) 的博文；Richard Fabian 有专著《Data-Oriented Design》；Artemis 是较早、较知名的用简单 ID 表示实体的框架。（Game Programming Patterns — data-locality）