缓存友好的数据布局：让数据排列更讨好CPU

可视化演示

动态演示缓存友好的数据布局的核心机制，通过输入/处理/存储/输出四种模式展示关键概念与交互流程。

台面与冷库：缓存的基本原理

开餐厅，最怕原材料放得太远。备料台就那么一小块，主厨做饭时却要不停从大冷库取料。冷库和备料台之间没有传送带，只有固定尺寸的取料托盘，一趟只端 64 字节——这个托盘，就是 CPU 的“缓存行”。每次去内存取数，都是整行整行地端回来，哪怕你只需要其中一个字节。

主厨有个职业习惯：刚才用过的料酒，一会儿多半还会用（这叫时间局部性）；料酒旁边顺手带回来的生抽，说不定马上也能用上（这叫空间局部性）。CPU 的缓存也是赌这两点：把最近用过、以及和它挨在一起的数据，都留在台面上。如果伸手要的材料已经在台面上，这叫命中；台面上没有，就得跑一趟冷库，这叫失效。从台面取只要 4 个周期，跑一趟冷库要 100 个周期——25 倍的差距，是所有访存优化的起点。

于是后厨的账很好算：一次内存访问的“平均成本”，等于命中和失效两种代价按各自发生比例加权。

理解了托盘和台面之后，后面两种布局谁更“讨好 CPU”，就只看一件事：你往托盘里装的东西，主厨这一轮到底用不用得上。

AoS 结构数组：一人一盒的便当

为了让主厨少跑腿，新来的小工想了个妙招：把每位客人的一餐装成一个便当盒，饭、肉、菜整整齐齐码在一起，一盒接一盒摆在货架上。可流水席上主厨这轮只需要把每盒里的“肉”挑出来过秤，他只能一盒一盒打开、只抠肉，饭和菜原样盖回去。更要命的是，服务员端回来的托盘里，肉旁边永远是暂时用不上的饭和菜——托盘被“陪跑”的食材占满了。

代码里的“便当盒”就是 AoS（Array of Structures，结构数组）。把结构体想成便当盒的模具：一个粒子包含 x、y、vx、vy 四个 double 字段，然后按“粒子 0、粒子 1、粒子 2……”的顺序，把整盒整盒排进数组。如果某个算法只关心 x 和 vx 两个字段（比如只更新速度），访问地址就是跳着走的：拿到粒子 i 的第 0 个字段，再跳 16 字节拿它的第 2 个字段，然后跳到粒子 i+1。

64 字节的缓存行里能装下 2 个完整粒子（32B × 2），但真正要用的只有 2 个 x、2 个 vx 共 32 字节——另一半是 y 和 vy，白占了托盘，行利用率只有 50%。而且这种“跳一步用一步”的模式，让 CPU 里那个勤劳的硬件预取器也猜不透主厨下一步要哪块，没法提前端托盘。

那便当方案就一无是处吗？也不是。如果算法就是按“一个粒子一个粒子完整处理”，所有字段全要用到，便当盒一拆开就是满盘可用，AoS 反而是最优解。问题是很多内核只碰一两个字段，便当盒就变成了“拖累托盘”的元凶。

SoA 数组结构：分桶存放的备料间

老主厨看不下去了，把小工们的便当盒全拆掉，改成“分桶备料”：所有米饭倒进米桶，所有肉块倒进肉桶，所有菜叶倒进菜桶，横平竖直排在冷库里。这轮只需要肉？直接把肉桶端到台前，一勺一勺连续舀——托盘里装的每一块都是肉，再也没有米饭来占地方。

SoA（Structure of Arrays，数组结构）就是分桶方案：不再让“粒子”成盒，而是把字段拆开，各自组成纯类型数组——xs[1024]、ys[1024]、vxs[1024]、vys[1024] 四个桶。只读 x 和 vx 时，就顺序扫一遍 xs 桶，再顺序扫一遍 vxs 桶，全程连续。

连续访问带来连锁反应：每条缓存行装 8 个 double，个个都是本轮要用的，行利用率接近 100%；硬件预取器看到这样规整的步长，会提前把后面几行端上台面；SIMD 指令还能一次加载连续 4 个 double 并行计算，而 AoS 里同样的事需要 gather 指令把散落的数据捞出来洗一遍。三层优势叠在一起，往往就是 2~4 倍的差距。

