《狂人》的元编程(2012)

好的，本系列之前的帖子实际上旨在传达有用的技术信息：假设您真的想编写一个网格生成器，那么其中肯定有一些有用的部分。

这不是这些帖子中的一个。事实上，这几乎是完全相反的：一个疯狂的策略，尽管困难重重，但实际上是奏效的，然后却产生了惊人的适得其反。我们提前知道会发生这种事，但我们绝望了。我不认为我们从整件事中学到了任何有用的东西--但这是一个很酷的故事(以一种非常书呆子的方式)，所以为什么不呢？把它当做一个(季节性合适的！)。复活节彩蛋。

这是一个真实的故事发生在2004年3月底和4月初-不到两周后的2004年，我们计划发布96K第一人称射击游戏“.kkrieger”。虽然这是一个很好的技术挑战，但就游戏方面而言，这是一个彻底的失败(主要是因为没有人真正深入地关心这一方面)。不过，这不是这篇文章的目的--关键是我们也差一点就错过了96K的限制。

任何自尊的4k介绍、64k介绍或其他大小受限程序的启动方式都太大了。我没有做足够的4K来给你一个数量级的估计，但我们的大多数严肃的64K在他们应该发布的几周前都在70-80K左右。最后两周通常会变成疯狂的匆忙，想要同时完成这件事(把所有的内容都放进去等等)。并使其符合尺寸限制。做这两件事本身就是一个真正的挑战。同时做这两件事既有极大的压力，又让人精疲力竭，而且到了最后，你基本上需要休假了。

无论如何，(广义地说)有3个不同的步骤可以确保你得到小的代码：

建筑。基本上，设计代码的方式要使它变得很小。准确地知道它包含了什么，保持它的模块化，并确保算法是适当的。以正确的方式存储数据，并与您的后端打包程序一起工作，而不是与之对抗。不过，这一切离发布还有两周多的时间--如果你不及早做好这一部分，你就不可能及时修复它。

驱逐压舱物。将会有一整条路径的代码根本不会被使用。如果您的数据中没有一个圆环，那么包括生成它的代码就没有意义了--如果只有一个圆环，您也许可以用现有技术中的其他东西来替换它。你明白我的意思。如果您至少对内容有基本的统计信息，那么这一步相当容易，而且它在短时间内会带来巨大的收益(在64K的上下文中，通常是几千字节的工作时间不到一小时)。

细致入微的工作。这就是事情变得一团糟的地方。它基本上归结为转储关于代码中所有函数的统计数据，找出哪些函数比应该的函数大，以及您可以做些什么来使它们变小。很多人盯着反汇编清单，试图找出编译器在哪里生成大代码以及为什么。还有，花很多时间盯着内容，想知道有没有什么捷径可以让这个特别的介绍变得更小。这是您开始切换到另一个分支(或者至少将所有更改都包装在#ifdef中)的地方，因为您将引入错误，并且在它结束时，部分代码将被破坏。这也是一项缓慢的工作--当最初的简单目标被关闭时，假设没有其他事情可做，我可以得到更小的32位x86代码(在64k的介绍环境中)，最多每天大约300-400字节。

基本上，在步骤2结束时，您已经非常清楚还有多少工作要做，尽管您对这些工作是什么几乎一无所知：)。请注意，这与速度优化有很大不同。对于速度优化，您通常愿意对数据流进行重大更改以减少工作(至少在重要的地方是这样)，并且将精力集中在热点上。对于大小优化，热点几乎是无关紧要的；当然，可能有一个地方，一个大的数组最终被代码初始化，而不是被存储为数据，修复这类事情通常很容易，也很有趣，但大多数情况下，“大小配置文件”中的热点是完成实际工作的地方。除非您实际做的是完全不必要的工作，否则优化速度并不会使您的代码从绝对意义上变得更小，它只会将复杂性(因此也就是大小)移到可执行映像中的其他地方。

速度微优化就是盯着循环，想办法让它们变得更紧。大小微优化就是盯着大量的代码，想办法要么完全摆脱它，要么与其他足够相似的东西共享代码，要么利用“区域效应”来实现特定于体系结构的小技巧。例如，在x86上，您可以对struct字段重新排序，以便最常访问的结构字段(根据不同的实例，而不是它们最终被执行的次数)最终位于基指针的127字节范围内，因此使用8位移位。诸如此类的事情。

