Связывание графиков структур по указателю и индексу в массиве

Question

Это вопрос о хорошей практике

Рассмотрим ситуацию, которая типична, например, для трехмерных движков, физических движков, метода конечных элементов или классических решателей молекулярной динамики: у вас есть объекты различных типов (например, вершины, ребра, грани, ограниченные сплошные объемы), которые сшиты друг с другом (например, вершина знает, какие ребра с ней связаны и наоборот). Для производительности и удобства использования такого движка крайне важно иметь возможность быстро просматривать сеть таких соединений.

Вопрос в следующем: лучше ли указывать на связанный объект по индексу в массиве или по указателю?... особенно с точки зрения производительности

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

использование индекса может быть более эффективным при использовании памяти, когда мы используем uint8_t или uint16_t для индекса вместо 32-битного или 64-битного указателя

Правда. Небольшое представление уменьшает общий размер структуры, уменьшая потерю кэша при его обходе.

индекс может нести некоторую дополнительную информацию (например, об ориентации края), закодированную в некоторых битах;

Правда.

Нам не нужно заботиться о массивах (или других структурах данных) для хранения объектов. Объекты могут быть просто динамически размещены в куче с помощью нового Vertex().

Это именно то, что вы не хотите делать, если говорить о выступлениях. Вы хотите быть уверены, что все вершины упакованы, чтобы избежать отсутствия ненужного кэша. В этом случае массив избавит вас от этого неправильного соблазна. Вы также хотите получить к ним доступ последовательно, по крайней мере, насколько это возможно, снова, чтобы минимизировать потерю кэша.

Насколько объем вашей структуры данных упакован, мал и доступен последовательно, это то, что на самом деле повышает производительность.

Может быть быстрее (?), Потому что не нужно добавлять базовый адрес массива (?). Но это, вероятно, незначительно в отношении задержки памяти (?)

Возможно незначительный. Вероятно, зависит от конкретного оборудования и | или компилятора.

Еще одно недостающее преимущество индекса: проще управлять при перераспределении. Рассмотрим структуру, которая может расти, например:

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

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

Если вы ссылаетесь на данную вершину, используя указатели, и происходит перераспределение, вы получите неверный указатель.

Answer 2

Для производительности важна скорость, с которой вы можете читать "следующий" элемент в любом порядке обхода, который обычно выполняется в горячем пути.

Например, если у вас есть ряд ребер, которые представляют некоторый путь, вы бы хотели, чтобы они сохранялись непрерывно в памяти (не используя new для каждого), в том порядке, в котором они связаны.

В этом случае (ребра образуют путь) ясно, что вам не нужны указатели, а также вам не нужны индексы. Соединения подразумеваются местами хранения, поэтому вам просто нужен указатель на первый и, возможно, последний ребра (т.е. вы можете сохранить весь путь в std::vector<Edge>).

Второй пример, иллюстрирующий знание предметной области, которое мы можем использовать: представьте, что у нас есть игра, поддерживающая до 8 игроков, и мы хотим сохранить "кто посетил каждый край пути". Опять же, нам не нужны указатели или индексы для обозначения 8 игроков. Вместо этого мы можем просто хранить uint8_t внутри каждого Edge и использовать биты в качестве флагов для каждого игрока. Да, это низкоуровневое разбиение битов, но оно дает нам компактное хранилище и эффективный поиск, как только мы получим Edge*, Но если нам нужно сделать поиск в другом направлении, от игроков к Edges, наиболее эффективным будет хранить, например, вектор uint32_t внутри каждого игрока и сделать индексацию в Edge массив.

Но что, если края могут быть добавлены и удалены в середине пути? Ну, тогда мы могли бы хотеть связанный список. В этом случае мы должны использовать навязчивый связанный список и выделить Edgeс в бассейне. Сделав это, мы можем хранить указатели на Edges в каждом объекте игрока, и они никогда не изменятся или не нуждаются в обновлении. Мы используем навязчивый связанный список с пониманием того, что Edge является только частью одного пути, поэтому внешнее хранение указателей связанного списка будет расточительным (std::list необходимо хранить указатели на каждый объект; навязчивого списка нет).

Таким образом, каждый случай должен рассматриваться индивидуально, с таким большим знанием предметной области, которое мы можем обнаружить заранее. Ни указатели, ни индексация не должны быть первым подходом.