实践数据导向设计：优化程序内存占用与缓存友好性

ChimiChanga

演讲者背景与动机 [0:00]

Andrew Kelley是Zig编程语言的创建者和Zig软件基金会的主席兼首席软件开发者。

• 编程之路的瓶颈与突破 [2:26]
  • 在约10年的编程生涯中，Andrew曾一度感到技能进步停滞，代码质量难以突破，总认为一周前的代码就是“垃圾”。
  • 意识到传统面向对象编程的局限性，并开始探索数据导向设计（Data-Oriented Design, DoD）。
  • 通过观看性能相关讲座、参加Handmade Seattle活动及阅读Richard Fabian的《数据导向设计》书籍，最终领悟了DoD的核心思想。
  • 演讲目标是帮助听众快速理解并应用DoD，避免他曾经历的漫长学习曲线，实现编程技能的又一次飞跃。

    

计算机内存结构与性能瓶颈 [4:43]

• CPU缓存层次与速度差异 [5:06]
  • 计算机内存由多级缓存组成：L1数据缓存、L1指令缓存（每个CPU核心独有），L2缓存（通常每个核心独有或共享），L3缓存（CPU核心间共享），以及主内存。
  • L1缓存速度最快（仅需几周期），但容量最小（256 KiB）。
  • L2缓存速度稍慢，容量稍大（2 MiB）。
  • L3缓存速度更慢，容量更大（16 MiB）。
  • 主内存速度最慢（几百周期），但容量最大（数十 GB）。

    

• CPU操作成本的巨大差异 [5:39]
  • CPU操作成本（以CPU时钟周期计）因操作类型和数据位置而异，差异可达几个数量级。
  • 极快操作：寄存器操作 (0周期)、L1缓存读取 (4周期)。
  • 中等速度操作：L2缓存读取 (10周期)、L3缓存读取 (40周期)。
  • 极慢操作：主内存读取 (200周期)、内核调用 (24000周期，如malloc可能触发)。
  • 关键发现：数学运算（如乘法）比L1缓存读取更快。这意味着有时重复计算比存储和读取结果更高效，反之可能因为内存访问而减慢。

    

• 缓存线与缓存未命中 [8:00]
  • 所有内存访问都通过缓存线（Cache Line）进行，通常大小为64字节。
  • 目标是最小化缓存未命中（Cache Misses），因为缓存未命中意味着CPU需要从较慢的内存层级（如主内存）加载新的缓存线，这将带来巨大的性能开销。

    

内存占用减少策略 [13:47]

• 核心策略：识别内存中大量存在的相同类型对象（如结构体），并努力缩小每个对象的大小。
• 1. 理解内存布局：结构体填充（Padding） [9:44]
  • 每个数据类型都有其自然对齐（Natural Alignment）和大小（Size）。
  • 编译器为了优化访问速度，会在结构体字段之间插入填充字节，以确保每个字段和整个结构体在内存中都能够正确对齐。
  • 例如，一个包含u32（4字节）和bool（1字节）的结构体，其大小可能因填充而变为8字节（在64位系统上），而不是简单的5字节。

    

• 2. 使用索引代替指针 [14:41]
  • 在64位CPU上，指针通常占用8字节，而使用32位无符号整数（u32）作为索引可以将其大小减半至4字节。
  • 优点：显著减少结构体大小，降低整体内存占用；同时可以降低结构体的对齐要求，进一步减少内部填充。
  • 注意事项：这种方法会降低编译时的类型安全，因为所有索引都是同类型（u32）。可能需要通过语言特性（如Zig的anyopaque）或自定义句柄系统来弥补类型安全问题。建议查阅Andre Weissflog的“Handles are the better pointers”博客文章。

    

• 3. 将布尔值带外存储（Out-of-band Storage） [16:48]
  • 单个布尔值（1位信息）可能因为对齐和填充而浪费整个缓存行（64字节）的空间。
  • 策略：将布尔值从主结构体中移除，通过将对象分离到不同的数组（例如，“活着的怪物”数组和“死去的怪物”数组）来隐式表示其状态。
  • 优点：显著减少结构体大小，从根本上消除了布尔值引起的填充浪费；提高循环效率，因为可以直接迭代处理活着的怪物，而无需加载和检查死去的怪物数据。

    

• 4. 使用结构体数组（Struct-of-Arrays, SoA）消除填充 [19:10]
  • 传统的“数组结构体”（Array-of-Structs, AoS）布局中，每个结构体实例都可能包含填充字节。
  • 策略：将结构体中的各个字段拆分为单独的数组。例如，一个Monster结构体包含anim（动画指针）和kind（种类枚举），可以转换为一个anim指针数组和一个kind枚举数组。
  • 优点：消除结构体内部的填充，大幅度减少总内存占用；提高数据局部性，因为相同类型的字段集中存储，CPU可以更高效地批量处理。

    

    

• 5. 将稀疏数据存储在哈希表中 [21:48]
  • 如果结构体中某些字段只有少数对象会使用（即数据是稀疏的），将其直接包含在结构体中会造成大量内存浪费。
  • 策略：将这些稀疏字段移出主结构体，并存储在一个哈希表（或类似稀疏数据结构）中，以主结构体的索引作为键。
  • 优点：只为实际存在的数据分配内存，显著减少整体内存占用。例如，一个怪物结构体中只有10%的怪物持有物品，将held_items数组移到哈希表中，可以大大节省内存。

    

