YSYSIMONCODE. ART. SCIENCE. VISION.

ECS: 稀疏集和指针稳定性 sparse sets and pointer stability

整理稀疏集如何通过分页存储、墓碑实体和墓碑版本号维持组件指针稳定性。

Dec 11, 2024约 7 分钟Principlesysysimon
ECSC++Sparse SetPointer Stability

在 ECS 架构中，指针稳定性 Pointer Stability 是指在程序运行过程中，无论是添加还是移除组件，实体或组件的指针都能保持稳定且有效的特性，这种特性在某些场景下非常有用

  1. 层级结构的处理
    稳定的指针使得处理父子关系变得简单高效。实体可以直接存储指向父节点或子节点的普通指针，而无需担心因重新分配或移动导致指针失效
  2. 与第三方库的集成
    一些 C 语言的库，要求用户手动分配对象并传递指针，稳定的指针可以确保传递的对象在整个生命周期内不会因系统操作而无效

有些模型使得实现指针稳定性非常困难，例如 原型 Archetype，因为它将具有相同组件集合的实体存储在紧凑的 表（archetype table） 中，所以在此模型中，添加或移除组件通常需要将实体从一个表移动到另一个表，这会破坏指针的稳定性，而如果需要实现指针稳定性，可能需要额外的妥协方式，比如为实体维护一个 稀疏集 sparse set 来提供稳定的引用

稀疏集

在 稀疏集 中，指针失效主要在以下两种场景中发生

  • 添加实体和组件到池中
  • 从池中移除实体，并因此移除组件

对于用户来说通常希望这两种操作具有指针稳定性，而其它一些操作，例如对池进行就地排序虽然也会使得所有引用、指针和迭代器失效，但是对于用户来说，执行这些操作以后发生指针失效是合理的

创建组件

当组件存储为紧凑的单块内存时，组件的创建（即添加组件）可能导致引用或指针失效，这是因为当存储空间不足时，系统需要分配更大的内存块并迁移所有组件，这种操作会使现有的指针指向旧的内存位置而变得无效

为了避免这种重新分配内存而导致的指针失效，可以引入 分页存储 的机制，这种方法通过将组件数组分为多个页面（小块内存）来解决

  • 分块存储组件
    将组件的存储划分为多个固定大小的页面，每个页面是一个连续的内存块
  • 动态扩展
    当一个页面用完时，不需要整体重新分配，只需分配一个新的页面并将其添加到存储结构中
  • 指针稳定性
    原有的组件不会被移动，因为重新分配只会影响页面的指针，而不会改变页面内存中的组件位置

分页存储的核心思想是移动页面指针而不是组件内容本身，因此现有的指针仍然有效，并且分配一个新页面的成本远低于重新分配整个数组，因为无需迁移已有的组件，虽然这会在迭代时会引入一些额外的跳转（取决于页面大小），但这些跳转的开销在现代处理器上通常可以忽略不计

// 一种分页示例
struct Page {
    Component components[PageSize];   // 每页存储固定数量的组件
};
 
std::vector<Page*> pages;             // 动态扩展页面

销毁组件

对于 稀疏集 来说，销毁组件时保持 指针稳定性 更具挑战性，通常，稀疏集合在移除组件时会采用 swap-and-pop 策略，即将待移除的组件与数组末尾的组件交换，然后从数组中移除末尾的元素，这种操作虽然高效，但会显然会导致 指针失效 的问题

为了保持 指针稳定性，我们必须

  1. 只移除，不交换
    不再进行交换操作，而是直接在组件池中留下一个 空洞，这意味着移除操作仅会使组件被标记为无效，而不会改变其他组件的位置
  2. 标记 空洞 的位置
    我们需要一种机制来标记这些 空洞，以便在未来可以重复利用它们而不会浪费空间

墓碑实体 Tombstone Entity

使用 墓碑实体 来标记组件移除后产生的 空洞 是一种简单的方案，但它存在明显的优缺点，因此是否使用墓碑实体需要根据实际需求权衡

