c++26 std::hive简析

Posted on Edited on

为了让魔法棒更像魔法棒，快速生成和销毁的粒子效果彻底摧毁了内存的秩序。但至少现在，粒子效果能够在蜂巢结构的六边形单元格里完成量子隧穿。

std::hive目前已经由标准委员会投票确定正式进入 C++26标准。std::hive 的标准化过程可谓是一波三折，P0447 提案最早于 2019 年提出，在五年的时间里经过了大量修改，目前已经有了 28个历史版本。因为之前尝试过游戏开发，被内存碎片的问题折磨的头疼不已，所以当发现一个专为游戏设计的数据结构进入了STL时，非常好奇其设计理念和实现方式。经过一番检索后，稍微总结了一下，接下来本文将对std::hive 的使用场景及其实现方法进行介绍。

对象池

后端性能优化存在着经典的三板斧——异步、分治、复用。

  • 异步：例如同步任务转异步，实现流程解耦，类似于 MQ（Message Queue，消息队列）的设计理念 ；例如在批处理过程中，先进行异步并发处理，最后再对结果聚合汇总，类似于 go 中 sync.WaitGroup 的设计理念；
  • 分治：针对高强度任务，可以化整为零，把工作量分治到多个预处理操作中，将蜂屯蚁聚化解为细水长流，类似于 go 中 map渐进式扩容的设计理念；
  • 复用：对于高频使用的资源类型进行循环利用，而非重复创建销毁，例如池化技术的设计理念。

此外，在某些场景中，程序可能需要动态创建、访问、修改、删除大量的对象，这些对象内持有其他对象的引用（指针），所有对象依靠对象间的引用相互交织起来形成一张复杂的、表达特定业务信息的网络。典型的例子是游戏场景，游戏中会包含大量人物角色、武器、物品等游戏元素，每个元素都由一个对象进行表示，程序会动态创建和删除游戏元素，且元素间会存在复杂的关系网络和交互。类似的设计需求在物理模拟仿真、编译器、图计算等领域也存在。

对于上述后端性能优化和使用场景的需求，程序中通常会使用对象池（object pool）来管理资源对象。对象池有多种名称，其他常见的名称包括 arena、chunked array 等等。对象池的设计和实现方法取决于使用需求，一般来说通用对象池应该具备如下的功能特性：

  • 支持向对象池中动态增加和删除对象；
  • 支持遍历对象池中已有的对象；
  • 对象池中的对象的地址是固定的，这样对象池的使用者可以简单地通过保存对象的指针来引用对象池中的对象。

std::hive 就是一个具备上述功能特性的通用对象池，它拥有以下一些重点功能和特性：

  • std::hive 是一个同质容器，其中存放的对象的类型是固定的，由 std::hive 的模板参数给出。
  • 程序可以动态地向 std::hive 中增加对象，可以动态地从 std::hive 中删除对象。std::hive 是一个带所有权的容器，在其析构时会同时析构其中包含的所有对象。增加或删除单个对象的时间复杂度均为 。
  • std::hive 支持遍历操作。std::hive 的迭代器是双向迭代器，不支持随机访问。std::hive 中的对象是无序的，也就是遍历对象的顺序是不确定的，和插入对象的顺序无关。迭代器前进或后退一步的时间复杂度均为 。
  • std::hive中包含的所有对象的地址都是固定的。也就是说：
    • 在向 std::hive 中插入新对象时，保证所有指向已有对象的指针和迭代器都不会失效。
    • 在从 std::hive 中移除对象时，除了指向被移除的对象的指针和迭代器外，保证所有指向其他对象的指针和迭代器都不会失效。

实现方法

其实已经存在一个标准容器满足前面所列出的所有要求，即 std::list 。但是将 std::list 用作对象池并不是最理想的方案，尤其是在对性能较为敏感时。这是因为：

  • std::list 在每次插入和删除对象时都需要分配或释放内存，这可能会造成内存碎片化并拖累性能；
  • std::list 中包含的对象往往在内存空间中不连续，空间局部性较差，在需要对对象进行遍历访问的场合无法利用高速缓存的优势。

std::hive 通过一系列手段缓解了 std::list 的这些问题，使之更适合于对象池的使用场景。

块

为了提升空间局部性，std::hive 会将对象组织到尽可能连续的内存空间中。在 std::hive 内部，存储若干空间上连续的对象的结构称为块（block）。下图展示了一个拥有一个块的 std::hive：

One Block Hive

上图中展示的块的容量（capacity）为 4，即这个块中一共可容纳 4 个空间上连续的对象。这个块中已经存放了 3 个对象，以蓝色方框进行标记。剩余的一个以白色方框标记的空间为空闲空间，可容纳一个新对象。

如果在块已满时需要向 std::hive 中插入新对象，std::hive 会分配一个新的块用于存放新对象。块的容量会呈指数增长，这样可以减少块的分配次数，提升性能。属于同一个 std::hive 的多个块使用链表连接起来。下图展示了一个块容量增长倍数为 2 的、拥有两个块的 std::hive：

Two Block Hive

从 std::hive 中删除一个元素后，如果块中的对象数量变为 0，那么这个块将被从块链表中移除并释放。另外，在删除一个元素后，空间上原本连续存放的多个对象可能变得不连续，他们之间可能会出现“空泡”。下图展示了一种可能的情况：

Free Slots

