任何程序员都将从对各种
数据结构以及如何分析其性能的了解中受益。 但是实际上，对于
AVL树 ，
红黑树 ，
前缀树 ，
跳过列表等，我从来没有派上用场。 我仅将某些数据结构用于一种特定算法，而仅用于某种数据结构（例如，用于在
A *路径搜索算法中实现
优先级队列的 堆 ）。
在日常工作中，我通常只使用很少的数据结构。 大多数情况下，它们对我有用：
- 共享数据数组（批量数据）-一种有效存储大量对象的方法。
- 弱引用（或句柄 ）-如果删除对象，则在批量数据中访问对象而不会导致程序崩溃的一种方法。
- 索引是一种快速访问批量数据中各个子集的方法。
- 数组数组是一种存储具有动态大小的批量数据对象的方法。
我将写几篇文章介绍我通常如何实现所有这些结构。 让我们从最简单，最有用的-批量数据开始。
批量数据
这个概念没有通用术语（或者我不知道）。 我将大量的相似对象称为“
批量数据 ”。 例如，可能是：
- 游戏中的所有子弹。
- 游戏中的所有树木。
- 游戏中的所有硬币。
或者，如果您以更高的抽象级别编写代码，则可能是：
- 游戏中的所有实体。
- 游戏中的所有网格。
- 游戏中的所有声音。
通常，游戏中的每个系统（渲染，声音，动画，物理等）都需要跟踪几个不同类型的对象。 例如，对于一个音响系统，它可能是：
- 可以播放的所有声音资源。
- 当前正在播放的所有声音。
- 所有效果（衰减，音调变化等）都将应用于声音。
对于批量数据，我将假设以下内容：
- 对象的存储顺序并不重要。 即 我们将数组视为许多对象。
- 每个对象都表示为一个固定大小的简单数据结构（POD结构） ，可以使用
memcpy()进行移动或复制。
当然，您可以提出顺序很
重要的情况 。 例如，如果对象表示要渲染的元素，则在渲染之前，我们可能需要从前到后对它们进行排序，以减少
重绘的次数 。
但是，我相信在大多数情况下，最好对使用的数据进行排序，而不是将数据存储在已排序的容器中，例如
红黑树或
B树 。 例如，我们可以在将渲染的对象传递到渲染器之前从前到后对它们进行排序，或者在将它们作为列表显示在屏幕上之前按字母顺序对文件进行排序。 对每个帧中的数据进行排序似乎成本很高，但是在许多情况下，使用
基数排序可以在
O（n）中完成。
由于我仅使用简单的数据结构，因此我更喜欢C ++对象而不是C ++对象，因为这样可以更轻松地了解内存中发生的情况并评估其性能。 但是，在某些情况下，您需要批量存储没有固定大小的数据。 例如，子对象的名称或列表。 我将在另一篇文章中讨论这些情况，我们将介绍“数组的数组”。 现在，让我们假设所有对象都是简单的，固定大小的数据结构。
例如，假设的声音系统的批量数据结构如下所示：
typedef struct { resource_t *resource;
在考虑存储批量数据的方法时，我们需要考虑两个目标：
- 添加和删除对象应该很快。
- 数据应以方便缓存的形式放置 ，以便您可以快速对其进行迭代以更新系统。
- 它必须支持链接机制 -必须有一种方法来传输有关批量数据中特定对象的信息。 在上面的示例中，淡入淡出应该能够指定衰减的声音。 在示例中，我将链接写为指针，但是它们的实现取决于批量数据的排列方式。
- 数据必须是友好的分配器 -它必须使用多个大内存分配，并且不能在堆上分配单个对象。
表示批量数据的两种最简单的方法是静态数组或C ++向量：
使用数组非常简单，如果您确切知道应用程序中需要多少个对象，它就可以很好地工作。 如果您
不知道这一点 ，那么要么浪费内存，要么用完对象。
向量
std::vector也是一个非常有价值且简单的解决方案，但是在这里您需要考虑一些方面：
- 由于调试迭代器，Visual Studio中
std::vector的标准实现在“调试”模式下运行缓慢。 它们应该设置为_ITERATOR_DEBUG_LEVEL = 0 。 - 要创建和销毁对象，
std::vector使用构造函数和析构函数，在某些情况下，它们的速度可能比memcpy()慢得多。 - 与实现简单的“可伸缩缓冲区”相比，
std::vector解析起来困难得多。
此外，没有其他措施，规则数组和向量都不支持对单个对象的引用。 让我们看一下本主题，以及创建批量数据系统时涉及的其他重要设计决策。
清除策略
第一个重要决定：删除对象
a[i]时应该做什么。 这是三个主要选项：
- 您可以移动所有后续元素
a[i+1] → a[i] ， a[i+2] → a[i+1]等，以关闭一个空插槽。 - 您可以将数组的最后一个元素移到一个空插槽：
a[i] = a[n-1] 。 - 或者，您可以通过在阵列中创建孔来将插槽留空。 以后可以使用此孔放置新对象。
第一个选择很糟糕
-O（n）花在所有这些元素的运动上。 第一种方法的唯一好处是，如果对数组进行排序，则将保留其中的顺序。 但是如上所述，订单并没有打扰我们。 请注意，如果您使用
a.erase()删除
std::vector元素，则将发生这种情况！
第二种选择通常称为“交换和弹出”。 怎么了 因为如果使用C ++向量，通常通过将要删除的元素替换（交换）为最后一个元素，然后删除或弹出最后一个元素来实现此选项：
std::swap(a[i], a[a.size() - 1]); a.pop_back();
为什么这一切都是必要的？ 在C ++中，如果我们
分配 a[i] = a[n-1] ，则必须首先通过调用其析构函数来删除
a[i] ，然后调用copy构造函数在位置
i和位置创建
a[n-1]的副本。最后，我们在移动向量时将析构函数
a[n-1] 。 如果复制构造函数分配内存并复制数据，那么这可能很糟糕。 如果我们使用
std::swap而不是赋值，那么我们只能使用构造函数移动而不应该分配内存。
同样，这就是为什么C ++我更喜欢简单的数据结构和C操作。如果您不知道内部发生了什么，C ++就会有很多性能陷阱。 在C语言中，交换擦除操作将非常简单：
a.data[i] = a.data[--an];
使用交换弹出时，对象保持紧密包装。 要放置新对象，只需将其附加到数组的末尾即可。
如果我们使用“有孔”选项I，则在放置新对象时，我们首先需要检查是否有任何可用的“孔”。 仅当没有空闲的“孔”时，才值得增加阵列的大小。 否则，在删除和创建对象的过程中，它将无限期地增长。
您可以使用单独的
std::vector<uint32_t>来跟踪孔的位置，但是有一个更好的解决方案，不需要额外的内存。
由于“孔”中对象的数据没有任何用处，因此您可以使用它存储指向下一个空孔的指针。 因此，数组中的所有孔都构成一个
简单的连接列表 ，并且如有必要，我们可以从中添加和删除元素。
这种类型的数据结构（其中未使用的内存用于绑定自由元素）通常称为
自由列表 。
在传统的链接列表中，特殊的列表
头元素指向列表中的第一个节点，最后一个列表元素指向NULL，这表示列表的末尾。 相反，我更喜欢使用
循环链接列表 ，其中标题只是一个特殊的列表项，最后一个列表项指向heading元素：
传统和环形链接列表。这种方法的优点是，通过减少列表开头和结尾的特殊情况的数量，代码变得更加简单。
请注意，如果您使用
std::vector来存储对象，则对象的指针将随着vector的每次重新分布而改变。 这意味着我们不能使用指向链接列表的常规指针，因为指针在不断变化。 要解决此问题，您可以将索引用作链接列表的“指针”，因为即使重新分配数组，索引也始终指向特定的插槽。 在下一节中，我们将详细讨论重新分配。
通过始终将其存储在数组插槽0中，可以为列表标题的特殊元素分配空间。
该代码将如下所示：
最好的清除策略是什么？ 将最后一个元素移到一个空插槽中，以确保数组紧密包装或通过在数组中创建“空洞”来代替已删除元素来将所有元素保持在原位？
做出决定时，必须考虑两个方面：
- 在密集阵列上进行迭代的速度更快，因为我们绕过了更少的内存，并且不必花费太多时间跳过空插槽。
- 如果我们使用紧密排列的数组，则元素将移动。 这意味着我们不能将元素的索引用作元素外部引用的常量标识符。 我们将不得不为每个元素分配一个不同的标识符，并使用查找表将这些常量ID与当前对象索引进行匹配。 如上所述，此查找表可以是哈希表或带孔的
std::vector （第二个选项更快）。 但是，尽管如此，我们将需要用于此表的额外内存和用于标识符的额外间接步骤。
选择最佳选项取决于您的项目。
您可以说存储密集的数组更好，因为与匹配外部链接相比，对所有元素（以更新系统）进行迭代的频率更高。 另一方面，我们可以说“有孔阵列”的性能仅在有大量孔的情况下才会变差，并且在游戏开发中，我们通常会在
最坏的情况下关注性能（即使在游戏中执行最大操作时，我们也希望帧频为60 Hz） 。 在最坏的情况下，我们拥有最大数量的实际对象，在这种情况下，数组
中将没有孔 。 只有当对象数量减少时，当我们删除其中一些对象时，才会出现孔洞。
也可以使用一些策略来加速具有多个孔的阵列的处理。 例如，我们可以跟踪连续孔序列的长度，以一次跳过整个孔序列，而不是逐个元素。 由于此数据仅用于“漏洞”，而对于普通元素则不需要，因此您可以将它们与发布列表的指针一起存储在对象的未分配内存中，而不会浪费额外的内存。
我认为，如果您不需要为快速迭代而优化代码，那么最好使用“带孔阵列”选项。 它更简单，不需要其他搜索结构，并且可以将对象的索引用作其ID，这非常方便。 此外，缺少移动物体消除了可能的错误。
批量数据删除策略。弱指针
值得注意的是，我很容易实现对批量数据对象的“弱指针”或“描述符”的支持。
弱指针是对对象的引用，可以以某种方式确定它所引用的对象已被删除。 弱指针的方便之处在于它们使您可以删除对象，而不必担心谁可以引用它们。 如果没有弱指针来删除对象，我们将需要搜索每个单独的链接并将其声明为无效。 如果链接以脚本代码存储在网络上的其他计算机上，则这可能特别困难。
请记住，我们已经有一个ID，用于唯一标识
现有对象。 在“有孔”选项中，此ID只是元素的索引（因为元素永不移动）。 对于密集排列的数组，此对象索引是
search数组中的记录。
ID本身不能用作弱指针，因为ID可以重复使用。 如果删除了一个元素，并且在同一位置创建了一个新元素，那么我们将无法仅凭ID来确定它。 要获得弱指针，您需要将ID与
generation字段结合使用：
typedef struct { uint32_t id; uint32_t generation; } weak_pointer_t;
generation字段是对象结构中的一个字段，该字段跟踪批量数据阵列中的插槽已重复使用了多少次。 （在紧密打包的情况下，它会跟踪该插槽在
搜索数组中已被重用了多少次。）
删除项目时，我们会增加其插槽中的世代号。 为了检查弱指针是否仍然有效，我们检查弱指针结构中的生成是否与其
id指示的插槽的生成匹配。 如果它们匹配，则我们引用的源对象仍然存在。 如果不是，则表示已删除该插槽，并且该插槽在发布列表中或已被重新使用。
请记住，由于
generation字段对于孔和现有对象都是必需的，因此您需要将其存储在联合之外：
typedef struct { uint32_t generation; union { object_t; freelist_item_t; }; } item_t;
分销策略
如果使用
std::vector来存储元素数据，则当数组已满并且需要增加时，将重新分配整个元素数组。 现有项目将复制到新数组。
std::vector 几何增长。 这意味着每当需要增加向量时，分布元素的数量就会乘以某个因子（通常乘以×2）。 几何（指数）增长很重要，因为它使增加阵列的成本保持恒定。
重新分配数组时，我们需要移动所有元素，这需要
O（n） 。 但是，随着数组的增长，我们为另外
n个元素增加了空间，因为我们将大小增加了一倍。 这意味着，除非我们向其添加
n个元素，否则无需再次增加数组。 也就是说，增加成本等于
O（n） ，但是我们仅在写入数组的第n次执行它们* O（n）*，也就是说，平均而言，写入一个元素的成本为
O（n）/ O（n）= O（1） 。
记录项目的成本称为
摊余常数 ，因为如果将所有正在执行的记录平均，则成本将是固定的。 但是，我们不要忘记，在平均之前，成本变得非常不稳定。 在每个
O（n）记录之后，我们得到一个高度
O（n）的峰值：
写入std::vector的成本。我们还要看看如果不使用几何增长会发生什么。 假设，我们不会在增长期间使内存增加一倍，而只是添加另外128个插槽。 移动旧数据仍然使我们付出
O（n）的代价，但现在我们需要每添加128个项目就要做一次，即现在的平均成本为
O（n）/ O（128）= O（n） 。 将元素写入数组的成本与数组的大小成正比，因此，当数组变大时，它将以乌龟速度开始工作。 糟糕！
std::vector分配策略是一个很好的标准选项，在大多数情况下都可以正常工作，但存在一些问题：
- 摊销常数不适用于实时软件。 如果您有一个非常大的数组（例如，数亿个元素），那么增加此数组并移动所有元素会导致帧速率明显下降。 出于同样的原因，这也是有问题的，因为垃圾回收在游戏中会带来问题。 平均成本有多低无关紧要，如果在某些帧中成本会上升，从而导致游戏故障。
- 同样，在大型阵列的情况下，这种分配策略可能会浪费大量内存。 假设我们有一个1600万个元素的数组，我们需要在其中写入另一个元素。 这将使阵列增加到3200万。 现在，阵列中有1,600万个我们没有使用的元素。 对于内存不足的平台，这很多。
- 最后，重新分配将对象移动到内存中，使所有指向对象的指针无效。 这可能是难以跟踪的错误的来源。
以下代码是移动对象时可能发生的错误的示例：
这里的问题是，
allocate_slot()函数可能需要重新分配数组以为
item_2创建空间。 在这种情况下，
item_1将被移至内存，而指向
item_1的指针将不再有效。 在这种特殊情况下，我们可以通过移动分配
item_1来消除错误，但类似的错误可能会更明显地出现。 就个人而言，他们已经咬了我很多次。
由于只有在分配
slot_2的那一刻
slot_2完全重新分配阵列时，错误才会出现，因此这种情况是不正确的。 该程序可以长时间正常工作，直到某些情况下更改了分布模式，此后该bug才可以工作。
所有这些问题都可以使用不同的分配策略来解决。 以下是一些选项：
- : 16, 32, 64, …, . , 16 , 32 , .… ,
std::vector . - , . , . . , O(n)
push() , . - , , , , .
我再说一遍，每种方法都有其自身的优缺点。后者很好，因为元素仍然彼此相邻地存储在内存中，并且我们需要跟踪单个缓冲区，因此不需要其他向量或列表。它需要设置数组的最大大小，但是虚拟地址的空间是如此之大，以至于您通常可以指定任何数量的数字而没有丝毫问题。, — ? , . , 16 , 16 , . , , 50 %. .
,
, , . *16 K * n*,
n — bulk data , , ( ).
. -, ,
blocks\[i / elements_per_block\][i % elements_per_block] . -, , (heap allocator), .
, « », -
std::vector , , . , , .
, , ID . , , . , 64 , 32 (4 — ).
(Array of Structures, AoS)
(Structure of Arrays, SoA). . , , , , :
typedef struct { float t; vec3_t pos; vec3_t vel; vec3_t col; } particle_t;
struct . « ». :
uint32_t num_particles; particle_t *particles;
, .
(SoA) struct:
uint32_t num_particles; typedef struct { float *t; vec3_t *pos; vec3_t *vel; vec3_t *col; } particles;
实际上，我们可以走得更远，因为vec3_t它本身就是一个结构： uint32_t num_particles; typedef struct { float *t; float *pos_x; float *pos_y; float *pos_z; float *vel_x; float *vel_y; float *vel_z; float *col_r; float *col_g; float *col_b; } particles;
这似乎比我们最初的AoS方案复杂得多，那为什么真的有必要呢？有两种说法支持这种方法：- 一些算法仅适用于字段的子集。例如，一种算法
tick()仅影响field t。该算法simulate_physics()仅影响字段pos和vel。在SoA方案中，仅将结构的某些部分加载到内存中。如果我们受到内存的限制（现代处理器通常就是这种情况），那么这可能会产生很大的影响。例如，一个函数tick()只会影响1/10的内存，这意味着它获得10倍的加速。 - SoA方案使我们可以将数据直接加载到SIMD寄存器中进行处理。如果我们仅限于FPU，这可能会产生很大的影响。使用AVX，我们可以一次处理八个浮点数，这可以使速度加快8倍。
这是否意味着在这些加速下tick()它将变得更快80？不行
仅当我们完全受内存限制时，我们才会获得10倍的首次加速；如果我们完全受内存限制，则SIMD将无法使我们更快地工作。SoA方法的缺点：- 代码变得越来越棘手。
- 分配器承受的压力更大，因为我们需要分配十个单独的阵列而不是一个点。
particle_t * , . .- ,
- ( ), . , .
, , struct , VM ( ). - 10 struct . 8- -, , . !
— SIMD. :
uint32_t num_particles; typedef struct { float t[8]; float position_x[8]; float position_y[8]; float position_z[8]; float velocity_x[8]; float velocity_y[8]; float velocity_z[8]; float color_r[8]; float color_g[8]; float color_b[8]; } eight_particles_t; eight_particles_t *particles;
在这种方案中，我们仍然可以使用SIMD指令一次处理8个粒子，但是一个粒子的字段在内存中非常接近，并且对于之前出现的高速缓存行冲突没有任何问题。这对于分配系统更好，因为我们回到了整个粒子阵列的一个分配。在这种情况下，该算法tick()将影响32个字节，跳过288个字节，影响32个字节等。这意味着我们将无法获得完整的10倍加速，就像在单独的阵列中一样t . -, - 64 , , , 5 . , , -, 100% .
, . ,
[16] , float - . , , , :
AoS SoA., SoA — « », SIMD , ( «»).
SIMD- «» , , , «» . , ,
, .
next , SIMD- . struct.
, , , struct . , , .
AoS SoA, , . «» AoS SoA , SIMD-, , . .
— AoS SoA - . , AoS SoA, , AoS ( ). , , .
, « ». 16- , SoA, . scratch buffer 16 .
结论
, « » bulk data :
«» , VM ( ), ( 16 , ).
, :
, 8 SIMD VM .
.