优势

  • 实现简单
    墓碑实体的实现非常直观，只需将被移除组件对应的位置标记为墓碑（null 实体），不需要额外的数据结构或复杂的逻辑，删除组件时，仅需简单地替换为墓碑标记，不涉及复杂的内存操作
  • 线程安全
    由于删除操作仅涉及标记墓碑，可以在多线程环境中并行删除多个组件，不需要加锁或同步操作，极大简化了并发场景下的管理
  • 无需额外存储
    墓碑的标记可以直接复用现有的实体 ID 空间，因此无需额外分配存储来追踪空洞位置
  • 空洞复用
    如果一个实体被重新分配了相同类型的组件，可以直接复用墓碑标记的位置，无需分配新的存储空间

看上去优势很多，但是实际执行时存在一些问题，主要是无法高效的追踪 空洞，因为 墓碑 仅仅标记了 空洞 的存在，但无法高效地管理或复用这些空洞

  • 方案 1：按需搜索空洞
    当需要新分配组件时，扫描整个数组寻找墓碑，这种方式在组件池较大时会非常耗时
  • 方案 2：不复用空洞
    完全忽略空洞，直接在池尾分配新的组件，但是如果不复用被标记为墓碑的空洞，随着删除操作增多，碎片化会导致大量空间浪费，长时间运行后，碎片化问题可能需要通过 重新压缩 compaction 来解决，这会引入额外的性能开销，对实时性要求高的系统尤为不利

墓碑版本号

引入 墓碑版本号 Tombstone Version 可以有效改进组件移除的管理，同时支持 原地删 in-place delete，这种方法结合了墓碑机制和隐式列表的优点，既能高效追踪空洞，也能在并发环境下保证线程安全

墓碑版本号的核心思想是

  • 版本号标记空洞 使用一个特殊的版本号（称为墓碑版本）来标记空洞，组件池中的空洞可以通过检查版本号来识别
  • 隐式列表追踪空洞
    实体标识符的实体部分可以存储下一个空洞的位置，从而构建一个隐式的空洞链表
  • 头指针管理空洞链表
    组件池需要一个额外的成员变量（如 firstHole）来存储空洞链表的头部位置
  • 原地删除
    在删除组件时，仅更新墓碑版本号，并将空洞加入隐式链表，无需移动组件数据，保持指针稳定性

实现步骤

  • 删除组件
    在组件销毁时，执行以下操作
    1. 将组件对应的版本号更新为墓碑版本号
    2. 将实体部分的标识符设置为当前 firstHole 的值（即链表的下一个空洞）
    3. 原子更新 firstHole 指向新的空洞
  • 分配组件
    在分配新组件时，优先从空洞链表中复用空洞
    1. 如果 firstHole 不为空，取出 firstHole 所指的空洞
    2. 将该位置的版本号更新为有效版本号
    3. 更新 firstHole 指向下一个空洞（链表头部的下一项）
    4. 如果没有空洞，则直接在数组尾部分配新的空间
  • 并发删除
    删除操作可能会同时由多个线程进行，但唯一可能的冲突点是更新 firstHole，所以使用原子变量管理 firstHole 的更新，避免线程间的竞争

迭代策略

上述解决方法由于使用了原子性的变量，所以在迭代时存在一些开销，但是 EnTT 允许单独控制某个类型是否开启 指针稳定性 这是由于其设计的独立池，而使之成为可能

  • U 类型主导迭代（无指针稳定性）
    如果主导迭代的池 U 没有启用指针稳定性，池中没有 空洞，迭代完全是线性访问，不需要检查墓碑或空洞，开销最小，这适用于那些主要以线性方式访问组件的类型，例如位置、速度等

  • T 类型主导迭代（启用指针稳定性）
    如果主导迭代的池 T 启用了指针稳定性，池中可能存在墓碑（空洞），迭代需要额外的条件分支来跳过墓碑

    • 分支预测开销： 每次迭代需要进行墓碑检查（通常是条件判断），可能导致分支预测失败
    • 缓存影响： 空洞可能破坏数据的内存局部性，从而降低缓存命中率，如果类型 T 的池中空洞较多，或者访问非常频繁（如主游戏循环中的热路径），性能下降可能更加明显

    这适用于那些需要随机访问或必须保证指针稳定性的类型，例如父子层级关系中的节点、需要传递给第三方库的稳定指针