分桶也有软肋：如果某轮确实需要“同一时刻拿到一个粒子的全部字段”，得分四次从四个桶取，反而绕路。所以别问“分桶和便当谁更好”，要问：这一轮主厨的取料模式，是按字段批量用，还是按个体完整用？

热冷分离：常用食材放台面

主厨盘点台面时发现，真正天天用的就是盐、糖、油、料酒这几样；那个一年才动一次的熏火腿，却天天占着台面最显眼的位置。他立下新规矩：按使用频率决定位置——高频材料留在台面，低频材料全部塞进冷库深处。

结构体里也有“熏火腿”。很多 struct 既装着每轮都要用的热字段（位置、速度、朝向），也装着一辈子读不了几次的冷字段（名称、描述、调试日志、创建时间）。把它们焊死在同一个结构体里，等于让熏火腿天天占台面——它占的每一字节，都在稀释缓存行里热字段的密度。

做法分三步：先给每个字段记访问频率；再把热字段抽进一个紧凑的 hot 结构体；冷字段挪去另一个 cold 结构体，两边用同一个数组下标关联。热结构变小后，一条缓存行能装下的元素数变多，遍历热字段的命中率显著上升；冷字段也几乎不再被拉进缓存，内存占用同步下降。

一个场景图里，把节点热结构从 48B 压到 16B，32KB 缓存从驻留不到 700 个节点变成 2048 个，相当于备料台凭空大了三倍。这不是魔法，只是把“常用”和“不常用”分开摆放而已。

对齐与填充：别让菜跨两个托盘

托盘的尺寸是固定的，冷库的货架格位也是焊死的——每次端托盘，都是从固定格位整块端出。后厨最头疼的事，是一份菜恰好骑在两个托盘的交界处：明明只多出 8 字节，却要端两个托盘，白跑半趟。

内存里有一模一样的尴尬：如果结构体大小不是 64 的倍数，数组元素就会“错位”，一个元素可能骑跨两个缓存行，读它一次要触发两次失效。对策是对齐：让数组起始地址按 64B 对齐，或给结构体 padding（填充）到缓存行整数倍，保证每个元素整整齐齐落进一行，不跨边界。

对齐还有个隐蔽的亲戚叫伪共享。两个线程各改一个缓存行里互不相干的变量（比如数组相邻元素），逻辑上毫无关系，但缓存一致性协议认为“这行被改了”，于是互相把对方手上的行作废，两个线程反复跑冷库。解决办法同样是填充：把高频触碰的变量各自推到不同的缓存行，物理隔离。

填充是有代价的——空占的字节会减少缓存驻留元素总数。所以明智的做法是：只在确认存在跨行浪费或伪共享的场景才上填充，而且要用实测对比说话，而不是逢结构体就 pad 到 64B。

访问顺序重组：集中火力出菜

主厨最恨“翻锅式做菜”：切两刀肉，去搅一下汤，再回来切肉，再去热饭……台面被不同食材反复占满又清空，冷库的腿都要跑断。后来改成“集中出餐”：先做完所有肉菜，再集中做汤，一轮只面对一种材料。

代码里的“翻锅”叫工作集失控：循环体一会儿摸数组 A 的头，一会儿摸数组 B 的尾，访问的内存区域太大，缓存根本装不下，行刚取回来就被挤出。重组访问顺序的思路，就是让任一时间窗口内访问的地址集中在一小片区域，并且在这片区域被挤出缓存之前把它用完。

常用手法有三：循环重排——把内层循环改成连续访问同一数组；分块（tiling）——把大数组切成小块，每块大小以“装得进缓存”为准，块内反复利用已取回的行；按访问顺序排序——例如按空间邻近访问的粒子，在数组里也排成空间相邻，遍历时地址自然连续。

这跟主厨“集中火力出菜”是同一个道理：把这一轮用得完的量正好摆在台面上，用完了再换下一批。缓存友好的本质，从来都是“批处理”，而不是“随机应变”。

实测对比：让数据说话

后厨里永远只有两派人：“我觉得这样快”和“我量过，这样快”。老主厨只信后者。数据布局折腾了一圈，如果不拿数据说话，跟算命没什么区别。

