ECS: 指针稳定性，墓碑和标识符

上一章我们知道，指针稳定性 是一个非常好的特性，但是为了实现它我们需要付出 墓碑实体 检查的代价，如果类型主要以线性方式迭代，那么性能将会遭受损失，但是即使某些类型 T 值得启用 指针稳定性，如果恰好包含它执行多组件池的迭代，并且它又恰好是组件池中实体数量最少的池，那么它会被选择为主导池，这会导致每次迭代都需要执行墓碑检查，增加了分支预测的开销，即使其它池没有启用 指针稳定性，所以我们必须找到一种办法来彻底消除墓碑检查带来的成本

实体标识符

我们知道可以将实际实体及其版本嵌入单个标识符中
具体为 实体部分 和 版本部分 分配多少 bit 位是一个实现细节

空实体 是 实体部分 的保留值
空实体 的 版本部分 并不被使用，所以它是闲置的，可以被利用

• 空实体 位于 稀疏数组 中

而 墓碑 则是 版本部分 的保留值
这次我们没有什么可以利用的，因为 墓碑 的 实体部分 也被用于说明具体哪个 实体 成为了墓碑

• 墓碑版本 位于 密集数组 中

所以如果 实体部分 和 版本部分 都是保留值，那么完整的实体标识符看起来是这样的

空实体 null entity

前文介绍了一种降低 稀疏集 查找成本的技术，将 空实体（即具有空实体部分的标识符）与 稀疏数组 相结合，以避免在查找期间检查 密集数组，如果 稀疏数组 中的元素为 空实体，我们肯定知道 密集数组 中没有匹配项

以下是查找函数 contains 的简化版本，不考虑 分页

bool contains(entity_type entity) const {
    const auto index = entity_to_index(entity);
    return index < sparse.size() && sparse[index] != null;
}

在这种情况下，我们不需要访问 密集数组 来获取实体的位置，这在迭代过程中节省了相当多的时间，主要是因为我们可以更早地丢弃元素并减少内存访问

但这实际上存在一个问题，我们的存在性检查只是

• 检查索引是否在范围内：index < sparse.size()
• 对应的条目不为空：sparse[index] != null

可以发现，contains 函数只检查实体的索引部分，而完全忽略了实体的版本号

• 如果传入的实体标识符版本号为 N，而池中存储的实体版本号为 M（M != N），函数仍然返回 true，这是错误的逻辑，因为版本号的变化通常意味着该实体已经被销毁并重新分配，此时索引可能有效，但对应的版本已不匹配

墓碑版本 tombstone version

前文也介绍了如何在 密集数组 中使用 墓碑 将元素标记为已删除而无需交换和弹出它们，这与分页相结合，使我们在任何情况下都能拥有指针稳定性

但是这会影响查找函数 contains，因为当实体被摧毁时，它们被标记为 墓碑，并通过隐式链表连接起来，这个链表可以按需访问所有已摧毁的实体（墓碑），如果我们正在迭代一个包含墓碑的组件池，那么迭代器会遍历池中的所有条目，包括正常实体和墓碑，在这种迭代中，每个标识符都必须传递给 contains 函数进行检查，因为它可能同时具有：

• 特殊的 版本部分： 表示该条目是墓碑
• 有效的 实体部分： 虽然可能指向一个有效的 实体标识符 (而不是 空实体)，但由于其版本号为墓碑标记，因此整体被视为无效

我们必须对这种情况进行检测

bool contains(entity_type entity) const {
    if(entity == tombstone) return false;
    const auto index = entity_to_index(entity);
    return index < sparse.size() && sparse[index] != null;
}

并且当我们在对 密集数组 进行迭代的时候，也必须执行检测

for(auto entity: pool.packed()) {
    // 首先检测当前遍历到的实体是不是 墓碑，可以快速跳过
    // 然后再检测当前实体是否在其他相关的组件池中有效
    if(entity != tombstone && check_all_other_pools(entity)) {
        // application code here
    }
}

在这两种情况下，都需要执行一个额外的分支检查，我们知道应该尽可能避免分支以获得更高的性能

最终实现

在 稀疏数组 中，我们要么存储 实体 在 密集数组 中的索引，要么存储一个 空实体，由于标识符的 实体部分 仅使用前 N 位，因此我们知道集合中的元素不能超过 N 个，而标识符的版本部分 在 稀疏数组 中并未使用，我们可以利用它来实现我们的目的