“空泡”的存在给插入和遍历操作都带来了麻烦。对于插入操作，我们希望在插入新对象时应尽可能复用已有的“空泡”所占用的空间，减少额外的内存分配和内存占用。此外，我们仍然希望能够在 的时间内找到可用的“空泡”。对于遍历操作，我们希望能在遍历时快速地跳过这些“空泡”，使得前进或后退一步的时间复杂度仍为 。为了实现这些目标，std::hive 需要额外两个数据结构，第一个结构名为空闲链表（free list），另一个结构名为跳跃域（skip field）。这两个结构相辅相成，可以说是 std::hive 的核心设计。

跳跃域

跳跃域是一个块级结构，即每个块都有一个跳跃域。一个跳跃域是一个整数数组，其长度和块的容量一致。跳跃域中的每个元素都和块中的每个对象或“空泡”形成一一对应关系，下图展示了前面的图示中的两个块的跳跃域：

Skipfield

我将某些跳跃域的元素标记为了“-”是因为这些跳跃域中的值没有意义，不会影响 std::hive 的操作。只有对象所对应的跳跃域元素、以及每个连续“空泡”的第一个和最后一个“空泡”所对应的跳跃域元素是有意义的，连续“空泡”内部的跳跃域元素没有意义。对象所对应的跳跃域元素均为 0，而“空泡”所对应的跳跃域元素为连续“空泡”的长度。

跳跃域的存在是为了加速遍历操作，使得遍历操作能够快速跳过“空泡”。具体来说，在有了跳跃域后，若当前的跳跃域元素为 0，说明当前的位置上存在一个对象。若当前的跳跃域元素不为 0，则说明存在“空泡”，将指向当前位置的指针向前或向后移动跳跃域元素所指示的距离后即可得到下一个对象的位置。如果当前位置跳出了当前块的边界，则前往下一个块继续执行遍历。由于每个块中都至少存在一个有效的对象，因此迭代器每次前进或后退一步都至多跳跃两次即可找到下一个有效的对象，因此单步遍历的时间复杂度保证为 。

跳跃域本质上是指示了每个连续“空泡”的长度，也就间接指示了每个连续“空泡”的第一个和最后一个“空泡”的位置。另外，对于每个连续“空泡”，只需要维护其中第一个和最后一个“空泡”的跳跃域元素。知晓了这一点后，很容易可以构造出跳跃域的快速更新方法。在删除一个对象时，std::hive 检查被删除对象的前后是否存在“空泡”。若前后均不存在“空泡”，那么将被删除对象所对应的跳跃域置为 1 即可。若前后只存在一个连续“空泡”，则将被删除对象的位置合入该连续“空泡”即可。若前后均存在连续“空泡”，则将这两个连续“空泡”合并为一个。这里的跳跃域更新算法读者可以很容易自行构造出来。在插入一个对象时，我们将在后面看到，对于每个连续的“空泡”，插入操作将按照位置顺序从前向后依次分配每个“空泡”。因此，在插入一个对象时，连续“空泡”的第一个“空泡”将被分配出去供对象占用，这里的跳跃域更新算法也很容易构造出来。

空闲链表

跳跃域仅仅指示了每个连续“空泡”的长度，并不足以使得插入操作能够枚举当前存在的所有“空泡”。为了能够让插入操作能够枚举 std::hive 中存在的所有“空泡”，还需要空闲链表这一结构。熟悉内存分配器的读者应该不会对空闲链表感到陌生，std::hive 也使用了这一结构来将所有的“空泡”链接起来，形成一个供插入操作枚举的“空泡”链表。

首先，std::hive 会使用一个单独的链表将所有包含“空泡”的块链接起来，如下图中的红色链接所示：

Free block link

在所有有“空泡”的块内部，std::hive 也会使用一个链表将所有连续的“空泡”的第一个“空泡”链接起来，如下图中的紫色链接所示：

Free slot link

通过跳跃域即可得知连续“空泡”的长度，因此空闲链表并没有将所有的“空泡”全部链接起来，而只需要链接每一段连续“空泡”的第一个“空泡”即可。通过这样的两级空闲链表，插入操作可以在 的时间内找到下一个可用的“空泡”，并在 的时间内将“空泡”分配出去。

此外，空泡链表节点在实现上其实是复用了空泡的存储空间，空泡链表是一个双向链表，利用空泡的存储空间存储了指向上一个和下一个空泡的链接指针。可以使用union共用体来实现空间的复用，减少内存的消耗。

块、跳跃域和空闲链表是 std::hive 的核心数据结构。利用这些数据结构，std::hive 可以在 的时间内完成对象的插入、删除和单步遍历操作，并满足其功能性要求。

接口

本节将简单介绍 std::hive 提供的接口。由于 std::hive 是一个标准容器，其接口设计和其他标准容器的接口非常类似：

  • 使用 insert 或 emplace 插入对象。注意由于 std::hive 是一个无序容器，因此不存在有序容器才会提供的 push_back 接口、 push_front 接口或指定插入位置的 insert 接口。
  • 使用 erase 删除对象，使用 clear 删除所有对象。
  • 使用 begin 和 end 获取容器首尾迭代器。
  • 使用 empty 查询容器是否为空，使用 size 查询容器中对象的数量。
  • 使用 reserve 为容器预留空间，使用 capacity 查询容器的总容量。

另外，std::hive 还提供了一个独特的成员函数 get_iterator 。这个成员函数接收一个对象指针，返回一个指向该对象的迭代器。在对象池的使用场景中，用户通常会直接使用对象的指针来引用对象池中的对象，因此这个成员函数让用户可以方便地将对象指针转换为迭代器，从而在对象池中定位该对象。
end☆~