通过指针与数组中的索引链接结构图

Question

这是关于良好做法的问题

考虑典型的情况,例如在3D引擎,物理引擎,有限元方法或经典分子动力学求解器中:您有各种类型的对象(例如顶点,边,面,有界实体体积)彼此交叉链接(例如顶点知道哪个边连接到它,反之亦然).对于这种引擎的使用性能和便利性,能够快速浏览这种连接的网络是至关重要的.

问题是:通过数组中的索引或指针指向链接对象是否更好？......特别是在表现方面

typedef index_t uint16_t;

class Vertex{
    Vec3 pos;
    #ifdef BY_POINTER
    Edge*   edges[nMaxEdgesPerVertex];
    Face*   faces[nMaxFacesPerVertex];
    #else
    index_t edges[nMaxEdgesPerVertex];
    index_t faces[nMaxFacesPerVertex];
    #endif
}

class Edge{
    Vec3   direction;
    double length;
    #ifdef BY_POINTER
    Vertex* verts[2];
    Faces*  faces[nMaxFacesPerEdge];  
    #else
    index_t verts[2];
    index_t faces[nMaxFacesPerEdge];
    #endif
}

class Face{
    Vec3   normal;
    double isoVal; // Plane equation: normal.dot(test_point)==isoVal
    #ifdef BY_POINTER
    Vertex* verts[nMaxVertsPerFace];
    Edge*   edges[nMaxEdgesPerFace];
    #else
    index_t verts[nMaxVertsPerFace];
    index_t edges[nMaxEdgesPerFace];
    #endif
}

#ifndef BY_POINTER
// we can use other datastructure here, such as std:vector or even some HashMap 
int nVerts,nEdges,nFaces;
Vertex verts[nMaxVerts];
Edge   edges[nMaxEdges];
Vertex faces[nMaxFaces];
#endif 

指数优势:

• 当我们使用uint8_t或uint16_t索引而不是32位或64位指针时,使用索引可以提高内存效率
• 索引可以携带一些比特编码的一些附加信息(例如关于边缘的方向);
• 数组中对象的排序可以携带一些关于结构的信息(例如,可以按顺序排列立方体的顶点{0b000,0b001,0b010,0b011,0b100,0b101,0b110,0b111}).这些信息在指针中不可见

指针的优点:

• 我们不需要关心存储对象的数组(或其他数据结构).可以简单地在堆上动态分配对象new Vertex().
• 可能更快(？)因为它不需要添加数组的基址(？).但就内存延迟而言,这可能是微不足道的(？)

Answer 1

为了提高性能，重要的是您可以按照热路径中常见的遍历顺序读取“下一个”元素的速度。

例如，如果您有一系列代表某个路径的边，则希望将它们按new连接顺序连续地存储在内存中（而不是用于每个边）。

对于这种情况（形成路径的边缘），很明显，您不需要指针，也不需要索引。连接由存储位置暗示，因此您只需要指向第一个边缘（最后一个边缘）的指针即可（即，您可以将整个路径存储在中std::vector<Edge>）。

第二个示例说明了我们可以利用的领域知识：假设我们有一个游戏最多支持8个玩家，并且想存储“谁访问了路径中的每个边缘”。同样，我们不需要指针或索引来引用这8个播放器。取而代之的是，我们可以简单地uint8_t在每个内部存储一个内部Edge并将这些位用作每个玩家的标志。是的，这是底层的敲打，但是一旦有了，它就能为我们提供紧凑的存储和高效的查找Edge*。但是，如果我们需要从播放器到Edges 在另一个方向进行查找，则最有效的方法是uint32_t在每个播放器内部存储例如vector 并在Edge数组中建立索引。

但是，如果可以在路径的中间添加和删除边缘怎么办？好吧，我们可能想要一个链表。在这种情况下，我们应该使用侵入式链表，并Edge在池中分配。完成此操作后，我们可以将指向Edges的指针存储在每个玩家对象中，并且它们永远不会更改或不需要更新。我们使用侵入式链表时要了解，an Edge只是单个路径的一部分，因此，链表指针的外部存储将很浪费（std::list需要存储指向每个对象的指针；侵入式列表不会）。

因此，必须根据我们事先发现的领域知识，单独考虑每种情况。指针和索引都不应该是第一种方法。

Answer 2

当我们使用uint8_t或uint16_t作为索引而不是32位或64位指针时,使用索引可以提高内存效率

真正.具有小的表示减少了结构的总大小,减少了遍历它时的高速缓存未命中.

索引可以携带一些比特编码的一些附加信息(例如关于边缘的方向);

真正.

我们不需要关心存储对象的数组(或其他数据结构).可以通过新的Vertex()在堆上动态分配对象.

这正是你不想做的,谈到表演.您希望确保Vertex全部打包,以避免不必要的缓存丢失.在这种情况下,数组可以避免错误的诱惑.您还希望至少尽可能多地按顺序访问它们,以最大限度地减少缓存未命中.

数据结构的打包量,小数量和按顺序访问的数量实际上是驱动性能的因素.

可能更快(？)因为它不需要添加数组的基址(？).但就内存延迟而言,这可能是微不足道的(？)

可能微不足道.可能取决于特定的硬件和/或编译器.

索引的另一个缺失优势:重新分配时更容易管理.考虑一个可以增长的结构,如下所示:

struct VertexList
{
  std::vector<Vertex> vertices;

  Vertex *start; // you can still access using vector if you prefer; start = &vertices[0];
}

如果使用指针引用给定顶点,并且发生重新分配,则最终会出现无效指针.