当我们第一次运行kkrieger的“播放器”版本时，压缩后的可执行文件大约是120K字节。当我们扔掉所有的压舱物并完成数据格式的调整时，我们已经降到了大约102k，但这仍然是一些内容(以及游戏的大部分内容--并不是说一开始就有那么多内容！)。失踪。在发行前两周多一点的时候，我们开始(或多或少是全职)在Chaos‘s Place会面，把一切整合在一起--请注意，Chaos、我和Gizmo(我们的两位艺术家之一)也是Breakpoint的组织者，也就是kkrieger即将发布的派对，所以我们也不得不早早到达派对地点，准备好一切，等等，这让事情变得复杂起来。所以我们知道可能还有一周半的时间，前面提到的狂热开始了-因为很多艺术仍然不完整(其中一部分在小的“Player”可执行文件中被破坏了)，游戏代码中有漏洞(最重要的是，一些严重的冲突问题，我们从未修复过)。工作繁重，睡眠却很少。在某个时候，Chaos竖起了一个(手绘的)标志，上面只写着“98304”，这是我们的目标大小(以字节为单位)-96(二进制)千字节。

上映前一周，我们的数据是10万。人们开始意识到：以我们目前的速度，这是行不通的--除非我们愿意丢弃大量内容，而这是我们真的不想要的。我们需要改变策略，尽快想出另一个计划。

关键思想是，在“细节工作”步骤中，如果您愿意真正将代码专门用于内容，那么可以做的事情有很多。就像在中一样，从字面上丢弃给定内容永远不会采用的所有代码路径。在最终交付的可执行文件中，所有内容都是从相同的源数据按程序生成的，播放器中的代码只需要为该数据文件工作，而不需要为其他数据文件工作。不过，这有一个很大的问题：手动准确地确定哪些代码路径实际上是必要的，这是一个时间沉没，一旦开始沿着这条路走下去，您就真的不能再接触数据了。

简而言之，手工操作不仅是垃圾工作，而且非常易碎--这就是为什么我们以前的64K从来没有这样做的原因。然而，在这种情况下，我们绝望了，我们真的不知道还能做些什么来在一周内减少4千字节。因此，我们做了任何有自尊的程序员在这种情况下都会做的事情：我们决定编写一个程序来为我们做这件事。

我们的想法是这样的：我们决定编写一个新的工具，名为“lekktor”(我知道，总是使用双k)。它取材于德语单词“lektor”，意思是编辑者，就像编辑书籍的人，而不是文本编辑者。Lekktor将使用该程序，并为其提供详细的代码覆盖率跟踪。然后，在第二遍中，它将获取在第一遍中收集的代码覆盖信息，并删除所有从未采用的路径。因为所有的内容生成都是确定性的，并且在程序开始时发生，所以您只需要在指令插入模式下启动游戏一次，获取转储的覆盖信息，然后再次运行lektor来编写“死掉的”源文件并重新编译。

听起来比较简单，对吧？唯一的问题是它涉及到解析和处理C++源代码。

Chaos最初的想法是从一个源代码精美的打印机开始(想想GNU缩进和类似的程序)。请注意，上述类型的源代码处理实际上并不关心声明和类型，这是C++中最棘手的两个部分。实际上，要进行这种处理，只需检测和解析某些类型的语句和表达式：if、Else、for、While、Do和&；&；、||和？：运算符。我们认为，一个优秀的源代码打印者至少应该了解那么多关于C++代码的知识，然后我们可以在关键位置添加一些额外的令牌，这样我们就可以做好准备了。

唉，我们花了一个下午的时间研究了不同的这样的包，他们中没有一个人真正对C/C++代码有那么多的理解；他们主要是试着凑合使用正则表达式。它不会飞到我们需要的地方。最后(2004年复活节前的那个星期天)，我们没有发现任何有用的东西--我们有一个计划，但没有办法实施。

就在那时，混乱决定：“那么，我想我需要编写我自己的C++解析器了”。

什么，你以为我用这篇文章的标题是在开玩笑吗？请注意，我们总共有3天的时间来做这件事，我们全力以赴做这件事；如果这件事没有成功，我们就完蛋了。幸运的是，它确实奏效了。说大也大吧。

事实证明，这并不难，只要您a)只需要大致地做这件事，b)只需更改您试图解析的程序来解决问题，c)愿意采取一些捷径来显著简化问题。例如，我们不需要能够解析模板声明；事实上，我们只解析了未经预处理的C++源文件，完全跳过了头文件(我们在头文件中没有太多代码，所以没有理由这样做)。这意味着我们需要修改代码的一部分，以便#ifdef等不会扰乱控制结构。例如，像这样的东西。

