云风的 BLOG: 支持部分共享的树结构

因为图形引擎中的对象天然适合用树 (n-ary tree) 表达，所以它在图形引擎中被广泛使用。通常，子节点会继承父节点的一些状态，比如变换矩阵，在渲染或更新的时候，可以通过先序遍历逐级相乘。

在 PC 内存充裕的条件下，我们通常不必考虑树结构储存的开销，所以大多数图形引擎通常会为每个渲染对象独立生成一个树结构，比如 Unity 中的 GameObject 就是这么一个东西。在 Ejoy2D 中，从节约内存的角度考虑，把树节点上的一部分可共享的状态信息（不变的矩阵、纹理坐标等）移到了资源数据块中，但是树结构的拓扑关系还是在新创建出每个 sprite 时复制了一份。

随着游戏制作的工艺提高，而大众使用的移动设备的内存增长有限，这部分的开销慢慢变得显著。在我们正在开发的几个项目中，渲染对象本身，而不算图形资源（贴图、模型等），也占据了以 M 为单位计算的可用内存。比如在一个项目中，某个巨型对象由多达 2000+ 个节点构成，创建速度和内存开销都成为一个不可忽视的问题。由于是于自研引擎，所以同事尝试过一些优化的尝试。

图形引擎处理的大多数的树结构对象，其实仅在编辑环境会对树的拓扑关系进行调整：增加、移动、复制节点。而运行环境下，树结构本身几乎是不变的。一般的树结构的实现是用指针来相互引用，编辑好的资源是树结构的序列化结果，而创建过程是一个反序列化过程，在内存中重建整棵树，并用指针重新建立节点间的联系。比如在 Unity 中，就把这种编辑好的树对象叫做 prefab 预制件。如果预制件比较复杂，加载预制件和从预制件中构建对象的时间成本都不算低。

一个优化方法是去掉运行时内存中的指针，改用 id 或资源数据块中的偏移量，这样，预制件可以直接从资源文件中成块读入，创建内存对象时也只需要用指针引用即可。可以节省大量在内存中重建的时间。Ejoy2D 现在就是这么做的。去掉指针的额外好处是在 64 位系统下，可以从 8 字节的引用开销减少到 4 字节（或更少）。Ejoy2D 当初做此修改，为一个项目一举减少了 10M+ 的运行期内存占用。而且资源文件可以在暂时不用的时候移出内存，等需要的时候再加载回来，而不用担心数据的内存地址发生了变化。

但是，如果想让游戏对象直接共享使用预制件，最核心需要解决的问题是：大部分对象并不能做到完全不修改树结构，且预制件中的树的拓扑关系并不直接对应到内存。

我们先来看对应关系的问题：

在 ejoy2d 中，资源（预制件）中的对象结构其实并不是树，而是一个有向无环图。例如：美术制作了一个房子，房子上挂着三个灯笼，在资源中，灯笼只有一个预置对象，是房子对它有三个引用。而在运行期，三个灯笼必须是三个独立对象；程序是有能力对它们分别修改属性的。比如改改颜色，摆动频率等等。也就是说，这个房子的预制件一但在内存中还原，原本共享的灯笼子物件，必须有三份可供修改的状态数据区。

再来看前一个问题：

对于制作好的预制件，运行期很可能对树上的某个节点做属性调整。比如、预制件制作了一个仓库，仓库中的货物就是由运行时决定的。我们在陌陌争霸中，为仓库的货物状态预设了数帧图片，在运行时可以设置显示第几帧，用来表示仓库的库存情况。如果仓库中的货物还可以根据运行情况实际表现出来，则还需要用到挂接的功能：把货物对象挂接到仓库预设的挂接点上。

由于这些实现上的复杂需求，ejoy2d 和大多数图形引擎一样，从预制件创建出游戏对象直接简单的重建树的过程。当你从资源中创建一个 sprite ，你会发现逐层创建出了 lua 对象。然而大多数情况下，运行期并不会修改其中的绝大多数对象的属性，而仅使用资源中预制好的那一份。这就造成了一些浪费。如果资源中的树不算复杂时，这个浪费是有限的；但是我们的一个使用 ejoy2d 开发的新项目，随着内部工具的完善，美术逐渐创作出越来越复杂的结构。使用 ejoy2d 做新项目开发的同学花了半年多精力想优化这个问题。

我最近也重新思考了一下，这个问题的本质是，如果已有一个层级复杂的树状数据结构（下面称它为蓝图），我们可不可以做到有很多基于它的副本，每个副本对其中的部分做修改，而共享那些没有修改的部分。

