矢量push_back非常慢

Question

因此,出于性能原因,我正在将我编写的Java代码转换为C++代码,以及使用CUDA并行化一些东西的意图.但是,我想要做的第一件事就是直接转换,只需在C++中运行,其代码与java中相同.

我遇到的问题是,下面的循环实际上需要几分钟才能完成C++,而在Java中几乎没有任何时间.唯一的区别是我在C++和ArrayListJava中使用向量.

当我最初创建单元格向量时,我还为邻居向量保留了适当的大小.此代码的目的是在3d立方体中创建统一的单元格网格,并在以后方便地将每个单元格的邻居存储在单元格内部.

我正在使用Visual Studio 2013,以防万一(对于C++)和Eclipse对于java.

我觉得我肯定错过了一些简单的东西,因为这样的减速似乎很疯狂,但是当我注释掉时push_back,代码基本上立即执行.

w,h和d都是20.cells是Cell结构的矢量(见下文).

for (int i = 0; i < w; i++) {
    for (int j = 0; j < h; j++) {
        for (int k = 0; k < d; k++) {
            for (int x = -1; x < 2; x++) {
                for (int y = -1; y < 2; y++) {
                    for (int z = -1; z < 2; z++) {
                        if (i + x >= 0 && i + x < w && j + y >= 0 && j + y < h && k + z >= 0 && k + z < d) {
                            cells[i][j][k].addNeighbor(cells[i + x][j + y][k + z]);
                        }
                    }
                }
            }
        }
    }
}

定义在不同的文件中:

struct Cell {
    std::vector<Particle> particles;
    std::vector<Cell> neighbors;
    int b = 0;

    void addParticle(Particle &p) {
        particles.push_back(p);
    }

    void addNeighbor(Cell &c) {
        neighbors.push_back(c);
    }
};

Answer 1

在C++中,标准容器例如vector按值存储元素,而不是通过引用(如Java中那样).这意味着您的循环正在创建不仅引用其他单元格而是包含它们的单元格.你最终会创建一个包含矢量的矢量嵌套的巨大森林,它们本身也包含矢量,等等(深度最多约20个级别!).

您可能想要做的是存储指向相邻单元格的指针:

struct Cell {
    ...

    std::vector<Cell*> neighbors;

    ...

    void addNeighbor(Cell &c) {
        neighbors.push_back(&c);
    }
};

这允许单元格彼此存储弱引用.

请记住,C++没有垃圾收集器,也没有进行太多的安全检查,所以完全有责任确保在不再需要单元格时释放单元格,并且当单元格是指针时,指针不会被解除引用不见了.