std :: vector vs普通数组

Question

我正在创建一个需要超快的程序.它使用CUDA在GPU上运行一些东西,然后在CPU上进行一些计算.为此,我需要将高度优化的GPU数据结构转换为我可以在CPU上轻松使用的内容.我的数据基本上是一个网格中的图形.目前我正在使用std :: vector作为CPU部分.因为我知道如果我做了很多push_back()s并且至少知道因为我知道我的图中有多少个顶点,所以有很多开销,我现在使用以下代码:

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.因此我reserve()在每个std :: vector中使用8个边缘.

然而,这似乎都非常缓慢.如果我为图形本身使用普通数组(所以基本上替换外部的std :: vector),那部分的速度提升是巨大的(比如大约10倍).

对于图形来说,这是可行的,但对于边缘并不是真的,因为我在这些边缘上做了一些后期处理,为此我真的需要像std :: vector这样有点动态(我添加一些边缘).

目前将数据转换为std :: vector的速度比在GPU上运行算法慢10倍(这是一种智能MST算法).这不是我想要的,因为现在开销太大了.

有人知道发生了什么或我如何解决这个问题？

ps我用-O2编译,因为我已经发现这可以产生很大的不同.也试过-O3,没有真正的区别.

顶点定义如下:

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