实用的面向数据设计¶
标题：Practical Data Oriented Design (DoD)
日期：2024/07/13
作者：Andrew Kelley
链接：https://www.youtube.com/watch?v=IroPQ150F6c
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
备注一：原来 index-based 和 SoA 设计就是 DoD，早就这么用了。其他技巧还是值得一学的。
备注二：encoding approach 一章生成的代码太过分了，我手动修了一下。建议还是看原视频。
备注三：Zig 案例以后再看，感觉很不错，TODO.
谢谢。我是 Andrew Kelley，Zig 软件基金会的主席和首席软件开发者。感谢大家来听我的演讲。首先，我这个遥控器该指向哪里？我正在按“前进”按钮。没反应？没有。我们遇到了一些技术问题。哦，好了。我得用力长按一下。好了，成功了。
好吧，我想先简单介绍一下我的背景故事。我相信在座的很多人都会觉得很熟悉。我很小的时候就对游戏产生了兴趣。但我父母给我定了个规矩，我每天只能玩电脑、看电视或玩电子游戏一小时。不管是什么，就是一天一小时。时间一到，我就会被赶下线。所以，不用说，我变得非常会钻空子。
我玩的第一款游戏是世嘉创世纪（Sega Genesis）上的《刺猬索尼克2》。所以这款游戏在我心中总占有一个怀旧的位置。但我最喜欢的游戏是那些你可以自己创造东西的游戏。有人还记得《托尼霍克职业滑板2》（Tony Hawk’s Pro Skater 2）吗？它里面有那个关卡编辑器，对吧？那玩意儿简直绝了。这个东西太酷了。你可以制作自己的关卡，可以设置起点，甚至可以自己制作、命名、计分那些“gap”（技巧挑战点）。然后你还可以和朋友们玩本地多人游戏，玩像 HORSE 和捉人游戏之类的。超级酷。
所以当我发现编程时，感觉它就像是终极游戏，对吧？就像是“制作你自己的游戏”。那是终极的力量。
是的，然后我开始接触 Visual Basic 6。直到现在我仍然非常喜欢它，对吧？你打开这个程序，就像任何其他同时代的程序一样，它会给你一个新文档，一个名为“Form1”的窗口，和你最终看到的样子一模一样。它简直就是在乞求你拖一个按钮上去，让它做点什么，对吧？
随着我的进步，我学了其他语言。我学了 Perl、Python、C++、C。是的，我和大家一样，学的顺序是错的。然后，每当我回头看自己写的代码，哪怕只是一周前写的，我总会觉得它看起来像垃圾。我会想：“是啊，我一周前写的那些代码，简直是垃圾。我这一周学到的东西可真多啊，对吧？” 这大概是我十年来的经历。你知道，每次我看我的旧代码，我都会想：“我知道怎么能做得更好。”
但后来，这种情况停止了，对吧？在大约十年的经验之后，我开始写代码，然后回头看我的旧代码，我会想：“嗯，还行。如果我现在来写，我大概也会这么写。我看不出有什么可以改进的地方。” 所以……你知道，整个过程的一部分就是，学习到，哦，他们教我们的面向对象编程，不完全对。就像，你知道，你学会了自己的方式。但我还是遇到了瓶颈，对吧？在某个时候，我遇到了这个瓶颈。
但后来发生了一些事，我又开始有那种感觉了。我现在就处于这个阶段，当我回头看我四个月前写的代码时，我又开始发现问题了。我突破了那个瓶颈。对我来说，这个突破点就是学习了面向数据编程（data oriented programming）。
为了达到这个阶段，你知道，我在 YouTube 上看了很多讲座。那个就非常有名。事实上，让我在这里花点时间……好的。我想我要做一个关于面向数据设计的演讲。我想我最好……是啊，感觉对了。是的，感觉对了。好的。
总之，是的，为了达到这个阶段，我看了一些讲座。我参加了三次 Handmade Seattle 大会，和很多人交流过。然后我读了 Richard Fabian 写的这本《面向数据设计》的书。但对我来说，我还是花了很长时间才真正理解它。就是，很长一段时间里我都没有顿悟。
所以我这次演讲的目标是，如果你在这里，如果你正处于我生命中那十年的阶段，我想帮助你和我一起跨越它。就像，如果你的学习模式和我一样，也许我可以帮你快进一下，对吧？
好的，那么，我们开始吧。
什么是计算机？¶
让我们从宏观视角来看。如果我在这台我用来演示的笔记本电脑上运行 lscpu 命令……哦，等等。我们的演示方式和我想的完全不同。开个玩笑。如果我们在我的主力笔记本上运行 lscpu，它会告诉我们一些信息。它有八个核心，支持超线程。我有这么多的 L1 缓存、L2 缓存、L3 缓存。这是什么意思呢？
这里用图表的形式展示一下。所以，这是从内存的角度来看，计算机到底是个什么玩意儿的宏观模型，对吧？如果你注意到，L1 的内存非常小。L2 多一点。L3 再多一点。然后主内存（Main Memory）是巨大的，对吧？所以这里存在权衡。L1 非常快。L2 慢一点。L3 再慢一点。而主内存则要慢得多。所以，在我进入下一张幻灯片时，请试着把这张小图记在脑子里。
这张图表要感谢 ithayer.com。如果你之后去查一下这张图，因为它超级有趣。我只会在这里强调几点。但我想指出的是，L1、L2 和 L3 在这张图表上的位置，对吧？如果你看这边，抱歉，按错按钮了。哦，是这个。这个。所以如果你看这边，我们每往下一行，就是一个数量级的差距，对吧？L1，非常快。好的，L2，一个数量级。L3，一个数量级。主内存（Main RAM），一个数量级，对吧？
另一个有趣的观点是，所有这些东西，CPU能做的很多事情都远比从主内存读取要快，对吧？所以，特别要注意的是，你能做的最快的事情是数学运算。是的，数学运算比从内存中读取更快。所以你可以从中得出一个非常有趣的结论，那就是：你应该对数学运算的结果进行“记忆化”（memoize）吗？也许不应该。你可能仅仅因为没有重复计算而拖慢了自己，对吧？这也包括乘法，对吧？乘法，就在那里。甚至比 L1 读取还要快，对吧？
此外，既然我们关注的是内存，我还想强调一件事。内核调用（kernel call）是这张图上可能最慢的事情之一。而这在你调用 malloc（堆分配）时就可能发生，对吧？而且，为了强调一下，关于那个 JSON 解析器的演讲，这也与之相关，对吧？因为他们发现，在第一轮优化中，正是 malloc 产生的内核调用，导致性能下降到了这个数量级，对吧？
好的。那么这里的要点是什么？CPU 很快，但主内存很慢。
好的。现在我们理解了。但我们该如何应用这个知识呢？我们实际上需要做什么？
我们需要在 CPU 上做更多的事情。我们需要减少与内存相关的操作。我们会更深入地探讨这一点。但让我再用一个宏观的心智模型来帮助你理解。
试着这样想：每当你需要进行任何内存访问时，你总是会经过一条缓存行（cache line）。总是如此。 那么问题是，为了完成任务，我们是否需要驱逐（evict）一条缓存行？
比方说，我要把一些东西存到内存里。每条缓存行通常是 64 字节。也可能是 32 或 128，但通常是 64。这就是你的操作粒度。所以，如果你要访问一个 64 字节块的某个部分，然后你又想访问同一个 64 字节块的另一个部分，那很好。你不会驱逐缓存行。但是，如果你访问一个非常远的地方，你可能需要另一条缓存行参与进来。你就会增加驱逐一条缓存行的几率，对吧？
所以这里的核心要点就是：不要产生缓存未命中（cache miss）。这就是全部的要点，对吧？
现在我要让这个……你知道，我的演讲题目是《在实践中应用面向数据设计》，对吧？我想帮助你做到它。你知道，我们都希望东西跑得更快，我们想要高质量的代码。我们到底该做什么？
这里有一个你可以使用的策略，在众多策略中，你可以用它来应用面向数据设计。
好的。想想你的个人项目。想想你正在做的东西。想一想，你在内存中哪里有大量相同类型的对象，比如一个结构体（struct）。想一想你内存中数量最多的那个结构体。然后想一想，你该如何让它变得更小。 这就是全部的诀窍。这就是我们今天要讨论的全部内容。
结构体在内存中的布局¶
好的，第二部分。我将做一个关于结构体如何在内存中布局的简短讲座。这部分是互动的，所以我希望大家可以喊出答案，别害羞，即使你是个爱卖弄的万事通也没关系。尽管说出来。
所以，在编程中，像 C、Zig、Nim 等语言里的每一种类型，都有一个自然的对齐（alignment）和大小（size）。我们通过一些例子来学习。
u32，一个 32 位的整数。它的自然对齐是多少？
四。
四。很好。大小呢？
四。
好的，大家意见一致。
我们来个不一样的。一个 bool。自然对齐是多少？
四。
大小呢？
四。
好吧，我听到了一些不同的答案。实际上，对齐是 1。你甚至可以在它没有对齐的情况下加载一个布尔值，加载一个字节没问题。对齐是 1，大小是 1。
下一个挑战。一个包含 u32 和 bool 的联合体（union）。自然对齐是？
四。
我听到了四。大小呢？
四。
好的，我听到的都是正确答案。是的。
现在，我们不用联合体，改用结构体（struct）。自然对齐是？
四。
四。哦，我听到了一些不同的答案。大小呢？
八。
我听到了八。
四。
对齐是其中最大成员的对齐，也就是 u32 的对齐。而大小是这样计算的：你从每个字段开始，加上它的大小。所以，我们从 0 到 4。好的。然后我们把 bool 放在那里。现在我们到了 5。但是，我们现在到结尾了。所以，我们必须对齐到结构体的对齐要求。我们必须再加三个字节的填充（padding），砰，砰，砰，回到 4 的倍数。所以答案最终是 8。好的。
/* 生成代码，仔细甄别 */
// struct { u32, bool }
// 假设 u32 对齐为 4, 大小为 4
// bool 对齐为 1, 大小为 1
//
// 字段 | 偏移量 | 大小 | 结束位置
// ------------------------------------
// u32 a; | 0 | 4 | 4
// bool b; | 4 | 1 | 5
// ------------------------------------
// 结构体总对齐为 max(4, 1) = 4
// 结束位置 5 不是 4 的倍数, 需要填充到 8
// padding | 5 | 3 | 8
//
// 总大小 = 8
好的，我们继续。现在我们有一个结构体，包含 u32，u64，u32。对齐是多少？
八。
八，正确。大小呢？
二十四。
是的，这个你得算一下。是的，24，对吧？因为算法是，从 0 开始，我们先放一个 4 字节的。但接下来要放 u64，它需要 8 字节对齐。所以我们必须跳到偏移量 8。然后我们把 8 字节的放进去，到达 16。然后我们放 4 字节的，到达 20。但现在我们还没对齐。我们必须再加 4 字节才能回到 8 字节对齐。所以现在我们是 24。
/* 生成代码，仔细甄别 */
// struct { u32, u64, u32 }
// 假设 u64 对齐为 8, 大小为 8
//
// 字段 | 偏移量 | 大小 | 结束位置
// ------------------------------------
// u32 a; | 0 | 4 | 4
// (padding)| 4 | 4 | 8 (为了 u64 的 8 字节对齐)
// u64 b; | 8 | 8 | 16
// u32 c; | 16 | 4 | 20
// ------------------------------------
// 结构体总对齐为 max(4, 8, 4) = 8
// 结束位置 20 不是 8 的倍数, 需要填充到 24
// (padding)| 20 | 4 | 24
//
// 总大小 = 24
所以，仅仅通过移动这两个字段的位置，对吧，我们把两个整数放在一起。现在我们得到的是什么？对齐是多少？
同样的对齐。
大小呢？
十六。
是的，我们降回到了 16。
/* 生成代码，仔细甄别 */
// struct { u32, u32, u64 }
// 字段 | 偏移量 | 大小 | 结束位置
// ------------------------------------
// u32 a; | 0 | 4 | 4
// u32 c; | 4 | 4 | 8
// u64 b; | 8 | 8 | 16
// ------------------------------------
// 结构体总对齐为 8
// 结束位置 16 是 8 的倍数, 无需填充
//
// 总大小 = 16
现在，也许你的语言会自动帮你做这件事。你知道，有些语言会。这不是我的重点。我的重点是，在计算机上，它就是这么工作的。如果语言帮你做了，那很好。但这就是语言为你做的事情，对吧？
好的，我还有一个。我们再加一个 bool 上去。现在怎么样了？对齐还是一样，对吧？八。大小呢？
二十四。
哦，我听到了不同的数字。好的，我们又回到了 24。是的。
/* 生成代码，仔细甄别 */
// struct { u32, u32, u64, bool }
// 字段 | 偏移量 | 大小 | 结束位置
// ------------------------------------
// u32 a; | 0 | 4 | 4
// u32 c; | 4 | 4 | 8
// u64 b; | 8 | 8 | 16
// bool d; | 16 | 1 | 17
// ------------------------------------
// 结构体总对齐为 8
// 结束位置 17 不是 8 的倍数, 需要填充到 24
// (padding)| 17 | 7 | 24
//
// 总大小 = 24
这太疯狂了，对吧，因为一个布尔值是……（译者注：此处录音有些混乱，但大意是）……一个布尔值在信息论上只是一个比特的信息，但我们的结构体大小从 16 变成了 24，对吧？我们为了给结构体增加一个比特的信息，付出了 64 个比特（8字节）的代价。
我记得在 Mike Acton 关于面向数据设计的演讲中，他对某个结构体里的一个布尔值非常生气，好像是在 Ogre 3D 引擎还是什么里面，对吧？我记得看这个的时候就在想，是啊，他非常生气，还写了个脚本来打印出有多少比特被浪费了之类的。我当时就想，好吧，好吧，我懂了。但问题是，我到底该把那个状态放在哪里？因为我需要知道它是真是假。我到底该怎么办？对吧？
所以，我将尝试回答这个问题。
实践中的策略¶
接下来我们进入下一部分。这里是一些你可以在实践中使用的策略，用来处理一个结构体，用它来表示相同的信息——根据信息论，你没有丢失任何比特——但你减少了你的结构体在内存中的占用，对吧？
策略一：使用索引代替指针¶
我们稍后会回到布尔值的那个问题，但这里有另一个例子。这是一个带有一些指针的结构体。
/* 生成代码，仔细甄别 */
struct Example {
ThingA* a;
ThingB* b;
ThingC* c;
ThingD* d;
};
如果我们在一台 64 位 CPU 上运行，它的大小是 32 字节，对吧？如果在一台 32 位 CPU 上运行，实际上只有 16 字节。所以，一个有趣的观察是，尽管 64 位计算机可以有更多的内存，但默认情况下它们实际上也使用更多的内存，对吧？因为每个指针的大小都翻倍了。
但你可以做一件事：只使用整数。
/* 生成代码，仔细甄别 */
struct Example {
u32 a_idx;
u32 b_idx;
u32 c_idx;
u32 d_idx;
};
如果我们不堆分配这些对象，而是把它们放在一个数组列表（array list）里，然后用索引（index）而不是指针来引用它们，我们在 64 位 CPU 上就把结构体的大小减半了。所以，使用索引代替指针。这是你可以用来减小内存占用的一个技巧。
我还想指出一点。我们还降低了对齐要求，对吧？在这个例子里，对齐从 8 降到了 4。所以如果你想在第五个字段加一个 32 位的整数，你不会浪费任何空间，对吧？因为如果我们试图在另一个指针结构体上加一个 u32，我们会为 4 字节的填充付出代价。这里是 4 字节对齐，我们不需要为那 4 字节的填充付费。这是另一个好处。
但是，我有一个警告：小心类型安全。因为在指针的例子里，如果你用了错误类型的东西，你会得到编译错误，对吧？你传了一个 A，但本该传一个 B，编译错误。如果它们都是没有类型的整数，这就……你知道，你让调试变得更困难，并且可能引入一些有趣的 bug，对吧？所以你必须小心。也许你的语言有“具名整数”（distinct integers）。那可能会有帮助。Zig 没有。也许我们应该加上。我想 Odin 有。那你就在这个用例下用 Odin 吧。
我还想说，如果你把这个记下来，去网上搜一下“Handles are the better pointers”。有一篇 Flow of Woe（Andre Weissflog）写的博客文章，写得非常好。我只是告诉你，这里有件事你可以做。我不是在告诉你细节，比如“这是你如何用整数代替指针的方法”。对吧，这是“怎么做”而不是“做什么”。好的，这就是第一个。我们把一个原本 32 字节的东西，通过这个例子降到了 16 字节。
策略二：将布尔值存储在“带外”（Out-of-Band）¶
还有什么？好的，这是一个例子。我们回到那个布尔值的问题。
/* 生成代码，仔细甄别 */
struct Monster {
u64* data;
u32 hp;
u32 mp;
bool is_alive;
};
我们有一个指针，两个 32 位整数，然后是那个布尔值。如果我们看它的大小，是 24 字节，对吧？这是同一个例子，64 位 CPU 上是 24 字节，32 位 CPU 上是 16 字节。浪费了很多比特。我做了点计算，让你有个感觉。如果你有 100 个这样的对象，那就是 2.4KB。
这就是我当时在想的：我能做什么？我需要知道这个怪物是不是活着的。我不能直接删掉那个字段，因为我必须知道答案，对吧？
诀窍是：你可以把那个信息存在别的地方。
通过使用两个数组而不是一个，你把所有活着的怪物放在一个数组里，所有死掉的怪物放在另一个数组里。现在，那个布尔值，根据信息论，它仍然存在——它存在于“它到底在哪个数组里”这个信息中，对吧？但从内存占用的角度看，它消失了。
所以我们从 64 位 CPU 上的 24 字节，降到了 16 字节，对吧？如果我们再用上我刚才提到的另一个技巧，改用索引，那就降到了 12 字节。所以，这又是一个技巧。我们减半了，对吧？我们原来是 24，现在降到了 12。原本 100 个怪物占用 2.4KB，现在我们用 1.2KB 就够了。
这还有另一个好处。那就是，如果你有一个循环，循环里做的第一件事就是检查“如果怪物死了，就跳过”，对吧？你可以想象在你的游戏里会这么做。现在，你只需要遍历所有活着的怪物。而之前，在内存里，你在触碰那个标志位，对吧？你在做一个内存加载操作来检查 is_alive 的值。那可能会驱逐一条缓存行。但如果我们只看活着的怪物，我们就不需要为那个检查付出代价。没有分支，没有加载。这将导致更少的缓存未命中。
所以，将布尔值存储在“带外”（out of band）。这就是我第一次看 Mike Acton 演讲时没理解的那个问题的答案。
策略三：用“结构体数组”（Struct of Arrays）消除填充¶
好的，下一个。我给你一点时间来研究一下这个结构体布局。
/* 生成代码，仔细甄别 */
struct Monster {
u64* data; // 8 bytes
MonsterKind kind; // 1 byte enum
};
// 8 字节对齐，大小为 16 字节 (7 字节填充)
我们还是用怪物举例，但我会不断换掉字段来展示不同的想法。同样，我们有一个指针。现在我们有一个枚举（enum），告诉我们这是哪种怪物。我们这里有五种怪物或者说动物。嗯，是的，人类也是怪物。
在这个例子里，我用了 10000 个怪物，然后做了点计算，总共是 160KB，对吧？我们来看看这在内存里是怎么布局的。在内存里，我们将会有……这被称为结构体数组（Array of Structs），对吧？所以在第 0 个元素，我们有结构体的所有字段。然后，在到达第 1 个元素之前，我们需要让第 1 个元素对齐。所以我们必须插入 7 个字节的填充，才能回到 8 字节对齐。这样第 1 个元素才能被正确对齐。同样，对于第 2 个元素，在它后面我们又需要更多的填充，这样第 2 个元素才能被正确对齐。所以每一个元素都在为 7 字节的填充付出代价。
但有一个非常简单的技巧你可以用。与其用一个数组，元素是结构体，不如用多个数组，每个数组的元素是结构体的一个字段。 这被称为数组的结构体（Struct of Arrays）。
所以，你知道，如果你的编程语言允许你使用多维数组列表（multi array list）之类的，那只是一个五个字符的修改。同样的 API。现在，元素都是紧挨着的，对吧？我们有指针、指针、指针、指针……它们都是 8 字节对齐，不需要填充。然后我们有枚举、枚举、枚举、枚举……它们都是 1 字节，记住，1 字节的东西不需要任何对齐。所以我们通过把它们放进不同的数组，就消除了填充。
如果我们回到我们的例子，这是一行代码的修改，我们只是用了不同的数据结构。现在我们从 10000 个怪物占用 160KB，降到了 91KB，对吧？这可不是开玩笑的。这只是通过消除填充就节省了大量空间。
所以，用“数组的结构体”消除填充。这是一个技巧。
策略四：用哈希表存储稀疏数据¶
我们还能做什么？好的，这里是另一个。
/* 生成代码，仔细甄别 */
struct Monster {
u32 hp;
u32 x, y;
ArrayList<Item> items_held; // 最多 4 个
};
在这个例子里，我们有个怪物，有一些 HP，一些 XY 坐标。我们有一个它们的数组。现在我们有这样一个东西，每个怪物可以持有最多四个东西，你知道，也许我们用 0 表示空。我运行了脚本计算了一下，如果有 10000 个怪物，这将是 366KB，包括数组列表容量的开销，对吧？就是你超额分配的那部分。为什么我们现在要包括这个计算，马上就会清楚。
让我们做一个假设性的观察。假设我们注意到，在我们的用例中，90% 的怪物什么都没拿。它们持有的所有物品都是空的。
如果我们做出这个观察，我们就可以利用它。
现在我们把那个字段拿出来，把它存到“带外”，有点像我们对布尔值做的，对吧？但现在我们用的是一个表。只要我们可以用一个怪物的索引作为哈希表（hash map）的键，我们就可以把那些数据作为值放进去。现在它就是稀疏的了。
/* 生成代码，仔细甄别 */
struct Monster {
u32 hp;
u32 x, y;
// u32 items_idx; (或者类似的东西)
};
HashMap<u32, HeldItems> monster_items;
如果我们做个计算，我写了一堆脚本来计算这些数字，后面幻灯片结尾会有 gist 链接，所以如果你想，可以检查我的工作。你之后可以下载下来玩玩。但总之，我计算了一下，对于 10000 个怪物，我们从 366KB 降到了 198KB，包括这些数据结构的开销，对吧？节省是实实在在的。而且这还是在只有 10% 的怪物持有东西的情况下。
我还想指出，我们可以做不同的事情。你知道，也许是大多数怪物只持有一件东西。那你就可以把那件东西放在结构体里，然后为它们持有四件东西的特殊情况做特殊处理。你知道，你完全可以根据你的观察经验，以启发式的方式选择存储数据的方式。
好的，用哈希表存储稀疏数据。就是这个。
策略五：编码方法（The Encoding Approach）¶
我还有最后一个要给你。这有点像我带到这次分享会上的酷东西。所以，请花点时间来理解一下这个，因为我认为这将是……这有点像我做过的最酷的事情之一。我不会让你做太难的事情，但看看这个，这个很有趣，对吧？
// 策略一：Tagged Union
struct Monster {
u32 x, y;
enum { Human, Bee } tag;
union {
struct Human {
u32 hat;
u32 shoes;
u32 shirt;
u32 pants;
bool has_braces;
} human; // ~20 bytes
struct Bee {
enum { yellow, black, red } color;
} bee; // 1 byte
} extra;
};
我给你 15 秒钟喊出这个结构体有多少字节。
二十八？
我们听到了 28。还有别的猜测吗？我告诉你，不是这个。你可能忘了这个联合体是带标签的（tagged）。
三十二。
我听到了 32。好的，这个是对的。所以 Human 结构体是 20，Bee 结构体是 1。这里有一个带标签的联合体。所以有一个标签，对吧？那只是一个枚举。然后是载荷（payload）。所以是 32 字节。
这是在使用一种策略，我们为每种怪物使用相同的大小。对吧？如果我们可以把这些都放进一个数组里，它们每个元素都会精确地占用 32 字节。这有方便的属性。但我们在付出代价，你知道，如果我们有很多蜜蜂，我们也在为所有那些人类付出代价，即使对于那些不是人类的蜜蜂也是如此。这句话听起来很搞笑，但这是事实。
好的，让我们试试一个不同的策略。让我们尝试用不同的方式组织我们的数据。
// 策略二：Polymorphism / Object-Oriented
struct MonsterBase {
enum { Human, Bee } tag;
u32 x, y;
};
struct Human : MonsterBase {
u32 hat;
u32 shoes;
u32 shirt;
u32 pants;
bool has_braces;
};
struct Bee : MonsterBase {
enum { yellow, black, red } color;
};
在这里，我实际上采用了一种面向对象的方法，或者你也可以称之为多态（polymorphism）。对我来说，这两个词意思差不多。但我们重新组织了数据，使得有一个基类结构体，好的，那是标签、X 和 Y。然后每个“特化”版本只是增加东西。所以 Bee 增加了颜色，Human 增加了帽子、衬衫、裤子和是否有牙套。
这实际上是一个改进。如果我们这样做，我们将从 32 字节降到（平均）24 字节。对吧？这是一个改进。就一组对象使用的内存量而言，我们通过面向对象的方法减少了内存占用，对吧？但我们能做得更好吗？
所以，现在请特别注意我们需要表示的所有状态，因为在下一张幻灯片上，所有状态是如何被表示的就不那么明显了，但那正是重点所在。对吧？所以也许关注一下，比如 has_braces 会很有趣，还有比如蜜蜂的颜色，黄色、黑色、红色。
好的，开始了。
// 策略三：The Encoding Approach
enum Tag {
BeeYellow, // 13 bytes
BeeBlack, // 13 bytes
BeeRed, // 13 bytes
human_naked, // 13 bytes
human_braces_naked, // 13 bytes
human_clothed, // 29 bytes
human_braces_clothed, // 29 bytes
};
// 12 bytes
struct Common {
u32 x, y;
u32 extra_idx;
};
struct Monster {
Tag tag; // 1 byte
Common common; // e.g., hp, x, y (12 bytes)
};
// 16 bytes
struct HumanClothed {
u32 hat;
u32 shoes;
u32 shirt;
u32 pants;
};
// 稀疏数据
HashMap<u32, HumanClothed> clothing_map;
这就是我所谓的编码方法（encoding approach）。在这个例子里，有一个标签和一些公共数据。但我们回到了那个特性，即它们都有一个占用相同大小的公共数据部分，然后有稀疏数据存储在外部。我们有点像把之前的所有经验教训都结合到了这一个例子中。
你可以看到，对于蜜蜂，不再有颜色枚举了。蜜蜂的颜色现在被提取到了编码标签中。同样地，我们对人类有四种编码。我们选择以不同的方式表示裸体的人类和穿衣服的人类。我们选择以不同的方式表示戴牙套的人类和不戴牙套的人类。所以那个 has_braces 消失了，融入了编码标签。蜜蜂的颜色消失了，融入了编码标签。你可以看到我们“带外”存储的主题又回来了，对吧？
那么这对人类是如何工作的呢？我们来看看 HumanClothed。我们如何知道一个穿衣服的人类的所有信息？在这个例子里，你知道，Monster 是在一个“数组的结构体”里的多维数组列表里，对吧？所以我们在标签和公共结构体之间没有为填充付费。对于一个穿衣服的人类，我们会根据标签重新利用那个……哦，我不需要指针，我在图里标了。好了。所以 extra_idx 可以根据标签被重新利用。所以如果标签是 HumanBracesClothed 或 HumanClothed，我们知道我们必须查看 extra_idx 字段，然后在这个额外的、额外的东西里查找这个结构体。这就是它的工作原理。
然后，让我们计算一下大小。如果你想编码一只蜜蜂，一只蜜蜂是 13 字节，因为你需要标签、公共结构体，但就这些了。颜色……我们可以把颜色放在这里，但我们甚至没用这个，我们只是把颜色放在了这里（标签里）。所以我们甚至有……关于蜜蜂的额外数据可以存储，你知道，这不是一个完全满载、完全高效的数据结构。这个……这不是为内存占用优化的。这是为了能放进幻灯片里而优化的。让我们说实话，对吧？
所以，这是最终的结果。现在为了给你一个数字，我必须增加更多的假设，对吧？因为我们让东西占用多少空间取决于……你知道，你实践中实际拥有的东西。所以我们必须做一些假设才能报告：我们做得怎么样？对吧？这很好，因为我们学到的是，通过采纳关于你实际数据的启发式信息，你可以创造出更适合你的编码。
所以在这里，我们必须假设人类和蜜蜂的分布是均等的。我们必须假设……你知道，裸体和穿衣服的人类的某种分布。我觉得一个现实的裸体和穿衣服的人类分布是各占一半，你知道吗？我觉得这符合现实世界。所以，我们这样做，结果是每个怪物平均 17 字节。所以我们从 32 降到了 17，通过切换到编码方法，几乎又减半了。
是的，我想我已经讲过这一点了，但就是根据你的实际分布来选择编码，对吧？如果……你知道，如果裸体和穿衣服各占一半不是你的情况，那就选别的。也许大多数人类只是戴着帽子到处走，别的什么都没穿。在这种情况下，你会想要一个“戴帽子的人类”的编码，你知道吗？然后你就可以把帽子作为 extra_idx，然后戴帽子的人类就只占 13 字节，搞定，对吧？
好的，这就是编码方法。我们会在接下来的部分回到这个话题。所以，嗯，这就是五个……你知道，这就是我想和你们分享的五个策略。这就是可以带回家的知识。
案例研究：Zig 编译器¶
但我确实有一个案例研究。所以，你知道，我在 Zig 编译器里做了这些事情。我只是想报告我的发现，这样你就知道，你知道，这不只是我……你知道，在家里想：“哦，也许我可以把数据移来移去。” 我在一个真实的项目里真实地尝试了，我会和你们分享结果。嗯，但我得说，你知道，这个家伙（Zig吉祥物）很可爱，但既然我们在谈论性能，我们就得快起来。
这是 Zig 编译器的流水线。它非常标准。在最左边，我们有源代码，就是你输入到编辑器里的东西。右边，我们有机器码，就是 CPU 能理解的东西。中间这些东西是逻辑，是做事情的实现。这些东西是数据，对吧？源代码是数据，机器码是数据。但我们无法控制源代码的格式或机器码的格式。机器码是由硬件指定的，源代码是由语言规范指定的。但是，其他所有东西都是编译器内部细节，我们可以选择任何我们想要的数据，任何我们想要的数据布局。
所以所有我刚才讲的原则，我们都可以在这里应用。这就是编译器的核心流水线。所以如果这些东西真的有效，我们应该能看到好的结果，对吧？
我还想利用我正在记录这些东西的机会来解释一下，这条线左边的所有东西，都是按文件为单位完成的。不管你传什么标志，不管任何事情。同样的源代码会产生同样的 ZIR 数据。在线的右边，我们开始需要更多地……参与到编译器的事情中。它是按函数为单位的。当我们开始进入代码生成阶段，现在我们必须为 ARM、x86 做不同的事情，你懂的。
我还想预告一下，这个部分是 高度可并行化（embarrassingly parallel） 的。所以我们稍后会回到这一点。
让我们聚焦于词法单元（Tokens）。我们来看看如何将这些减少内存占用的策略应用到一个真实世界的项目中，我们的目标是词法分析源代码，并输出一个词法单元列表，然后这个列表可以被……嗯，用于编译器的解析。
我给你们看一个结构体。我现在不是在做练习，所以如果你没完全搞懂也没关系。我不会让你去计算这些。这更多是宏观层面的了。但我只是在报告：这是以前的样子，对吧？
/* 生成代码，仔细甄别 */
// 以前的 Token 结构体（64 字节）
struct Token {
TokenType type; // enum
u64 start_pos;
u64 end_pos;
u32 line;
u32 column;
// ... 可能还有解析后的字面量数据
};
以前是……你可能认得出来，对吧？这是带标签的联合体方法，所有东西都一样大。你可以看到我……那里有个枚举，有一些填充，对吧？这就是我现在看我的旧代码，然后想：“哦，现在我又看到错误了”，对吧？所以比如，那个枚举……这里有布尔值吗？可能。为什么我们用 64 位的 size？为什么我们要存储行号和列号，我们完全可以计算出来，你知道吗？就像……我几乎为我的旧代码现在看起来有多糟糕而感到高兴，终于，对吧？
所以，说得更简洁一点：
我们可以懒计算行号和列号，把它们去掉。
另一个点，让我们做一个合理的限制。我们只希望能够编译 4GB 或更小的源文件。如果我们做出这个限制，我们可以做出一个更好更快的编译器。所以让我们用更少的内存来存储那些位置。
另一个点，我们需不需要在编译器里存储一个词法单元的结束位置？我的意思是，我们可以再词法分析一次，对吧？我们可以再做一点点数学运算，避免存储一些内存。
还有，像在编译器里，词法单元就是像
*、/或者and关键字。我们甚至不需要重新词法分析它们。我们只要知道……我们基于它是一个and关键字就知道结束位置了。很明显是 3，对吧？最后，为什么我们在词法分析阶段就解析整数字面量？为什么我们解析字符串字面量？我们可以之后再做。成本是一样的，但现在我们可以通过不存储所有这些额外数据，让我们的词法单元小得多。
然后，是的，所以这是结果，对吧？我把我自己的所有策略都过了一遍，你知道，采纳了我自己的教训。我们从每个词法单元 64 字节降到了 5 字节。
/* 生成代码，仔细甄别 */
// 现在的 Token 结构体（5 字节）
struct Token {
TokenType type; // 1 byte
u32 start_pos; // 4 bytes
};
它就是……它在文件里的什么位置，以及在文件那个位置上的是什么东西。这就是现在的 Zig 词法单元。所以是的，它小多了。我们有很多词法单元，对吧？你可以想象，你源代码里的每个标识符，每个星号，每个斜杠，都是一个词法单元。所以当编译器工作时，每一个都只占用 5 字节，而不是 64 字节。就是这个。
接下来我们看 AST（抽象语法树），然后我会给你们看一个基准测试，然后我们再看下一个。
好的，AST。我再给你们看一个结构体。这是以前的样子。实际上，这是我们今天发布的编译器里仍然的样子，所以这个还没有被……可以说是修复。
/* 生成代码，仔细甄别 */
// 以前的 AST 节点（120 字节）
struct AstNode {
NodeType type; // enum
bool some_flag;
u32 line, column;
// ... 很多指针和联合体 payload
};
这又是带标签的联合体策略，用于 AST 节点。你可以看到我有个布尔值在里面。你可以看到我有个枚举在里面。行号和列号在干嘛？它们总是不停地回来。就像我当时非常偏执，总怕我会忘记东西的行号和列号，但你完全可以懒计算它。所以是的，再一次，别再……别再记忆化那些我可以计算出来的东西了。
对吧？还有，我当时还存储了……就像，指向哪个词法单元的链接，或者说哪个 AST 节点指向哪个，所有这些。你实际上……它是一个树形结构，所以你只需要存储一个。这与其说是面向数据设计的东西，不如说是我意识到我可以再次计算某些东西，计算某些东西而不是记忆化它，对吧？这个要点也是如此。
然后，好的，编码策略要回来了，对吧？所以我们开始了。我把新的放上来。新的那个……我做了，我写了一个有点 hacky 的脚本，对两种情况都运行了整个标准库的测试，然后就……计算了一下每种有多少，再除以总数。所以这些数字实际上非常准确。
我们从 120 字节降到了平均 15.6 字节。 你知道，它是平均值，因为现在的节点每个都占用不同的大小。
同样，这不完全是实际的样子，这是为了能放进幻灯片而优化的。但它就是编码策略。所以你可以看到有一个主词法单元。所有这些都是用“数组的结构体”存储的，所以我们没有为填充付费。有一个左手边和右手边，根据标签被重新利用。重点是我们有多种编码。一个变量声明被用三种不同的方式编码。一个 if 被用两种不同的方式编码。一个 while 被用两种不同的方式编码。然后就是……你知道，有任意数量的这些编码，取决于我们启发式地发现我们需要用一种高效的方式来表示什么。
好的。我给你们看了这两个，我实际上也收集了一些性能数据。所以它有帮助吗？是的。 在我只做了这两项改动，还没改任何其他东西之后，我只测量了……只是解析一大堆文件的差异。这是我得到的数据。墙钟时间（Wall clock time）是关键，对吧？如果你得到了 22% 的墙钟时间提速，这是我非常满意的事情。 所以，这很好。
但我们还没完。编译器的流水线里还有三个阶段。我会讲讲这个。我……我时间不多了。所以我不会讲这个。我也不会讲这个。 suffice it to say，同样的策略也有效。但我们来看看下一个阶段，ZIR（Zig 中间表示）。
这个阶段会接收一个语法树，然后输出一个……还没有做类型分析的中间表示（IR）。这是我们以前有的。以前我们有……它基本上是多态，你知道，面向对象编程，那套东西。所以每个节点根据它是哪种，会有不同的大小。用指针互相引用。你知道，一种规范的……在这个例子里，标签。它不是编码策略，对吧？有一种规范的方式来表示所有东西。从可维护性的角度来看，这很好，但……对于内存占用来说，不那么理想。
这里有一些观察：
不是每条指令都需要一个源位置。有些可以从……其他上下文中推断出来。
源位置可以是
u32的索引，指向词法单元数组或 AST 节点。所以，这将把那个的大小减半。还有，抱歉，还有这个。以前它是一些规范的源位置的东西。现在因为我们在做……现在因为我们在做编码，编码告诉了你源位置的含义。所以编码可以说，在这种情况下，源位置是一个词法单元索引。或者在这种情况下，源位置是一个节点索引。
然后最后，这是指针到索引的事情，对吧？所以现在对其他指令的引用是……它们的大小减半了。对吧，就是这个。
最后，引用可以编码简单的值。如果你只是在谈论……你知道，一个
true，字面上的值true或false，我们不需要创建……一整条指令来表示它。对true或false的引用本身，在 IR 格式里，可以有一个专门用于此的枚举标签。我会快速带过那个，因为我不想超时。
但总之，之前是平均每个 54.0 字节。哦，抱歉，我们还要做一个观察。我们显然要用编码策略，这是我一直在说的。所以我们要从多态策略表示内存，转换到编码策略。我们从平均 54.0 字节降到了平均 20.3 字节。 同样是平均值。你知道，演讲最后下载代码，检查我的工作。我写了一些脚本，对整个标准库运行，来计算出这些平均值。
这就是编码策略。我必须把它简化很多才能放进幻灯片，但……是同样的东西，对吧？就是编码。你用多种不同的方式来编码，以表达所有东西。这里我们可以看到 strong 和 weak。那是一个布尔标志，被……你知道，放进了编码标签里。我还能指出什么？我想我不需要再指出别的了。就是编码策略。和我给你们看的其他三个例子是一样的。我们从 54.0 降到了 20.3。
但我想指出的是，每一次这些改进，我们都把每个对象的大小减半或更小。通过这些技术，这个东西使用的内存量急剧减少。
所以……它奏效了吗？你知道，用更少的内存是否会导致更少的缓存未命中？经验上来看，是的。 在这个例子里，它给了我 39% 的墙钟时间减少。这太夸张了。而且这是在我刚才报告的，只为另外两个做的改进之上的。我猜我内存里这种对象的数量比另一种要多。所以，这奏效了。在一个真实世界的项目里，它奏效了。如果你用了这些技巧，你会得到更快的代码。
现在，我知道我预告了那个高度可并行化的事情。所以我还有一件事要报告。那就是，当我着手……我实现了一个线程池，抱歉，是 king 实现了线程池，我只是从他那里复制过来了。谢谢。然后我……我让它把做这个高度可并行化部分的工作分配出去……你知道，在线程池上。这是在我的……戴尔 Inspiron 上。这是一台相当强劲的笔记本，对吧？是一台好笔记本。当我只对流水线的这个部分做这个时，结果是每秒 890 万行代码。
那可真是他妈的快。
还有一个附赠的好处。ZIR，对吧？这个流水线部分的输出，现在只有四个数组。一个标签数组，一个公共数据数组，然后像是一个额外数据数组，还有一个字符串表。就是数组。没了。把它保存到磁盘和从磁盘加载，简直是愚蠢地简单。Posix 上有一个系统调用叫 writev 或 readv，你实际上就是把数组给操作系统，它一次性就把所有事情都做了。就像，一个系统调用就能把这些保存到缓存，或者从缓存加载。所以，就像，这个数字，这个包括了……把数据保存到缓存，对吧？就像，我们在这里和文件系统交互，以避免下次再做这个工作。
提醒与进展报告¶
不过有个提醒，对吧？我只在谈论这个橙色的部分。而编译器流水线的这些部分可不是开玩笑的。我知道……那是 Walter 吗？是的，我知道你现在就在想这个，对吧？
所以我想强调一下这边的区域，因为我给你的那个数字，会下降很多，对吧？如果我能让它保持在一百万以上，我会很高兴。但显然，如果流水线的这些部分更难，那个数字就会下降。那个数字只针对橙色部分。我只是想说得非常清楚。
但让我……让我放大一点，告诉你们，好的，我们现在到哪一步了？进展如何？我做了这张幻灯片，这样你们可以大致了解。我给你们那个数据的部分，那部分已经完成了。好的，但我们还在做后端。所以，嗯，对于自举（self-hosted）编译器，我们大约有 35% 的行为测试通过了。所以每次我报告这些改进时，我谈论的都是在自举编译器里做的改进。这和你今天下载 Zig 得到的不一样。如果你今天下载 Zig，你得到的是慢的那个。
所以如果你对这个感兴趣，还没试过，我实际上有点建议你等一等。也许等到这些数字上升到……我不知道，90% 左右。90% 左右。你知道，等到我们有一个版本，把这个新代码作为默认发布，然后再去体验。我只是想非常坦诚地报告这里的进展。
我想……是的，我想我们从这里继续。
总结¶
让我们总结一下。
这是从内存角度看的计算机的样子。 把 CPU 缓存加入到你对计算机的心智模型中。
CPU 很快，内存很慢。
找出你在内存里有大量相同东西的地方，然后让每个东西的大小变得更小。
有很多方便的技巧你可以用来减小东西的大小：
用索引代替指针（小心类型安全）。
将布尔值存储在“带外”。
用“数组的结构体”消除填充。
用哈希表存储稀疏数据。
用编码代替多态。
而且，你知道，正如 Zig 编译器所展示的，这是值得的。这些技巧有实际的、真正的好处。
嗯，就是这样。这是我的演讲。谢谢收听。
（听众鼓掌声）