CODEWITHSUNDEEP
c++performancevector
Kinru
Kinru

Reputation: 399

Vector push_back incredibly slow

So I'm in the process of converting Java code that I wrote into C++ code for performance reasons as well as the intention of using CUDA to parallelize some of the stuff down the road. However, the first thing I wanted to do was a straight conversion and just have it running in C++ with the same code as was in java.

The issue I'm running into is that the loop down below is literally taking minutes to finish in C++ while it took barely any time at all in Java. The only difference being that I am using a vector in C++ and an ArrayList in Java.

I am also reserving the proper size for the neighbors vector when I initially create the cells vector. The purpose of this code is to create a uniform grid of cells in a 3d cube and to store the neighbors of each cell inside of the cell itself for convenience later.

I am using Visual Studio 2013 in case that matters (for C++) and Eclipse for java.

I feel like I am definitely missing something simple here as such a slowdown seems crazy, but when I comment out the push_back, the code executes basically instantly.

w, h, and d are all 20. cells is a vector of Cell structs (seen below).

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]);
                        }
                    }
                }
            }
        }
    }
}

Defined in a different file:

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);
    }
};

Upvotes: 2

Views: 2243

Answers (2)

bsr
bsr

Reputation: 61

For Cells, the above answer would suffice. But for particle, would propose the following model:

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

The above code creates lot of Particle objects in the memory and does lot data copying. The following model would save memory allocations and copying:

struct Cell {
    std::vector<Particle> particles;
    Particle& getNextParticleRefForUpdate()
    {
        particles.push_back(Particle());
        return particles.at(particles.size() - 1);
    }
    ...
 };

The particle class would expose set function:

struct Particle
{
    int a;
    int b;

    void set(int& aval, int& bval)
    {
        a = aval;
        b = bval;
    }
    ...
};

While setting particle objects of a Cell object, the function would do the following:

Cell cell_val;
int aval = 5
int bval = 10;
Particle& par_val = cell_val.getNextParticleRefForUpdate();
par_val.set(aval, bval);

Upvotes: 0

Rufflewind
Rufflewind

Reputation: 8956

In C++, standard containers such as vector store their elements by value, not by reference (as would be in Java). This means your loops are creating cells that don't just refer to other cells, but contain them. You end up creating a huge forest of nested of vectors that contain vectors, that themselves also contain vectors, and so on (up to about 20 levels in depth!).

What you probably want to do is to store a pointer to the adjacent cells instead:

struct Cell {
    ...

    std::vector<Cell*> neighbors;

    ...

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

This allows the cells to store weak references to each other.

Keep in mind that C++ doesn't have a garbage collector, nor does it do much safety checking, so it's entirely your responsibility to make sure that the cells are deallocated when they are no longer needed and that pointers are not dereferenced when the cells are gone.

Upvotes: 8

Related Questions