The world at your fingertips — 天涯明月刀幕后（10）回收

2018-04-03

https://zhuanlan.zhihu.com/gu-yu

前文回顾：The world at your fingertips - 天涯明月刀幕后（9）工具

垃圾回收

引擎中，对象生命周期也要更好的管理起来。

整个项目使用的旧引擎框架，对于对象生命周期的管理，是比较简单的，依赖于引用计数。我一直不太喜欢引用计数，因为它对指针加入了额外的内存开销，同时在指针操作上，加上了额外的引用计数的操作，再加上需要考虑多线程操作指针时刻的引用计数安全性，也会带来额外的性能开销，还会引起循环引用导致的内存无法释放问题。

所以之前的几个版本都没有好好处理对象生命周期，对象全依赖于程序员手工创建和释放，反正demo规模小，能扛住。但这次要做的demo版本规模稍大，是时候好好管理这一块了。

我开始做一个垃圾收集系统（Gabbage Collection），也是比较简单的Sweep and Clean体系。我们把对象分成Managed和Unmanaged两部分，对于Unmanaged的那部分对象，程序员必须自己去管理。

对于managed那部分对象，主要就是游戏内用的对象，由于我们已经在整套序列化体系中标注出指针，那么扫描指针变成一件非常简单的事情，我们在整个游戏循环后，线程安全的地方，做一次Sweep，把被Reference到的对象标注出来，把其他没有被引用的对象放到pending delete的队列，过几帧后就可以安全的删除了。

这样做，带来了很多好处。

换关卡等操作变得极其简单，只需要把整个关卡的根指针赋值NULL，然后做一遍垃圾收集工作，所有关卡里面的无用对象，由于丢失了到根结点的引用路线，就被删除了。

更有趣的是，如果我们有足够的内存，那完全可以先加载一部分新的关卡，然后再删除旧关卡，这样新旧关卡共用的那部分object，就不用被删除和重新创建，仅仅需要reset一下内部的变量值，就可以自然地被重用，节约开销。

考虑到网游一般都是大地形streaming，我们事实上不停在做物件删除和重建，垃圾系统在整个过程中，能最大限度重用新旧系统共用的Object，减少IO和内存分配的压力。当然这个问题Reference count系统也可以做到，不值得特别展开。

平时的指针操作都没有性能开销，只在垃圾回收的时候才有少量开销。这一点听上去似乎不重要，我们只是把一部分开销从一个地方移动到了另一个地方。但实际非常重要，游戏引擎中，性能的可预测、可管理极其重要。在引用计数系统里面，整个系统是均匀的变慢，你并没有太好的方法去优化它。但在垃圾回收系统里，我们平时运行是不需要引入这个系统的，我们只是定期运行垃圾回收系统，即使有较大的开销，也是一个可控的情况。对于集中的开销，后续我们还开发了分帧的垃圾回收系统，可以在一个固定分配的时间片预算里面，进行GC的操作，这样我们就可以顺利抹平性能消耗的尖刺，达到平滑的帧数。

垃圾回收系统还带来了更多有趣的用法。

考虑到多线程框架中，逻辑线程和渲染线程往往耗时不一样，这些线程在同步点上有可能会互相等待。有了我们的比较通用GC时间片系统，我们可以在两个线程互相等待的时候，在空闲cpu上插入少量GC的工作，让它们尽可能多的利用足cpu时间。反正GC标注工作是一个循环往复的工作，再多的CPU都是有价值的。

再比如在Editor中的对象Copy/Paste，本来并不是特别容易做的一件事情。对于没有外部引用对象的情况，相对比较简单，直接复制一个就好。但如果一个对象还引用了别的对象，就会比较复杂。有几种情况需要分开讨论。一种是引用的对象，从属于这个对象，这种情况下我们需要把这个对象以及引用对象一起复制一份，并且让旧的对象引用它，这个我们称为Deep copy。另一种情况是引用对象是公共的对象，比如关卡中其他物体，这个情况下，我们不能简单的复制这个新的对象，而是直接引用它，这个我们称为Shallow copy。考虑到每一个对象可能都会引用其他对象，我们的整个过程必须是递归的选择shallow copy和deep copy。好在所有的引用都已经用垃圾回收系统标识出来，仅仅需要根据引用数据的类型，打上shallow copy或者deep copy的标记，就可以比较简单的做到这个事情。