• 当我们想在 稀疏数组 中存入 空实体 的时候，同时将其 版本部分 设置为 墓碑 (也就是被 保留的实体标识符 reserved identifier)
• 其它任何时候，稀疏数组 中的元素都应该包含两个部分，实体部分 存储该实体在 密集数组 中的索引，版本部分 存储该实体的实际 版本

完成后，对 contains 函数进行简单的修改即可解决上述两个问题 (任然忽略了内存分页)

bool contains(entity_type entity) const {
    const auto index = entity_to_index(entity);
    return (index < sparse.size()) && ((~null & entity) ^ sparse[index]) < null;
}

标识符版本部分是否是有效版本

这里 (~null & entity) 将返回实体的 版本部分

• null 是一个特殊的位掩码，用于提取 版本部分，假设实体标识符 entity 是一个 32 位整数，高 16 位是版本号 (从左到右前面的半部分)，低 16 位是索引 (后面半部分)，那么 null 可能是 0x0000FFFF 而按位取反的 ~null 就是 0xFFFF0000，运算 ~null & entity 会屏蔽实体标识符的索引部分，只保留版本号
• entity 是输入的实体标识符

提取版本后，((~null & entity) ^ sparse[index]) ，也就是 ((提取的版本) ^ sparse[index]) 将测试两个版本是否相匹配，这里的位操作 异或 ^ 是常用于检测相等的位运算符

• 两个位相同：结果为 0
• 两个位不同：结果为 1

如果两个数完全相等，则异或结果为 0，如果两个数不同，则异或结果的每一位表示它们的差异，这非常适用于版本检查，如果实体标识符的 版本部分 与 存储版本 完全一致，则异或结果为 0，如果版本不一致，异或结果为非零值，且结果值能够直观反映差异

注意这里不能用位运算符的 按位与 &，因为它只有当 两个位都为 1，结果才为 1，通常适用于提取特定位（通过掩码）

但是我们想要的实际上是一个 bool 值，而不是两个版本号每一位的差异，所以我们再将异或的结果和 null 即 0x0000FFFF 进行比较 ((~null & entity) ^ sparse[index]) < null 也就是 异或结果 < null，我们如果版本相等，也就是 异或结果为 0x00000000 那么它必然小于 null，这样也就完成了标识符是否是有效版本的判断

在以下情况，两个版本会不相等

• 该实体不是集合的一部分，因此稀疏数组中设置的版本是墓碑版本
• 稀疏集中的实体与提供检查的实体具有不同的版本

假设数据 entity = 0xABCD1234

• 高 16 位版本号：0xABCD
• 低 16 位索引：0x1234

情况 1：实体在集合中 稀疏数组存储的是有效版本 sparse[index] = 0xABCD

version  = (~null & entity)        = 0xFFFF0000 & 0xABCD1234   = 0xABCD0000;
result   = version ^ sparse[index] = 0xABCD0000 ^ 0xABCD0000   = 0x00000000;
is_valid = (result < null)         = (0x00000000 < 0x0000FFFF) = true;

情况 2：实体不在集合中 稀疏数组存储的是墓碑版本 sparse[index] = 0xFFFF

version  = (~null & entity)        = 0xFFFF0000 & 0xABCD1234   = 0xABCD0000;
result   = version ^ sparse[index] = 0xABCD0000 ^ 0xFFFF0000   = 非零值;
is_valid = (result < null)         = false;

标识符实体部分是否是空实体

这很容易判断 entity_to_index(null) 返回的索引始终大于 sparse.size()，因此 (index < sparse.size()) 部分会起到判断作用

总结

我们需要 空实体 是因为我们想直接在 稀疏数组 内检测实体是否有效，而不想去因此额外访问 稠密数组，通过将无效 实体 在 稀疏数组 中的 实体部分 标记为 空实体 来实现

我们需要 墓碑 是因为我们需要 实体 在 稠密数组 内具有 指针稳定性 ，通过不在 稠密数组 中交互和弹出 实体 (这将导致指针失效)，而是在 稠密数组 中，将被摧毁的 实体 的 版本部分 标记为 墓碑版本 来实现这一点

最后我们通过在 稀疏数组 同时管理 实体索引 和 版本信息 来实现最少内存跳转的实体有效性检测，也就是说，除了在 密集数组 中使用 墓碑版本号 来保证指针稳定性之外，也在 稀疏数组 中引入 墓碑版本号 来加速实体有效性检测 (检测到不是 空实体，版本号也不是 墓碑版本号 则该 稀疏集 中含有该实体)