c++ - std::vector 与普通数组

Question

我正在创建一个需要超快的程序。它使用 CUDA 在 GPU 上运行一些东西，然后在 CPU 上进行一些计算。为此，我需要将高度优化的 GPU 数据结构转换为可以在 CPU 上轻松使用的数据结构。我的数据基本上是一个布置在网格中的图表。目前我在 CPU 部分使用 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。因此，我在用于边缘。

但是，这两者似乎都非常慢。如果我为图形本身使用普通数组(因此基本上替换了外部 std::vector)，那部分的速度改进是巨大的(大约 10 倍左右)。

对于图表来说这是可行的，但对于边缘来说并非如此，因为我在这些边缘上做了一些后处​​理，为此我真的需要像 std::vector 这样有点动态的东西(我添加了一些边缘)。

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

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

附注我使用 -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，每个Vertex 至少有3 个内存分配(一个用于边缘，一个用于removed，一个用于doNotWrite)。相对于您在此处尝试执行的高性能操作，动态内存分配的成本可能很高。

要么使用保证足够大(可能会浪费空间)的普通旧数组，要么使用专门的内存分配器和 vector，根据您的特定需求量身定制。

---

此外，您是否按内存顺序访问元素？您的示例似乎表明是这样，但您是否在所有情况下都这样做？

---

此外，您甚至需要 Vertex.pos 吗？不能从 Vertex 在网格中的位置推断吗？