4

这是关于良好实践的问题

考虑典型的情况，例如在 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()。
  • 可能更快（？），因为它不需要添加数组的基地址（？）。但这在内存延迟方面可能可以忽略不计（？）
4

2 回答 2

5

对于性能，重要的是您可以按照热路径中通常执行的任何遍历顺序读取“下一个”元素的速度。

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

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

第二个例子说明了我们可以利用的领域知识：假设我们有一个最多支持 8 个玩家的游戏，并且想要存储“谁访问了路径中的每个边缘”。同样，我们不需要指针或索引来引用 8 个玩家。相反，我们可以简单地uint8_t在每个内部存储一个Edge并将这些位用作每个玩家的标志。是的，这是低级位碰撞，但一旦我们拥有一个Edge*. 但是如果我们需要在另一个方向上进行查找，从玩家到Edges，最有效的方法是在每个玩家内部存储一个向量，然后对数组uint32_t进行索引。Edge

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

因此，每个案例都必须单独考虑，尽可能多地了解我们可以提前发现的领域。指针和索引都不应该是第一种方法。

于 2016-04-21T09:39:24.883 回答
5

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

真的。具有较小的表示会减小结构的总大小，从而在遍历它时减少缓存未命中。

索引可以携带一些以某些位编码的附加信息（例如关于边缘的方向）；

真的。

我们不需要关心数组（或其他数据结构）来存储对象。对象可以简单地通过 new Vertex() 在堆上动态分配。

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

你的数据结构有多少被打包、很小和按顺序访问，才是真正推动性能的因素。

可能更快（？），因为它不需要添加数组的基地址（？）。但这在内存延迟方面可能可以忽略不计（？）

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

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

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

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

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

于 2016-04-21T10:54:55.923 回答