垃圾回收系统也可以对磁盘上冗余资源文件做清理，所有访问不到的对象就是没用的，游戏打包的时候也不需要带上那些对象。在编辑器中做一次全关卡的GC操作，就知道什么对象有价值，什么对象没有用，输出列表后，把无用的对象一一物理删除，就完成了磁盘资源清理。

当然没有免费的午餐，GC系统的缺点也是有的。回收体系变得更复杂，程序员的理解成本更高了。而且日常开发过程中，有不少开发规范要遵守，对新加入团队的程序员来说，学习门槛变高了。早期不够完善的时候，也可能引入一些随机crash，非常难查。

总体来说我对新系统还是很满意，垃圾回收体系对于简化对象管理、性能控制等各方面，都有很大的好处，也提供了不少side effect，可以帮助工具集做得更好。

GC优化

说完垃圾回收，说一下后续做的一次优化。

垃圾回收系统启动一次，往往要数十毫秒，可能引起性能的波动。为了降低性能的波动，我们做了分帧的回收优化，每一个frame分配了3ms供系统使用，垃圾回收系统每帧都跑，用满3ms就退出，不再进一步消耗性能。经过多帧的垃圾回收，终于完成mark所有对象的时候，我们就把系统中的多余对象做上标记，过几帧全部删除。之所以要过几帧删除，主要是考虑多线程问题，还有可能有其他线程正在使用这个变量。

如果GC能跑快一点，我们就能更及时回收垃圾，对工具效率和内存管理也会有一定的收益。

当时正值春节前夕，同伴们纷纷离开了办公室。每逢佳节，手头需要做的杂事瞬间收敛，不再需要为琐事奔忙。既然大家都退散了，还有半天就要休假，那就不考虑长远的工作，抽空看看代码，看有什么可以优化的吧。

我看了一下内存统计的log，注意到每次GC，都会有30000多次的内存分配，这个显然太多了，从那里入手看看吧。

要优化，先建立测试体系。我在一个指定的场景，Loading完地图，等待固定的帧数，做了一个GC，且不分帧，一次做完，尽量确保测试条件稳定。然后启动GC，自动输出一个垃圾回收到结束后所需的时间。做完这个，我统计了一下当前GC的时间，作为基准参考。然后我就禁用了编译器对代码的优化，便于调试，再另外输出一个GC时间，作为优化的起点，开始下一步的优化。

整个GC系统分成三部分，首先清理所有对象池中的对象标记，确保所有对象的标志都是干净的，然后循环对所有根节点对象进行序列化操作，通过指针对象访问到其他对象，一一打上标记，最后再遍历一遍所有对象，没有标记的对象都是可回收的对象。

原始的版本，关闭编译器优化后大约需要19.6ms。

第一想到的是，内存分配是不是太多了，一次GC有33000次内存分配，原因出于在遍历指针对象时，会随手把后续需要遍历的对象push到一个list里面，这操作会导致内存重新分配。由于这个容器需要push_back，也需要pop_front，所以无法使用vector，我随手把容器类型改成了deque，分配操作变成了26000次，但再尝试GC，依然要19ms，这次尝试顺利的失败了。

deque还是分配太多，我们更简单点，直接做一个定制容器，一个resize，一次分配好需要的内存，push_back和pop_front就会变成很简单的指针加减操作。GC结束后统一释放这块内存即可。马上分配操作的时间变成了15500次，时间有19.6ms变成了16.6ms。

本想回家休假了，但初战告捷，自然要乘胜追击。

继续看内存分配问题，还是有15k的内存分配，来自于一个辅助类的clone操作，这个操作需要分配很少的内存，在同一个函数里先分配，用好就在同一地方释放。这个有点浪费，我想从算法角度处理一下。但我看了一下算法，这个clone类可以隐藏template的细节，简化复杂的模板代码，所以也不容易改掉。对于local使用的少量内存分配，用动态内存分配太浪费了，我用_alloca的方法，直接把内存分配在stack上，简单快速，且无需释放，函数退出的时候自然就回收了。三行代码一改，内存分配直接下降到2次，时间从16.6ms变成了13.8ms。

继续努力，我找到一个频繁被使用的struct，里面比较复杂，既不是POD，又有一些不必要的字段。我先去掉了default的constructor，再去掉了一个没用的字段，希望memcpy的时候能少copy一点内容，profile一下，效果寥寥，只有0.3ms的减少，可以忽略。

最初内存分配的罪魁祸首被干掉，我开始没有方向了，胡乱尝试了一下，把对几个容器的操作inline化，无效。