比较容易想到的方案有这些：

在蓝图的每个节点上预留一个指针，指向一个列表；如果有副本向修改这个节点，就把修改后的属性加到这个列表中。在遍历这个节点时，一旦发现这个节点有人修改过，就找到对应的修改数据。另外，蓝图中如果有重复引用的节点（例如上面提到的屋檐下挂的灯笼），在修改其属性时，需要拷贝分裂。
对 1 方案做一些修改，预留指针只保存一个槽位，副本修改属性记录在副本对象中，而在遍历蓝图前，将副本中修改过的属性填入蓝图，遍历完成后再清除；或是在填入的同时把副本指针也记录在节点上，遍历时忽略非自己修改的节点。
在副本中保留一个修改节点数据的 hash 表，遍历蓝图的时候查询 hash 表，找到可能修改的属性。
在修改蓝图的某个节点时，部分复制创建出一颗不完全树，只保留被修改属性的节点和它们的祖先；让那些没有修改的分支引用回蓝图。遍历的时候改遍历复制出来的不完全树。

这几个方案大同小异，我们实际在项目中采用的方案 1 ，数据结构比原先的 ejoy2d 复杂了很多，衍生出不少 bug ，目前还不够稳定。

我这几天的思考结果是，在方案 3 的基础上做改进，或许是更好的选择。

方案三的本质是：运行时的树由蓝图和对蓝图的补丁两个部分构成。这样从数据结构上来说，它们是独立的两块数据，相互引用关系比较简单。可能的额外开销是遍历每个节点时需要额外的一次 hash 表查询，虽然大多数情况下是 Hash 表查询是 O(1) 的操作，但实际上会因为冲突而 O(1) 高一些，尤其是这个方案的初衷之一就是节省内存，如果预留比较大的 hash 表池来减少冲突率的话，很可能剩下的内存又再次消耗掉了。另外 hash 表的 key 也不太好选择，不能直接用节点对象的指针，因为在蓝图中有大量的对象是被共享的。

怎么改进呢？

其实、我们对树的遍历方式其实是唯一的。在图形引擎中多半选择深度优先的先序遍历，也就是先访问根节点，再依次访问子节点。如果树的拓扑结构稳定，其实每次遍历的过程都是唯一的。所以运行时的每个节点其实都可以根据其遍历次序有一个不变的唯一序号。对于上面提到的屋檐下的灯笼，多个灯笼虽然共享着蓝图上的同一块数据，但每个灯笼，以及灯笼下的子节点都有不同的访问编号。我们可以用这个编号来索引附加（修改的）节点属性。

由于访问次序固定，我们也不再需要用 hash 表来记录 patch 集合，而只需要按访问先后次序来排列好 patch 即可。再访问过程中，每访问到一个节点，就把访问编号加一，检查 patch 链表头就知道是否当前节点丫头修改属性了，这样就可以做到严格的 O(1) 时间，同时也不增加内存开销。

order 的值虽然无法直接记录在蓝图上，但我们可以在蓝图中预算好每个子树的总节点数，这样计算节点的 order 成本仅 O(log n) 。而且仅在取节点引用，或是从非根节点开始遍历时才需要计算一次。

还剩一个问题：

遍历树结构变复杂了，即使我们把遍历算法写对，却很难用常规手法封装。用简单的迭代器模式是不够的，遍历树不仅仅需要访问到每个节点，还需要在遍历过程中感知到树的遍历层次变化。比如在 ejoy2d 现在的公开版本中，需要按树层级来累乘变换矩阵，这个临时矩阵是存放在遍历过程中的函数调用栈上的。我们还可能根据枝干上的（隐藏）属性来跳过子节点等等。

否则，既然访问持续恒定，为什么不直接把树摊平？btw, 在上面提到的当前项目中，维护引擎的同学已经把摊平树结构作为了一项优化。

我还没有见过哪个 C 版本的 n-ary tree 能够把接口设计好，做到高内聚性的实现；大多数情况下，C 语言的项目中都会根据实际需要来实现一个仅满足自身需要的 n-ary tree ，把模块内聚性的边界放在更高一些的层次，而不直接暴露树结构的接口。

C++ 倒是有几个树结构的实现：比如 tree.hh 以及 boost::graph ，它们都是想切合 STL like 的迭代器模式，实际用起来是很麻烦的。我想这也是为什么即使是 C++ 项目，大多数人也自己用更基本的数据结构 std::map std::set std::list 等组装。

