Are Multidimensional Arrays Faster Than Multidimensional Vectors?

[2NywAqkS]

I have often read that vectors should be used instead of arrays but when I changed one of my particle simulators data storing arrays to a vector there was a noticeable drop in performance. Are their some situations when it is better to use raw arrays?

I initialised the multidimensional vector like this:

vector< vector<double> > Particle_Index(PARTICLES, vector<double>(5));

Any help is much appreciated.
Rowan

[mik2718]

A possible reason could be loss of cache coherence.

A vector allocates extra (unused) space at the end so that push_back operations only occasionally cause a reallocation.

So the vector<double>(5) entities may be taking up more space than just 5 doubles.

Run speed is strongly influenced by how much of the program and data can fit into the CPU cache. The extra space could be affecting this.

In C++11 the array container has been introduced for fixed size arrays. This should give identical performance to a C style array.

[Peter87]

Yes that is probably slower. Using a single dimensional vector will probably be equally fast as the 2D array.

Multidimensional vector:

vector< vector<double> > Particle_Index(PARTICLES, vector<double>(5));
for (int i = 0; i < PARTICLES; i++)
{
    for (int j = 0; j < 5; j++)
    {
        Particle_Index[i][j] = 1.0;
    }
}

Equivalent code with single dimensional vector:

vector<double> Particle_Index(PARTICLES * 5);
for (int i = 0; i < PARTICLES; i++)
{
    for (int j = 0; j < 5; j++)
    {
        Particle_Index[i * 5 + j] = 1.0;
    }
}

You might want to wrap the matrix in a simple class to avoid mistakes.

[hamsterman]

I don't think there should not be too much difference. Maybe you didn't have your optimizations on?

A vector of vectors should work like

int** arr = new int*[width];
for(...) arr[i] = new int[height];

cout << arr[i][j];

The slow because both [] cause reading from memory.

A 2d array works like

int arr[width*height];
cout << arr[i+j*width];

This is (less) slow due to a multiplication.