std :: vector vs normal array

Question

Я создаю программу, которая должна быть очень быстрой. Он запускает некоторые вещи на графическом процессоре, используя CUDA, а затем выполняет некоторые вычисления на процессоре. Для этого мне нужно преобразовать высоко оптимизированную графическую структуру данных в нечто, что я могу легко использовать на процессоре. Мои данные в основном представляют собой график, выложенный в сетке. В настоящее время я использую std :: vector для части процессора. Потому что я знаю, что есть довольно накладные расходы, если я много push_back() с и я по крайней мере знаю, потому что я знаю, сколько вершин у меня есть в моем графике, теперь я использую следующий код для этого:

new_graph.resize(blockSize * blockSize); 
for (unsigned long long y = 0; y < blockSize; y++) { 
    for (unsigned long long x = 0; x < blockSize; x++) { 
     int idx = y * blockSize + x; 
     new_graph[idx] = Vertex(x, y); 
    } 
} 

После Я добавляю края. К сожалению, я не знаю, сколько ребер на вершине у меня есть, но я знаю, что он никогда не будет больше 8. Поэтому I reserve() 8 в каждом std :: vector, который я использую для ребер.

Однако, оба эти устройства выглядят чрезвычайно медленно. Если я использую обычный массив для самого графика (так, в основном, заменяя внешний std :: vector), улучшение скорости в этой части огромно (например, 10x или около того).

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

В настоящее время преобразование данных в std :: vector является чем-то вроде 10 раз медленнее, чем запуск моего алгоритма на графическом процессоре (который является интеллектуальным алгоритмом MST). Это не совсем то, что я хочу, потому что теперь накладные расходы слишком велики.

Кто-нибудь знает, что происходит или как я могу это исправить?

p.s. Я компилирую с -O2, потому что я уже выяснил, что это может иметь большое значение. Также пробовал с -O3, никакой реальной разницы.

Vertex определяется следующим образом:

struct Pos { 
    int x, y; 
    Pos() { 
     x = 0; 
     y = 0; 
    } 

    Pos(int x, int y) { 
     this->x = x; 
     this->y = y; 
    } 
}; 

struct Vertex { 
    Pos pos; 
    bool hidden; 
    unsigned long long newIdx; 
    Vertex() { 
     this->pos = Pos(); 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 

    Vertex(Pos &pos) { 
     this->pos = pos; 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 

    Vertex(int x, int y) { 
     this->pos = Pos(x, y); 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 
    int numEdges; 
    int numRemovedEdges; 
    std::vector<Edge> edges; 
    std::vector<bool> removed; 
    std::vector<bool> doNotWrite; 
}; 

Answer 1

Возможно, вы платите за динамическое выделение памяти, которое vector делает, чтобы зарезервировать пространство для своих элементов?

Даже если вы reserve оптимально, вы будете иметь, по крайней мере 3 распределения памяти для каждого Vertex (один для edges, один для removed и один для doNotWrite). Динамическое распределение памяти потенциально дорого по сравнению с высокопроизводительным материалом, который вы пытаетесь сделать здесь.

Либо используйте простые старые массивы, которые гарантированно будут достаточно большими (потенциально теряющими пространство) или специализированным распределителем памяти вместе с vector, с учетом ваших конкретных потребностей.

---

Также вы получаете доступ к элементам в памяти? Ваш пример, кажется, предлагает так, но вы делаете это во всех случаях?

---

Кроме того, вам даже нужны Vertex.pos? Не может быть : от позиции Vertex в сетке?

Answer 2

Не может создать один объект Vertex, тетср х и у значения в нем (так что вы не должны вызвать конструктор для каждого цикла) , затем memcpy весь Vertex в ваш std :: vector? Память вектора гарантированно выкладывается как обычный массив, поэтому вы можете обойти всю абстракцию и напрямую манипулировать памятью. Нет необходимости в сложных вещах. Кроме того, возможно, вы можете компоновать данные, которые вы возвращаете с GPU, таким образом, чтобы вы могли мгновенно копировать целые блоки, экономя вас еще больше.

Answer 3

Существует другое решение, которое я использовал недавно в аналогичной ситуации. В пакете llvm есть класс SmallVector. Он предоставляет интерфейс, который очень похож на std :: vector, но позволяет сохранить некоторое фиксированное количество элементов в строке (поэтому, если вектор не превышает этот начальный предел, дополнительных дополнительных распределений памяти не происходит). Если SmallVector пытается расти выше этого начального размера, тогда выделяется блок памяти, и все элементы перемещаются туда - все на одном прозрачном шаге.

несколько вещей, которые я должен был исправить в этом SmallVector:

1. Наименьшее количество элементов, которые можно было бы поставить в месте есть 2, поэтому, когда один элемент используется в, например, 99.99% случаев существует довольно накладные
2. Обычная использование свопа(), чтобы освободить память (SmallVector(). Своп (VEC)) не свободной памяти, так что я должен был осуществить это сам

Просто посмотрите для последней версии llvm для исходного кода класса SmallVector

Answer 4

Структура данных ЦП крайне неэффективна из-за количества распределений динамической памяти, ненужных операций присваивания и общего размера каждой вершины. Прежде чем рассматривать оптимизацию этой структуры, было бы хорошо понять поток данных между структурами данных ЦП и структурами данных графического процессора, поскольку преобразование между этими двумя форматами может занять много времени. Это вызывает вопрос, почему структура GPU не используется на стороне процессора?

Если вы рассматривали это только со стороны процессора и хотите сохранить структуру данных AoS, то 1. Упростите структуру данных вершин. 2. Удалите все динамические распределения памяти. Каждый std :: vector будет делать dynb 3. Замените удаленный и doNotWrite на std :: bitset < 8>. 4. Удалите numRemoveEdges. Это remove.count(). 5. Если Edge маленький, вы можете быстрее найти его края [8]. 6. Если вы решите остаться с вектором, попробуйте использовать распределитель пула. 7. Измените порядок элементов данных в вершине по размеру, чтобы уменьшить размер вершины.

Все эти рекомендации, скорее всего, не лучшее решение для совместного использования данных с помощью графического процессора. Если вы используете распределитель пула и используете UVA (CUDA Linux), вы можете просто скопировать данные на GPU с помощью одной копии памяти.