还是要耐心看看代码，我又注意到了，在遍历指针的时候，我们先peek一下队列，取出首部的指针，然后处理这个指针，最后把这个指针pop出来。这个是冗余操作，既然这个指针迟早要死，为什么不在第一时刻死呢？我顺手在自定义的容器里面处理了一下，把peek去掉，我们直接pop指针，取出这个pop的指针做后续处理。进一步看，这些指针会被加入待处理队列，留给后续处理。但并不是每一个指针都要加进去，如果这个对象的指针已经被处理过，就不需要了。我加上一个检查flag的操作，确保一个指针指向的对象，只在没有处理过的时候才加入，时间很快从13.5ms降低到了10.8ms。

进一步看，每一个对象和结构都会被完整扫描，但其实并不需要，有很多结构里面没有任何指针，这些结构并不需要被处理。在生成对象数据元信息的阶段，其实我可以在宏里面做很多预处理，如果一个对象完全没有指针，我完全可以在预处理阶段标识出来，有了这个标识，我就可以知道这个结构没有指向外部的引用，就根本没有必要扫描相关的结构。我可以直接跳过这个结构扫描。做完改动，10.8ms又变成了8.5ms。

后续的思路又开始模糊，还能进一步优化吗？没有什么能够阻挡，一个进入心流状态的人，当然要乘胜追击。

我对待处理队列做了很多微调，有进步，也有反复，对很多GC以及对象本身的标志做了细致的管理，确保尽可能不把无需处理的对象加入GC系统，说起来简单，做起来还是很繁琐的，主要是需要相当深度的测试，确保没有破坏整个游戏，工具集也需要看一下，也许随手调整了一个标志，就有可能导致GC整个系统失败，进而会有内存泄露。当然这个工作主要还是体力活，脑力损耗不大，正好逛逛办公室，心情，一般都是随着办公室人数的增多而成反比，今天人不多，心情挺好。做了这些精细调整后，时间消耗从8.5变成了7.2ms。

我在细致调整的同时，也随手加了一个新的统计信息，关于所有的引用对象和指针被访问了多少次的，从这个统计里面，我注意到了我们有17万次的引用访问。这里也许有戏，对象数量和访问数量有点偏多。

找到了新的线索，我又来了精神。测试环境下大约有18000个对象，但我们访问了17万次引用，有点多。我加了一些log代码，dump出所有reference信息调用的时候，都是在什么对象的什么引用上面，然后我就发现我们有大量的策划使用的静态表格，里面有很多的引用。这个当然不能怨策划，还是我们需要解决的问题。策划表格会被转成XML或者二进制，用和其他游戏对象一样的机制被序列化，所以本质上每一个表格也都是对象，但我真没想到表格之间还要互相引用别的对象，我一直以为表格内部都是纯数据。糟糕的是，表格的每一行通常是一个巨大的结构体，也会有很多行，结构体里面只要有一个指针，就会被重复无数遍，这个指针也需要一次次被重新查找扫描，成为后续GC的负担，更何况往往结构体里面会有很多个指针，带来的负担就更大。

表格应该是一个静态的结构，无需被频繁的分配和释放，我们是不是应该考虑将其静态化？并告知GC，跳过这一步？听上去很靠谱，实际做起来也是，我简单加了一个GC_Free的标志，标识出表格。然后在GC扫描的时候，会有检查对象标志的地方，也去查一下GC_Free标志，可以跳过所有带有这个标志的对象，简洁完美。时间开销进一步减少，7.2ms变成了4.3ms。

进一步做了不少尝试，去除一些无关的调试代码，尝试把一些函数参数全局化，减少频繁调用的函数开销，但测试下来都没有什么效果，全部revert回去。

最后找到了结构体序列化的地方，有一个Lazy Init结构体元素的地方，是在序列化的时候才做一些数据的初始化，我改成了在游戏初始化的时候把所有的信息都预处理完，又节约了额外的0.2ms，最终GC一次的开采大约稳定在4ms。

做完这一切，时间也不早了，没有进一步的力气深入打磨，我打开了所有的编译器优化，让编译器完成最后的工作，编译器优化后，大约开销在2.4ms，完全可以接受了，我随手把每帧分配给GC的时间片预算从3ms改成1ms，整个引擎Loop终于从GC系统优化中收益，得到了2ms的时间。

一整天奋战，原始版本的19.6ms，优化到4ms，加上编译器优化，只要2.4ms，成绩不小，我带着心流的满足，愉快地开启了春节放假模式。

参与评论