• 6. 使用“编码”代替面向对象/多态 [23:29]
  • 传统面向对象的多态（如带标签的联合体或继承）虽然提供了统一的接口，但可能因为需要为最大的变体预留空间而浪费内存。
  • 策略：根据数据的实际分布和访问模式，设计更紧凑的“编码”方式。将不常用或特定类型的状态信息直接编码到枚举标签中，或将额外数据存储在外部辅助数组中，并使用主结构体的索引指向它们。
  • 优点：平均每个对象占用的内存更小。例如，将蜜蜂的颜色和人类是否带牙套的信息直接编码到怪物的类型标签中，可以进一步减少结构体大小。

    

Zig编译器案例研究 [30:11]

Andrew Kelly将上述数据导向设计原则应用于Zig编译器，旨在提升编译速度。

• Zig编译器流水线 [30:36]
  • 编译器流程：源代码 -> Tokenizer -> Tokens -> Parser -> AST -> AstGen -> ZIR -> Sema -> AIR -> CodeGen -> MIR -> Emit -> 机器码。
  • 数据部分：Tokens、AST、ZIR、AIR、MIR是编译器内部数据，其内存布局可以由开发者控制。
  • 逻辑部分：Tokenizer、Parser、AstGen等是处理数据的逻辑组件。
  • 高度并行部分：流水线的左侧（Tokenizer、Parser、AstGen、ZIR）是高度并行的，适合进行优化。

    

    

• Token对象的优化 [32:15]
  • 优化前：每个Token对象占用64字节，包含了不必要的行/列信息、结束位置和未解析的字面量数据。
  • 优化思路：
    • 行和列信息可以按需（lazily）计算，无需存储。
    • 将最大源文件大小限制为4GB，可以使用32位无符号整数作为索引。
    • Token的结束位置可以根据其类型隐含或通过重新词法分析计算，无需存储。
    • 整数、浮点数和字符串字面量的解析可以延迟到后续阶段。
  • 优化后：每个Token对象平均仅占用5字节（只存储类型标签和起始位置索引）。

    

• AST节点（AsNode）的优化 [35:22]
  • 优化前：每个AST节点平均占用120字节，包含布尔值、行/列信息以及指向其他AST节点的指针。
  • 优化思路：
    • 行和列信息可以延迟计算（使用4字节索引指向Tokens数组）。
    • 仅需存储一个Token索引（入口Token），其他相关Token可以通过该索引在Token数组中查找。
    • 再次利用编码策略，将多种类型（如变量声明、if、while语句）编码到更小的结构中。
  • 优化后：每个AST节点平均降至15.6字节。

    

• 性能提升 [37:57]
  • Token和AST优化结果：
    • 缓存未命中减少15%。
    • 总指令执行量减少28%。
    • 总CPU周期减少26%。
    • 墙钟时间（Wall Clock Time）加快22%。

- ZIR阶段优化结果 [38:41] - ZIR是Zig中间表示（Zig Intermediate Representation），优化前平均每个节点54.0字节。 - 优化思路：移除不必要的源位置信息；将引用（指针）替换为32位索引；将简单值（如true/false）直接编码到引用中；使用编码策略代替面向对象/多态的结构。 - 优化后：平均每个ZIR节点降至20.3字节。 - ZIR阶段优化结果： - 墙钟时间减少39%。 - 峰值内存使用减少40%。 - 缓存未命中减少53%。 - 指令执行量减少23%。 - CPU周期减少41%。 - 并行化与磁盘I/O优化 [42:44] - 通过线程池对高度并行阶段（Tokenizer、Parser、AstGen、ZIR）进行处理，在Dell Inspiron笔记本上达到了每秒890万行代码的速度。 - ZIR的输出现在仅由少数几个紧凑的数组组成，使得从磁盘保存和加载缓存变得极其高效，可以通过单次POSIX系统调用（preadv/pwritev）完成，进一步避免了重复工作。

• 项目进展与展望 [44:14]
  • 词法分析、解析和AST生成阶段已100%完成数据导向设计优化。
  • 语义分析（Sema）阶段完成了35%。
  • 后端（代码生成和发射）仍在开发中，尚未进行这些优化。
  • Andrew坦言，目前发布的Zig编译器仍是旧版本，新的优化将在未来的版本中默认启用。

总结 [45:46]

• 将CPU缓存添加到计算机的心理模型中，深刻理解CPU快而主内存慢的根本性能瓶颈。
• 核心思想：识别内存中大量存在的相同类型对象，并努力缩小每个对象的大小。
• 运用各项实用技巧来减少内存中对象的大小：
  • 使用索引代替指针（注意类型安全）。
  • 将布尔值带外存储。
  • 使用结构体数组消除填充。
  • 将稀疏数据存储在哈希表中。
  • 使用“编码”代替面向对象/多态。
• Zig编译器案例表明，这些数据导向的优化策略带来了巨大的实际性能提升，证明了其实用价值。