ECS: 嵌套组和完美 SoA

整理 ECS 分组的本质、嵌套分组的维护顺序，以及 perfect SoA 布局背后的代价。

Dec 6, 2024约 7 分钟Principlesysysimon

在前面的章节我们介绍了 分组 grouping 功能，它可以实现根据需要的组件集对实体以 SoA Struct of Array 的内存布局进行优化访问，这保证了实体及其组件被紧密地排列在一起，并以相同的顺序存储，这样做具有显著的性能优势，迭代将是线性的（从 0 到 N），无需跳跃或分支，这对于 CPU 缓存是友好的，尽可能减少了在迭代中浪费 CPU 周期

但是这也有所限制，即每种组件类型只能属于一个分组

比如，如果你创建了 <sprite, renderable> 这样的分组，你就无法直接优化另一个类似的分组（例如 <sprite, renderable, position>），而不得不通过间接访问的方式来获取组件

突破单组件只能属于一个分组的限制的关键在于，我们实际上并不需要强制性地引入排序，事实上，排序只是创建和维护分组时的附带结果，而并非必要条件，真正定义一个分组的是对原始数组的划分，即将数组分成两部分：属于分组的元素 和 不属于分组的元素

分组的本质

一个分组本质上是一个指针，指向分组中元素的最后一个位置，通过维护这一指针，可以实现

新实体加入时，移动组件到分组的末尾，并增加指针位置
实体移出时，将其与分组最后一个元素交换，并减少指针位置

这将导致数组被分为两部分

分组中的元素（紧密排列，符合分组条件）
未分组的元素（不需要特别关心其排列或关系）

嵌套分组 Nest Group

通过将分组的紧密排列部分看作一个独立的数组，我们可以进一步对其划分，从而实现 嵌套分组

简单分组
对于 <A, B> 分组，已包含实体 e4 和 e7

A packed    : [e4|e7|e3|e8|e6]
A component : [A4|A1|A0|A2|A3]
  <A, B> ___________^
 
B packed    : [e4|e7|e5]
B component : [B0|B2|B1]
  <A, B> ___________^

分组 <A, B> 的部分（紧密排列的 e4 和 e7）已经固定，而其他未分组的部分无须关心

嵌套分组假设我们创建一个更大的分组 <A, B, C>，它是 <A, B> 的子集，要求实体同时拥有组件 A、B 和 C

A packed    : [e4|e7|e3|e8|e6]
A component : [A4|A1|A0|A2|A3]
  <A, B, C> _____^
  <A, B> ___________^
 
B packed    : [e4|e7|e5]
B component : [B0|B2|B1]
  <A, B, C> _____^
  <A, B> ___________^
 
C packed    : [e4|e8|e5]
C component : [C2|C0|C1]
  <A, B, C> _____^

在这个嵌套分组中

<A, B> 包含至少与 <A, B, C> 相同的元素
<A, B, C> 将 <A, B> 划分为两部分
- 同时拥有 C 的实体部分（如 e4）
- 不拥有 C 的实体部分（如 e7）

嵌套分组的条件是，一个分组必须 完全包含 另一个分组，包含是指一个分组的组件类型列表是另一个分组的扩展。例如，<A, B, C> 扩展了 <A, B>

迭代 嵌套分组 和迭代普通分组一样，例如

迭代 <A, B>
- 获取 A 和 B 的打包数组
- 遍历 [0, size_of(<A, B>)) 范围
迭代 <A, B, C>
- 在 <A, B> 的基础上，添加 C 的打包数组
- 遍历 [0, size_of(<A, B, C>)) 范围

不同分组间互不依赖，也不需要了解彼此的存在

嵌套分组必须满足包含关系，如果分组有冲突则无法实现，例如 <A, B> 和 <A, C>，它们之间不存在包含关系，无法在实体或 组件数组 中创建嵌套分区

在嵌套分组中，当让实体进入一个深层嵌套的分组时，执行顺序非常关键，如果顺序不正确，将导致分组的破坏，甚至无法恢复

假设我们有以下初始状态

A packed    : [e4|e7|e3|e8|e6]
A component : [A4|A1|A0|A2|A3]
  <A, B, C> __^
  <A, B> ___________^
 
B packed    : [e4|e7|e5]
B component : [B0|B2|B1]
  <A, B, C> __^
  <A, B> ___________^
 
C packed    : [e6|e8|e5]
C component : [C2|C0|C1]
  <A, B, C> __^

假设实体 e8 拥有组件 A 和 C，但缺少 B，因此它不属于 <A, B> 或 <A, B, C> 分组，现在为 e8 添加组件 B，并直接将其与 <A, B, C> 所指向的元素交换

A packed    : [e8|e7|e3|e4|e6]
A component : [A2|A1|A0|A4|A3]
  <A, B, C> _____^
  <A, B> ___________^
 
B packed    : [e8|e7|e5|e4]
B component : [B3|B2|B1|B0]
  <A, B, C> _____^
  <A, B> ___________^
 
C packed    : [e8|e6|e5]
C component : [C0|C2|C1]
  <A, B, C> _____^

我们发现了问题：实体 e8 确实进入了 <A, B, C> 和 <A, B>，但实体 e4 意外地退出了 <A, B>，尽管它仍然拥有 A 和 B，这是由于 操作的顺序不正确 导致的

嵌套分组规则

正确的 嵌套分组 维护需要遵循以下规则

添加组件时，按从最大分组到最小分组的顺序依次测试并交换
移除组件时，按从最小分组到最大分组的顺序依次测试并交换

正确的执行步骤如下
步骤 1：让 e8 首先进入 <A, B>
操作按 <A, B> 的指针执行

A packed    : [e4|e8|e3|e7|e6]
A component : [A4|A2|A0|A1|A3]
  <A, B, C> __^
  <A, B> ___________^
 
B packed    : [e4|e8|e5]
B component : [B0|B3|B1]
  <A, B, C> __^
  <A, B> ___________^

步骤 2：让 e8 进入 <A, B, C>
操作按 <A, B, C> 的指针执行

A packed    : [e8|e4|e3|e7|e6]
A component : [A2|A4|A0|A1|A3]
  <A, B, C> _____^
  <A, B> ___________^
 
B packed    : [e8|e4|e5]
B component : [B3|B0|B1]
  <A, B, C> _____^
  <A, B> ___________^
 
C packed    : [e8|e6|e5]
C component : [C0|C2|C1]
  <A, B, C> _____^

可以看到，e8 进入了 <A, B> 和 <A, B, C>，并且 e4 仍在 <A, B> 中，未被错误移出

代价

嵌套分组 在带来性能优化的同时，也不可避免地带来了一些额外的代价，然而，这些代价与基本分组功能中的代价是相同的，关键在于如何权衡这些代价和收益，特别是在关键路径上的性能需求

组件实例的构造和销毁成本增加
一个组件类型被更多的分组拥有，会增加构造和销毁时的处理负担
- 例如，如果一个组件类型属于 3 个分组，则在创建或删除实体时，需要额外维护所有相关的分组关系
性能衡量
虽然这些开销存在，但通常只有在极端情况下才能显现，比如同时创建或销毁大量实体（例如 1M 实体），因此，建议在实际项目中，通过测量来量化代价，并评估是否值得