面向数据设计的冒险之旅（三）C：外部引用

译者：崔嘉艺（milan21）

审校：王磊（未来的未来）

在这个系列教程的上一部分中，我们讨论了Molecule引擎中的句柄/内部引用，并讨论了它们相对于原始指针和普通指针的优势。

简而言之，句柄能够检测到二次删除，对释放数据的访问以及不能意外释放 - 请阅读以前的博客文章来了解所有的细节。

这一次，我们将介绍ID或是外部引用，这些机制也允许我们在内存中移动单个项，而不需要任何人注意到这一点。 但是，为什么我们要这样做呢？

答案很简单：Molecule引擎的世界/单位管理使用一个实体 - 组件系统，其中每个实体由它所组成的组件定义。 组件是小的、正交的数据，并且各个系统负责处理相应的组件。 所有组件都是简单的平坦结构，并且根本不包含任何逻辑或代码， 所有的代码都驻留在各自的系统中。

举个简单的例子来说，一个SkinnedMeshComponent组件存储了引用网格数据的各种句柄，包含蒙皮数据的双缓冲顶点缓冲区，以及着色器和材质。 它不包含任何代码，可以随意复制。

SkinnedMeshSystem负责处理组件：它拥有所有组件，创建并销毁它们，并负责更新和渲染它们。

那么为什么我们需要在内存中移动项呢？

l 创建和销毁组件都应该是时间为O（1）的操作。 如果不是这种情况的话，那么玩了好几个小时后，或者在创建大量组件的时候，性能可能会严重恶化。

l 遍历所有组件以更新它们，应该能尽可能少地导致缓存未命中。 因此，所有的项都应该像数组一样紧密地封装在内存中。

显然，这两个要求是相互矛盾的。 我们可以通过使用列表来满足时间为O（1）创建和销毁组件的要求，这解决了我们的第一个问题。 但是，我们无法以缓存友好的方式遍历所有组件。

另一方面，使用简单的数组满足了我们的第二个要求，但是如果我们不使用任何辅助数据结构，则创建和销毁组件将成为时间为O（N）的操作。

一个自定义的数据结构

与许多编程问题一样，我们会通过一些额外的间接工作来完成这些要求。

我们实际上不是使用列表或数组，而是使用：由列表管理的稀疏数组和包含单个组件的密集数组。

稀疏（外部）数组将索引存储在密集（内部）数组中，并为每个项生成一个代。这个代是我们上一次引入的单调递增的整数。密集数组将这些项连续存储在内存中，就像常规数组一样。

这种数组中的组件不被句柄所引用，而是被所谓的ID引用。 一个ID存储一个索引到稀疏数组中，以及创建时产生的代。

我们来详细说明下在这样一个数据结构上需要执行的操作的性能特征：

l 创建组件包括在密集数组（时间为O（1））的末尾添加一个新的组件，并使用原地的列表（时间为O（1））在稀疏数组中分配一个新的组件。该插槽将索引存储在内部数组中，并且用户在外部数组（时间为O（1））中保留一个“智能索引”的ID。

l 销毁组件意味着由ID描述的插槽需要返回到列表（时间为O（1）），并且组件需要从内部数组中移除。这可以通过时间为O（1）的操作完成，方法是将已移除的组件与数组中的最后一个组件进行交换，同时正确地将相应的索引从外部数组更新到内部数组。

l 访问一个组件会导致额外的缓存未命中，因为有额外的间接引用：我们首先需要访问稀疏数组以获取索引，并使用该索引从内部数组中检索组件。

l 对所有组件进行迭代是在密集数组上进行简单的循环操作，从而导致缓存未命中的数量最少。

可以看出，创建和销毁都是时间为O（1）的操作，遍历所有的组件就像遍历一个普通的数组。 这种方法唯一的缺点是对每个外部组件的访问都会导致额外的缓存未命中。可以说，对单个组件系统外部的访问的次数应该比每帧要访问的内部数据的次数要少得多，因此这样的数据结构在几乎所有情况下都应该是更好的。

此外，如果您足够小心的话，某个组件的查找可以在一个框架内完成，并且指向底层组件的指针可以缓存一个框架。 我不会推荐这样做，但是如果您确实需要每帧访问数千个单独的组件，这种方法可能是有益的。

Bitsquid引擎使用一个类似的数据结构，称为packed数组，但是我的实现与Niklas的不同。

结论

在Molecule引擎中，我使用ID来引用各种组件。用户只能看到ID，没有别的东西。因此，ID与句柄共享所有好处，还有一些额外的好处，特别是与实体组件系统结合使用更是如此：组件不需要基类，因为实体可以简单地存储一组ID /整数。这么做会在组件和实体之间创建更少的耦合。