《狂人》的元编程(2012)

2020-11-13 17:48:14

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

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

这是一个真实的故事发生在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之后的许多场合,当我们在做介绍,进入大小优化阶段时,我们中的一个人会建议“好吧,你知道,我们可以再挖一次莱克托…。”。然后我们都会颤抖,只是摇摇头。