实测要讲方法：数据量要超过缓存容量，否则小数组全塞进缓存，什么布局都很快；多跑几次取中位数，排除噪音；除了盯墙钟时间，还要用 perf 或 Cachegrind 这类工具看 cache-misses——因为有时布局改了但命中率没变，说明瓶颈根本不在访存。

一组来自真实项目的示意数据：粒子系统从 AoS 改 SoA，单字段遍历快约 2~3 倍；热冷分离后，L1 命中率从 68% 升到 92%，总耗时少约 1.4 倍；严重伪共享的场景填充后，多线程吞吐提升 4~5 倍；大矩阵分块遍历快 1.5~2 倍。这些数字不保证在你机器上重现，但量完之后，你的直觉会越来越准。

收尾记住四条取舍原则：AoS 留给“记录级、全字段、按序处理”；SoA 留给“字段级、批量、可向量化”；热冷分离看冷字段占比是否明显；对齐填充只打“已确认的仗”。没有银弹，但每一次实测，都会让你比“凭感觉优化”的人多看透一层真相。

AI 应用场景

Python 演示

LINE_BYTES = 64CACHE_SLOTS = 16MISS_CYCLES = 100HIT_CYCLES = 1  class CacheSim:    """模拟 64 字节缓存行与直接映射小缓存, 统计命中数与周期"""     def __init__(self, line_bytes=LINE_BYTES, slots=CACHE_SLOTS):        self.line_bytes = line_bytes        self.slot_tags = [-1] * slots        self.hit_count = 0        self.miss_count = 0     def read(self, address):        """按一个字节地址发起一次读, 返回模拟周期"""        tag = address // self.line_bytes        slot = tag % len(self.slot_tags)        if self.slot_tags[slot] == tag:            self.hit_count += 1            return HIT_CYCLES        self.slot_tags[slot] = tag        self.miss_count += 1        return MISS_CYCLES     def bench(self, addresses):        """跑完一整段访问序列, 返回 (命中数, 失效数, 总周期)"""        self.hit_count = 0        self.miss_count = 0        self.slot_tags = [-1] * len(self.slot_tags)        total_cycles = 0        for addr in addresses:            total_cycles += self.read(addr)        return self.hit_count, self.miss_count, total_cycles  def aos_kernel(n, fields=4, field_bytes=8, use=(0, 2)):    """AoS: struct 连续存放, 每元素只访问 use 指定的两个字段"""    stride = fields * field_bytes    seq = []    for i in range(n):        base = i * stride        for idx in use:            seq.append(base + idx * field_bytes)    return seq  def soa_kernel(n, fields=4, field_bytes=8, use=(0, 2)):    """SoA: 每个字段独立成数组, 只访问 use 指定的两个数组"""    seq = []    for idx in use:        start = idx * n * field_bytes        for i in range(n):            seq.append(start + i * field_bytes)    return seq  if __name__ == '__main__':    n = 1024    sim = CacheSim()    aos_res = sim.bench(aos_kernel(n))    soa_res = sim.bench(soa_kernel(n))    ratio = aos_res[2] / soa_res[2]    print('AoS: 命中 {} 次, 失效 {} 次, 周期 {}'.format(*aos_res))    print('SoA: 命中 {} 次, 失效 {} 次, 周期 {}'.format(*soa_res))    print('SoA 相对 AoS 加速约 {:.2f} 倍'.format(ratio))

1. tag = address // self.line_bytes算出地址落在哪条缓存行，整行取回是缓存的基本动作。
2. slot = tag % len(self.slot_tags)直接映射缓存把行号散列到固定槽位，模拟真实缓存的组映射。
3. if self.slot_tags[slot] == tag:槽位里存的还是这一行，就是命中（hit）。
4. self.hit_count = 0bench 开头清零计数并清空槽位，保证两次布局互不污染。
5. base = i * strideAoS 里第 i 个粒子的起始地址，stride 是 32B 的整条记录。
6. for idx in use: seq.append(base + idx * field_bytes)只访问 use 指定的字段，模拟“只读 x 和 vx”。
7. start = idx * n * field_bytesSoA 里每个字段数组的起始地址，字段之间完全分开。
8. print('SoA 相对 AoS 加速约 {:.2f} 倍'.format(ratio))用数据下结论：同一逻辑，布局不同，结果差近一倍。

常见误区

面试题