Связывание графиков структур по указателю и индексу в массиве
Это вопрос о хорошая практика
Рассмотрим ситуацию, которая типична, например, в 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(), - Может быть быстрее (?) потому что не нужно добавлять базовый адрес массива (?). Но это, вероятно, незначительно в отношении задержки памяти (?)
Решение
использование индекса может быть более эффективным при использовании памяти, когда мы используем uint8_t или
uint16_t для индекса вместо 32-битного или 64-битного указателя
Правда. Небольшое представление уменьшает общий размер структуры, уменьшая потерю кэша при его обходе.
Индекс может нести некоторую дополнительную информацию (например, об ориентации
края) кодируется в несколько битов;
Правда.
Нам не нужно заботиться о массивах (или других структурах данных), чтобы
хранить объекты. Объекты могут быть просто динамически размещены на
куча новой вершины ().
Это именно то, что вы не хотите делать, если говорить о выступлениях.
Вы хотите быть уверены, что все вершины упакованы, чтобы избежать отсутствия ненужного кэша.
В этом случае массив избавит вас от этого неправильного соблазна.
Вы также хотите получать к ним доступ последовательно, по крайней мере, насколько это возможно, снова, чтобы минимизировать потерю кэша.
Насколько объем вашей структуры данных упакован, мал и доступен последовательно, это то, что на самом деле повышает производительность.
Может быть быстрее (?), Потому что не нужно добавлять базовый адрес
массив (?). Но это, вероятно, незначительно по отношению к памяти
задержка (?)
Возможно незначительный. Вероятно, зависит от конкретного оборудования и | или компилятора.
Еще одно недостающее преимущество индекса: проще управлять при перераспределении.
Рассмотрим структуру, которая может расти, например:
struct VertexList
{
std::vector<Vertex> vertices;
Vertex *start; // you can still access using vector if you prefer; start = &vertices[0];
}
Если вы ссылаетесь на данную вершину, используя указатели, и происходит перераспределение, вы получите неверный указатель.
Другие решения
Для производительности важна скорость, с которой вы можете прочитать «следующий» элемент в любом порядке обхода, который обычно выполняется в горячем пути.
Например, если у вас есть ряд ребер, которые представляют некоторый путь, вы бы хотели, чтобы они сохранялись непрерывно в памяти (не используя new для каждого), в том порядке, в котором они связаны.
Для этого случая (ребра, образующие путь), ясно, что вам не нужны указатели, а также вам не нужны индексы. Соединения подразумеваются местами хранения, поэтому вам просто нужен указатель на первый и, возможно, последний ребра (то есть вы можете сохранить весь путь в std::vector<Edge>).
Второй пример, иллюстрирующий знание предметной области, которое мы можем использовать: представьте, что у нас есть игра, поддерживающая до 8 игроков, и мы хотим сохранить «кто посетил каждый край пути». Опять же, нам не нужны указатели или индексы для обозначения 8 игроков. Вместо этого мы можем просто хранить uint8_t внутри каждого Edge и использовать биты в качестве флагов для каждого игрока. Да, это низкоуровневое разбиение битов, но оно дает нам компактное хранилище и эффективный поиск, как только мы получим Edge*, Но если нам нужно сделать поиск в другом направлении, от игроков к Edges, наиболее эффективным будет хранить, например, вектор uint32_t внутри каждого игрока и сделать индексацию в Edge массив.
Но что, если края могут быть добавлены и удалены в середине пути? Ну, тогда мы могли бы хотеть связанный список. В этом случае мы должны использовать назойливый связанный список, и выделить Edgeс в бассейне. Сделав это, мы можем хранить указатели на Edges в каждом объекте игрока, и они никогда не изменятся или не нуждаются в обновлении. Мы используем навязчивый связанный список с пониманием того, что Edge является только частью одного пути, поэтому внешнее хранение указателей связанного списка будет расточительным (std::list необходимо хранить указатели на каждый объект; навязчивого списка нет).
Таким образом, каждый случай должен рассматриваться индивидуально, так как мы знаем как можно больше об этой области заранее. Ни указатели, ни индексация не должны быть первым подходом.