我花了两天时间来实现上面的想法，代码放在 github 上，尚还有一些部分（主要是生命期管理）需要完善。

在我的实现中，我设计了以下数据结构：

tree_blueprint 表示树结构蓝图，在蓝图阶段可以从根开始构建树，增加子节点，但不可以删除和移动节点。这是因为这些灵活的需求多半在编辑器中才有，而编辑器完全可以用动态语言来实现编辑过程，蓝图只需要满足基本的构建需求就可以了。如果需要修改蓝图，不如从头创建一个新的。蓝图的序列化过程并没有实现，但它应该很容易做到。蓝图结构主要记录的是树的拓扑形态，每个节点上的附加属性用一个 void * userdata 传入，它不关心具体是什么。

tree_patch 是针对某张已经定型（不再修改）的蓝图的一些修改，它由一系列的补丁循序组成。每个补丁记录有对应的节点遍历次序号(order) , 和修改过的属性段 userdata 。补丁也允许对蓝图上对应节点的做额外挂接 (mount) ，但不可以新增子节点。重新挂接的子树是一个 tree 结构，而不能使蓝图节点。

tree 是 tree_blueprint 和 tree_patch 的联合。一张蓝图和一组对应的补丁，构成了一个运行时的树结构。蓝图斯不可修改的，可以被多个 tree 引用。补丁是 tree 唯一的，不可被引用。补丁在每次新增节点后，都会生成一个新版本。对已有节点上修改属性数据则不会影响补丁的版本。

tree_node 是对 tree 上任意节点的引用，每个节点可以有多个 tree_node 引用共享。实际封装到上层后，可以用 cache 来保证做唯一引用以简化生命期管理。所有的运行期读写树节点的操作都需要通过 tree_node 来完成。

tree_blueprint 可以 print 出 tree ，tree 可以取得根节点的 tree_node ，tree_node 可以 setpatch 和 getpatch ，也可以 read 出对应蓝图上的原始属性信息，还可以 fetch 其子节点，或 mount 一个新的 tree 。

我觉得把出去 tree_node 之外的结构统一起来做生命期管理比较好。因为他们的数据间的相互引用关系比较复杂，用标记清除的垃圾回收算法比用引用计数更为简单牢靠。所以另外设计了一个 tree_manager 结构，管理了所有的以上结构，并用数字 id 来自带具体对象。

tree_node 是个例外，在 api 设计时，全部都由调用者传入这个结构的内存，它是对实际数据的引用，这里并没有做反向引用，也就是说 tree 本身并不知道自己被多少 tree_node 引用过了，我想这个问题在上层封装中比较容易解决。比如在 lua 封装中，可以用 tree 的 id 和 order 做唯一索引来制作一个 tree_node 的 cache 。

这里预设的场景是：fetch 一个 tree node 预留额外的属性空间这个操作是比较低频的，可以接受较大的时间成本。因为实际使用的时候，我们都是在初始化阶段就把需要关注的节点引用好，或者只在第一次访问时做唯一一次 fetch 操作。一旦保留了 tree node 对象，读写上面的属性应该是最快的，保证 O(1) 时间可以完成。遍历是另一个需要关注的性能热点，数据结构的设计应该尽量满足遍历最快，空间最省。

树的遍历接口我仔细设计过，虽然用起来比较麻烦，但基本保证了高内聚性。好在上层封装也仅有有限的几处调用树的遍历：渲染遍历、更新遍历、点击测试遍历。ejoy2d 并没有专门对遍历做封装，而是简单的复制了遍历代码；这次树结构变复杂，恐怕就不适合复制代码了。

这次我使用了一个回调函数的接口：

void (*tree_traverse_func)(void *bp, void *patch, void *argument, void *stackframe);

在访问每个节点时都会调用，前两个参数指蓝图上绑定的 userdata 及补丁（如果有）上绑定的 userdata 。

后两个参数用于模拟递归层次。argment 指上层调用传入的数据块，对于根节点，它就是 tree_traverse 调用传入的数据；然后在遍历过程中，遍历函数会在自己的栈帧上分配出一块内存，通过 stackframe 参数给回调函数，回调函数可以把需要传递给下层的数据写入，遍历框架会将其用 argument 传给下一层节点。如果当前访问的节点是叶节点，那么 stackframe 为 NULL 。

解释起来可能说不太清楚，可以看看例子里是怎么使用的。