有序数列的数据结构优化

在我们的 ecs 模块中，有一个重要的内部数据结构是 eid 的数组。它是 Component 结构的一部分，表示每个 Component 属于哪个 Entity 。目前，它是以一个有序的 id 数组实现的。

这个数据结构常见的操作分别是：遍历、随机访问、查找 id 所在的位置。一个有序数组可以很好的完成任务。O(1) 的随机访问时间，O(Log N) 的查找时间。

我们的 Entity ID 是 48bit 的，我觉得保存 48 或 64bit 的 id 数组有点浪费，且空间越大，实际操作效率也会相应降低。实际上，Entity 的个数不会太多，我觉得限制在 2^24 (一千六百万左右）足够了，所以用了一个间接索引，保存 24bit id ，再用它去索引真正的 entity id 。

三个字节保存内部 id 听起来有点别扭，因为内存访问没有对齐。但是 4 字节又略显浪费，2 字节我担心不够用。所以，在上个月时，尝试做了一点优化：

将数据按固定 32 (或至多256) 个元素分组。每组 64bits header + 32 * 8bits 。header 保存第一个元素的高 40bits ，后面是每个元素的低 8bits 。每组分为三个区段: 1. 高位相同 2. 高位+1 3. 其它离散数据。header 中用 2 bytes 保存 1,2 区段个数。用 16bits 保存离散数据的 offset 。

所有离散数据依次用 40+24 bits 数组额外储存。40 bits 高位，24bits 是它的 index 。前面每个组的离散区段在这个离散数组中每段是连续的，并可以直接 offset 索引。所以：任何随机访问都是严格O(1) 的。

最坏情况，数据结构退化成一个 64bits 数组，大小为 n * 31 / 32 加上固定的 每个元素 10bits 开销。二分查找的比较次数在最坏情况也不会恶化。

我尝试做了实现， 但写完后发现代码过于复杂。虽然大 O 的估算性能不是问题，但实际上比平坦数组差距很大。所以我放弃了这个想法。

当然，促使我放弃的更重要原因是：我们游戏实测中，Entity 的个数峰值仅有一万左右，原不到设计时考虑的百万量级。如果 Entity 数量可以控制在 64K 之下，直接用一个 2 字节的内部 id 即可。

所以我转而考虑另一个问题：

一个平坦有序数组，它的插入和删除效率是很低的，时间复杂度为 O(n) 。这里是否有优化空间？

当然，在我们的 ecs 系统中，是不允许插入 Component 的（Entity 必须在创建时决定它的 Component 构成），实际用下来并无问题。而删除操作是集中在每 frame 做的。也就是当 frame 删除的所有 Component 一起的开销是 O(n) ，并不会变成 O(n^2) 。

但 tag 是个例外，一个没有数据的 Component 被称为 tag ，它仅用于 Entity 筛选。tag 可以动态添加和删除。我在前两年专门针对它 做过一些优化 。删除的复杂度可以降低到 O(log N) ，添加最坏是 O(n) 但通常可以比之小。

怎样优化有序数列的插入和删除？这其实是一个经典问题。最为人所知的方法有 B 树和跳表。

B 树的想法是：我们在保存这个数列的时候，将其分段，每段并不填满。这样，插入的时候通常只用移动一段的数据，而不需要处理整个数列。

跳表的想法则是：用链表来保存数列，这样合并 freelist 的策略，就可以以 O(1) 的时间成本插入或删除元素。但，链表不支持随机访问，索引其中特定位置的元素需要 O(n) 的时间复杂度。为了解决这个问题，就增加一个额外空间来换取时间，间隔若干元素再加上若干高层次的链表。这样，在随机访问时，从高层向低层迭代，就可以以大约 O(Log N) 的时间复杂度检索到。

而我面临的问题数据规模不大，大约是数百到上万左右，极少情况会超过 10 万。完全可以针对性的设计一个更简单更高效的数据结构。这就是我今天实现的，它像是 B 树和调表想法的结合：

我把数列以 256 个一组分组，分段保存。每一组有一个很小的 header 。每段 256 个槽位里是一个装满的循环队列。只有最后一组是个例外：它可能是不满的。

当我们做随机访问时，先计算是哪一组，再结合循环队列的头位置做一个简单的取模操作就可以定位到元素。

在删除元素时，先在所在组里删除，最多移动 127 个元素（可能向前滚动，也可能向后滚动） ，然后依次把后序每组的第一个元素移进来。

添加元素则是删除的逆操作，它也最多移动 127 + n 个元素，n 是组的数目。

因为大多数情况下，我们的 entity 数量都不会太多，所以内部 id 的数字都不大，我认为 2 个字节就够了。但是，我还是想支持超过 64K 的情况。所以、我把以上的分组分成两种：致密型和稀疏型。

所谓致密型分组，分组中最小的元素和最大的元素相差不超过 64k ，这样，在 header 中保存一个 32bit base ，再在实际的 chunk 中保存 int16 的 delta 。这个 delta 是有符号数，范围是 -32K 到 32K 。如果不能以这样的形式保存的分组，就使用稀疏型分组，直接保存 256 个 4 字节 id 。稀疏型分组需要的内存正好是致密型的 2 倍。

为了管理这两种不同类型的分组，我采用了 freelist ，每个 node 都是 1 个稀疏型分组的大小（1024 字节），它同时可以保存两个致密型分组。

绝大多数 id 都保存在致密型分组内。两个挨在一起的分组占用一个 node 。如果我们需要把一个分组从致密型提升为稀疏型，就先看它是否有伙伴。如果有，则把伙伴设置为单身，而自己从 freelist 中分配一个独立的新 node ；如果没有伙伴，就直接独占当前 node 即可。

从稀疏型降为致密型只需要做相反的操作即可。

今天，我用 C 语言实现了一下。在 O3 优化时，和平坦的简单数组相比，随机访问效率几乎相同；而二分查找性能差不多会损失 5% 到 10% 。数组越大，性能差距越小。我想是因为传统的数组是 32bits 一个元素的，而目前这个实现绝大多数情况都是 16bits ，对内存访问更为友好。而且，header 带有的 base 信息也方便了第一步的初步检索。

​Read More