17. Data Locality
17. Data Locality：按访问顺序连续排列热数据，减少缓存行搬运和指针追逐，通过可复位因果实验和反例证据验收。
17. Data Locality
学习目标
- 能解释缓存行的作用
- 能对比AoS与SoA
- 能应用冷热数据分离
为什么"17. Data Locality"从问题证据开始
你的游戏里有上万个实体，每帧都要遍历它们更新 AI、物理、渲染。最直觉的 OOP 做法是把每个实体的所有属性打包进一个对象，对象们散落在堆上——new 出来的对象地址彼此无关。代码今天能跑，但性能惨淡：遍历一万个实体时，每次访问对象都要跳到一块陌生的内存，CPU 缓存反复未命中——处理器大部分时间在等内存，而不是在算。
本页把"无模式基线"定义为"实体对象散落堆上"的代码，然后引入数据局部性作为候选机制，验证它是否真的让"遍历热点"变快。通过条件是相同算法下缓存命中率显著上升、帧耗时下降——而不是改算法。
🔮 猜一猜：AoS 与 SoA 遍历一万个位置，哪个更快？
来源、版本与独立重写边界
本页用作者完整在线正文核对正式标题、设计分叉和时代语境，并以作者源码仓库交叉检查结构。仓库许可证明确正文、HTML与样式为 CC BY-NC-ND 4.0，示例程序等其他文件为 MIT；因此下列中文解释、图示、交互和代码均为独立教学重写，不翻译、拼接或改写受 ND 限制的原文表达。
本章机制与术语
理解 Data Locality 需要四个核心概念：
- ↡：CPU 与内存之间的高速缓冲——按"缓存行"（64 字节）批量搬运数据。
- 缓存命中/未命中（hit/miss）：访问的数据已在缓存中（快）还是要从内存加载（慢 100 倍）——性能分水岭。
- ↡：同类型数据紧密排列——遍历时顺序访问，预取生效。
- ↡：通过指针跳到不连续内存——缓存友好的反面。
四个概念共同约束"按访问顺序连续排列热数据，减少缓存行搬运和指针追逐"：任何结论都必须回到"缓存命中率、遍历帧耗时、内存局部性"三个可观察量。
Data Locality — 让数据排列贴近访问方式
第 1 / 4 步 · ① 分散存储：每个实体带全部属性，遍历跳跃访问
同属性排成连续数组，遍历变顺序访问——缓存友好，性能翻倍。
💡 对着动画看：动画上半部分是"分散存储"——pos/hp/sprite 交错排列（红色块），遍历只取 pos 时每步跳过两块内存，缓存几乎全未命中；下半部分是"连续数组"——六个 pos 紧密排列（绿色块），顺序扫描预取生效。读"数据是性能？"一节时，记住这个对比：数据怎么排，决定遍历多快。
官方结构逐项深读
17. Data Locality
Data Locality 的主张：让数据在内存里的排列，贴近代码的访问顺序。如果代码顺序遍历"所有实体的位置"，那么位置数据就应该是一块连续数组，而不是散落在各个对象里。它的目的不是改算法（算法复杂度没变），而是改数据布局——让 CPU 缓存高效工作，把"等内存"的时间省下来。
Intent
意图：利用 CPU 缓存的特性加速热点循环。缓存按行搬运数据（一次 64 字节），如果访问的数据连续，一次搬运喂饱多次访问（命中）；如果数据分散，每访问一次就搬一行（浪费带宽）。数据局部性让"搬运的字节"和"用到的字节"比例接近 1:1——这是现代 CPU 上最廉价的优化。
Motivation
一万个实体的遍历：如果每个实体是独立 new 的对象，地址随机散布在堆上。遍历第 i 个实体的位置时，CPU 要把含它的缓存行搬进来——但下一个实体在完全不同的地址，刚搬的行用不上，再搬一行。一万次访问 = 一万次搬运。缓存行里 99% 的字节是浪费的——性能瓶颈从"算法"变成"内存带宽"。
A data warehouse
把数据想象成仓库：缓存是叉车，一次能搬"一托盘"（64 字节）。如果托盘里正好是接下来要用的货（连续数据），效率极高；如果货散落各处，叉车跑一趟只取一件——访问模式决定叉车效率。游戏里"货"是实体属性，"访问模式"是遍历循环。数据局部性 = 让托盘装得满、路线走得直。
A pallet for your CPU
CPU 的"托盘"：缓存行 64 字节，能装 16 个 float 或 8 个 double。顺序访问一个 float 数组时，搬一行喂 16 次访问；访问散落对象时，搬一行只喂 1-2 次。差距可达 10 倍——同样的算法，布局不同，速度天差地别。这就是为什么"数据结构 > 算法技巧"在性能优化里常被低估。
Wait, data is performance?
"数据也是性能？"——是的，而且常常是最容易被忽略的性能。程序员优化算法、优化循环，却很少看数据怎么摆。现代 CPU 快过内存几个数量级，等内存的时间支配了运行时间。数据局部性是"让 CPU 少等内存"的艺术——不改变任何算法逻辑，只改数据排列，就能收获数倍加速。
The Pattern
模式结构：识别热点循环（每帧遍历的热门数据）→ 把该循环访问的数据按列分离（位置数组、血量数组、精灵数组各一块）→ 用连续数组存储 → 遍历时顺序访问。核心原则：同一循环里一起用的数据，在内存里也放一起（或者至少按访问顺序连续）。
When to Use It
何时用数据局部性：性能瓶颈在遍历大量数据（实体更新、粒子系统、碰撞检测）且已确认是缓存问题（profile 显示 cache miss 高）。何时不用：数据量小（几千字节装进缓存，布局无所谓）、访问模式本身随机（数据局部性救不了随机访问）。判断标准：profile 说了算——先测缓存命中率，再决定是否重构布局。
Keep in Mind
数据局部性的代价：代码更复杂（对象被拆成多个数组，封装被破坏——entity.position 变成 positions[entityId]）、数据结构改变（数组结构（SoA）vs 对象结构（AoS）的选择）、不是银弹（只优化热点，别把整个代码库改成数组风格）。作者提醒：这是权衡——用可读性换性能，只在 profile 证明值得时用。
Sample Code
示例代码：GameEntity 数组 vs positions[]/healths[]/sprites[] 三个数组。AoS（数组 of 结构体）：Entity entities[N]，遍历取位置要跳过其他字段（缓存行浪费）；SoA（结构体 of 数组）：float xs[N], ys[N]，遍历位置就是顺序访问两个数组（缓存完美）。SoA 是数据局部性的标准实现——现代 ECS 就是 SoA。
Contiguous arrays
连续数组的第一原则：别用指针追逐，用索引。实体互相引用时，Entity* next 会跳到不连续内存；换成 int nextIndex + 一个大数组，遍历就是顺序内存访问。对象池、ECS 都用"数组 + 索引"代替"堆对象 + 指针"——这是数据局部性最直接的落地：同批数据住在一起。
Packed data
紧凑数据：把结构体的字段按使用频率与大小重排——高频字段放前面（缓存行里先装它）、冷热字段分离（见下节）。struct { float pos[3]; int hp; char name[16]; }——如果遍历只取 pos 和 hp，name 就是缓存行里的浪费。让热字段在缓存行里尽量多，冷字段挪走。
Hot/cold splitting
冷热分离：把实体的热数据（每帧访问：位置、速度、血量）与冷数据（偶尔访问：名字、描述、掉落表）拆成两块。热数据紧凑数组（缓存友好），冷数据单独存放（访问少，不在乎局部性）。这比"所有数据塞一个结构体"缓存效率高得多——按访问频率分家，热的一起住，冷的自便。
Design Decisions
两个关键设计决策：多态怎么处理（虚函数与数据局部性冲突）和 实体怎么定义（对象 vs 数组）。前者决定是否牺牲多态换性能，后者决定数据的基本组织——下面两节展开。
How do you handle polymorphism?
多态与局部性的矛盾：虚函数让每个对象可能携带不同的数据布局（子类不同字段），无法统一排成数组。解法：放弃多态，按类型分数组（每种实体一个数组：skeletons[]、goblins[]——同型实体数据布局相同，可连续）；或用标记联合/变体（一个数组存多种实体，用类型标签区分——布局固定但灵活性降）。作者倾向：热点用同构数组，多态留给冷数据。
How are game entities defined?
实体定义：对象风格（Entity 类 + 继承/组件——语义清晰，但数据散落，缓存差）与数组风格（positions[]/healths[] 等平行数组 + ID 关联——缓存好，但代码要管理多个数组的同步）。作者建议：混合——实体逻辑仍用对象/组件思维，但底层热点数据用 SoA 数组，实体持索引而非指针。ECS 正是这套思路的完整实现。
See Also
- Component：组件把实体能力拆开，数据局部性把组件数据排成数组——ECS 结合两者：组件=数据、系统=逻辑、数组=存储。
- Object Pool：对象池固定槽位 + 连续数组，天然与数据局部性兼容——池中的对象住在一起。
- Spatial Partition：空间分区把对象按位置分组，与数据局部性互补——分区后同组对象可能也在内存上相邻。
可迁移实现或计算骨架
initial state -> profile 定位缓存热点 -> 热数据按列分离 -> 连续数组存储 -> 遍历顺序访问
fault injection -> 实体对象散落堆上，指针追逐
pass condition -> 缓存命中率上升、遍历帧耗时下降
reset -> initial state对应实现要点：先 profile 确认缓存问题是瓶颈；热点循环访问的数据拆成平行数组（SoA）；实体用索引而非指针；热冷数据分离。该骨架只保存实验合同；真实项目还要固定数据规模、缓存行大小与 profile 基线，并保留基线实现以便回退。
本章练习与节点验证矩阵
练习
问题 1：布局对比。
操作：在动画中对比分散存储与连续数组两种布局的遍历代价
问题 2：SoA vs AoS。
操作：实现位置遍历的 AoS 与 SoA 两个版本，各跑一万实体测帧耗时
问题 3：冷热分离。
操作：把实体的名字/描述挪出热结构体，对比缓存命中率
问题 4：指针 vs 索引。
操作：用指针链表与索引数组分别遍历实体，对比耗时
术语复核
名词解释
本章出现的专业名词，用大白话再讲一遍。
- 缓存
- 缓存命中
- 指针追逐
练习答案参考
练习判据即答案：每个练习的"验证判据"列给出了通过标准——先自己动手，再对照判据核验。
术语复核与本章回顾
掌握"17. Data Locality"意味着能从"实体对象散落堆上让缓存反复未命中"出发，解释缓存、缓存命中、连续数组与指针追逐四者的关系，再用"缓存命中率、遍历帧耗时、内存局部性"三个可观察量推翻或保留实现。若三个判据不能同时满足，本章仍未通过。
一句话回顾：数据怎么排，决定遍历多快——热数据按列排成连续数组，遍历变顺序访问，缓存喂饱、指针不追，性能白捡数倍。
阅读导航
← 上一页：VI. Optimization Patterns · 下一页：18. Dirty Flag → ← 上一页：VI. Optimization Patterns · 下一页：18. Dirty Flag →