IF(条件) { //... } #ifndef is_troo 否则(条件_2) #其他 否则(条件_3) #endif { //... }。

这是不允许的--损失不大，但你明白了：我们完全愿意以相当简单和机械的方式重新格式化代码，如果这意味着我们能得到我们的代码覆盖率分析的话。

第二天早上，混沌不得不从“假期”中抽出时间，去柏林参加一个工作会议。这意味着在每个方向都需要大约2个小时的火车车程；他随身携带了笔记本电脑、一副耳机和一本《可重定位的C编译器：设计与实现》(A Retargetable C Compiler：Design and Implementation)。到下午晚些时候他回来时，他已经有了一个非常粗略的解析器，可以“理解”简单的函数-当然，还可以正确地缩进它们：)。当晚我们入睡时，我们已经让它在目标代码库的某些部分上工作了。

在接下来的几天里，我将省去你的详细内容；这些细节对这个特别的故事几乎没有什么补充作用。我们最终使用lekktor节省了大约4.5k，达到了我们的目标。当然，我们的野心也增加了一点；我们有一个小的介绍片段，但我们愿意去掉它(因为它真的与游戏无关)。一旦我们离得很近，我们就一直推着，试图也保持开场白。但这是一个很高的要求--这基本上是游戏中使用类似场景的功能的唯一序列，所以它引入了很多其他东西都不需要的代码，而且花费的不仅仅是数据。当然，还有大量的最后一刻的内容调整和(最终徒劳无功)的尝试来清理破损的游戏性。

在比赛开始前2小时，我们有了一个没有INTERO的版本，符合96K的限制，而一个有INTRO序列的版本，超过了限制的0.5K。因为这一周我们还有其他工作要做，所以我们主要是通过(小心地)将越来越多的源文件转移到lekktor来实现这一点的。我们有一个神奇的#杂注，可以用来打开和关闭代码区域的处理；慢慢地，我们不断深入整个项目。我们不仅开始对完全确定的内容生成代码进行“lekktoring”，还开始对低级初始代码、3D引擎的一部分以及游戏代码的一部分进行“lekktoring”。我们试着小心翼翼地正确标记“禁忌”部分，但我们在巨大的压力下工作，同时还有大量的其他事情要做，而且没有足够的睡眠，所以我们在一些地方变得马马虎虎。

突然，比赛开始前一个半小时(截止日期过后几个小时--成为组织者…的好处)。，Chaos笑着向我走来，说他已经对代码做了一些重构，并重新运行了Lekktor，现在我们确实有足够的空间来保持介绍序列了！不用说，我们欣喜若狂，把整本书和自述文件一起打包，拉上拉链，然后发货(可以这么说)。

当然，在这一点上，你可以想象实际发生了什么。因此，为了我们共同的娱乐价值，下面是他在试运行期间没有触发的事情的完整清单(据我所知)，这些东西后来从发布的版本中汇编出来：

我们使用阴影体积；单面模板卡片(两次通过)或双面模板卡片(一次通过)有阴影路径。我们正在录制的卡片(GeForce4Ti)有双面模板，所以单面模板代码没有进入发布的版本中。哎呀。(这一次与试运行期间的“用户错误”无关)。

在开始时的菜单中，向下光标有效，但向上光标无效(在测试运行期间，他从未在菜单中点击向上光标)。

开始时的小敌人可以击中你，但是他没有被敌人的子弹击中，所以在发布的版本中，敌人的子弹不会造成伤害。

部分冲突解决代码消失了，因为它从未在试运行中使用过。

不管它的价值是什么，这可能是230字节左右的代码。嘿，考虑到我们几乎删除了随机的if，这实际上是一个相当短的列表！：)。

老实说？我不太确定。然而，这个故事本身有一个很好的诗意正义，我保证这一切真的不是我编造的--所有这一切都像我描述的那样发生了！

事实上，我们一开始就知道这是个坏主意，但另一方面，这是我们曾经有过的最好的坏主意之一：)，有些错误是值得犯的(一次)。混沌和我都很清楚，我们实际上是在乞求这样的事情发生，比如魔术般丢失的碰撞代码。但我们绝望了，我们真的很想在断点释放克里格，我们做到了，所以最后一切都解决了。Kkrieger是一个糟糕的游戏，不管有没有上面提到的错误；至少这样我有一个很好的故事可以讲。

嗯，还有一个跑路的恶作剧。在.kkrieger之后的许多场合，当我们在做介绍，进入大小优化阶段时，我们中的一个人会建议“好吧，你知道，我们可以再挖一次莱克托…。”。然后我们都会颤抖，只是摇摇头。