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

Question

这是关于良好实践的问题

考虑典型的情况，例如在 3D 引擎、物理引擎中，Finite element method或 classical molecular dynamics求解器:你有各种类型的对象(例如顶点、边、面、有界实体体积)，它们相互交叉链接(例如顶点知道哪条边连接到它，反之亦然)。为了性能和使用方便，这种引擎对于能够快速浏览这种连接的网络至关重要。

问题是:通过数组中的索引或指针指向链接对象更好吗？ ...尤其是性能方面

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() 在堆上简单地动态分配对象。
• May be faster (?)因为它不需要添加数组的基地址(？)。但这在内存延迟方面可能可以忽略不计(？)

Answer 1

using index can be more memory efficient when we use uint8_t or uint16_t for index instead of 32-bit or 64-bit pointer

没错。具有较小的表示可减少结构的总大小，从而减少遍历时的缓存未命中。

index can carry some additional information ( e.g. about orientation of edge ) encoded in some bits;

是的。

We don't need to care about the arrays (or other data-structures) to store the objects. The objects can be simply allocated dynamically on the heap by new Vertex().

就性能而言，这正是您不想做的。 您要确保 Vertex 全部打包，以避免不必要的缓存丢失。 在这种情况下，阵列可以使您免受错误的诱惑。 您还希望至少尽可能多地按顺序访问它们，以尽量减少缓存未命中。

数据结构的打包程度、大小和顺序访问的程度，才是真正插入性能的因素。

May be faster (?) because it does not need to add the base address of the array (?). But this is probably negligible with respect to memory latency (?)

可能可以忽略不计。可能取决于特定的硬件和|或编译器。

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

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

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

如果您使用指针引用给定的顶点，并且发生了重新分配，您最终会得到一个无效的指针。