1. ## Vector vs. array.

The discussion a couple of days ago relating to vectors and arrays got me thinking: If we have a 2D array, how does that compare to a vector of vectors when it comes to performance.

The answer is that in non-optimized debug it's horrible - vector of vector is many times slower than a 2D array. Fortunately, the compiler magic in optimized mode makes the difference much smaller.

My test-code is this:
Code:
```#include <iostream>
#include <iomanip>
#include <vector>
#include <ctime>

const int size = 100;

class B
{
public:
virtual int sum() = 0;
};

class V : public B
{
private:
std::vector < std::vector <int> > vec;
public:
V()
{
for(int i = 0; i < size; i++)
{
vec.push_back(std::vector<int>(0));
for(int j = 0; j < size; j++)
{
vec[i].push_back(i * j);
}
}
}
virtual int sum() {
int s = 0;
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
s += vec[i][j];
return s;
}
};

class A : public B
{
private:
int arr[size][size];

public:
A()
{
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
arr[i][j] = i * j;
}
}
}
int sum() {
int s = 0;
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
s += arr[i][j];
return s;
}
};

int func(B *b)
{
return b->sum();
}

void timeIt(char *name, int (*f)(B *b), B * b)
{
int x = 0;
clock_t t = clock();
for(int i = 0; i < 1000000; i++)
{
x += f(b);
}
t = clock() - t;
std::cout << "x = " << x << std::endl;
std::cout << name << ": " << std::setprecision(6) << static_cast<double>(t) / CLOCKS_PER_SEC << std::endl;
}

#define TIME_IT(f, b) do { timeIt(#b, f, &b); } while(0)

int main()
{
A a;
V v;
TIME_IT(func, a);
TIME_IT(func, v);
}```
And the result is about 4.3s (4.265-4.281) and 5.9s (5.906-5.931) over 6 runs-take away the extremes. That makes 5.9/4.3 -> 1.37 -> about 37% performance loss.

Of course, this is simply testing the performance of accessing an array/vector rather intensely. A lot of the time, we do other things as well, and there are certainly benefits to using vectors if we need to grow the array dynamically - if nothing else because it's easier to write the code.

--
Mats 2. Seems logical. 3. Strangely, the output that I got with MingW was:
x = -288423680
a: 19.703
x = -288423680
v: 16.157
Which means that the vector version was faster?! (Does the compiler do that bad with plain arrays or is it beneficial to store the subvectors in separate chunks of memory, seeing that it doesn't perform "real" random access.

But with VC++ 2005:
x = -288423680
a: 7.812
x = -288423680
v: 73.453 4. Originally Posted by anon But with VC++ 2005:
Code:
```x = -288423680
a: 7.812
x = -288423680
v: 73.453```
Holy crap! Did you enable full optimization, or was that in Debug mode or something? 5. Release, with Code::Blocks selected best optimization (no other needed). #define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0
too.
To remove range checking and other stuff. This will make it more comparable to other compilers.
Also, mats, your example wouldn't work correctly for me and frankly, I don't see why you're making it so complex. I tested with:

Code:
```const int iterations = 1000000; // 1 million
const int arraysize = iterations / 1000;
int array[arraysize][arraysize];
std::vector< std::vector<int> > varray;

int main()
{
int sum = 0;

DWORD dwTick = timeGetTime();
for (int i = 0; i < arraysize; i++)
for (int j = 0; j < arraysize; j++)
array[i][j] = i * j + j;
for (int i = 0; i < arraysize; i++)
for (int j = 0; j < arraysize; j++)
sum += array[i][j];
cout << "Took " << timeGetTime() - dwTick << " ms.\n";

dwTick = timeGetTime();
for (int i = 0; i < arraysize; i++)
{
varray.push_back( std::vector<int>() );
for (int j = 0; j < arraysize; j++)
varray[i].push_back(i * j + j);
}
for (int i = 0; i < arraysize; i++)
for (int j = 0; j < arraysize; j++)
sum += varray[i][j];
cout << "Took " << timeGetTime() - dwTick << " ms.\n";
}```
Results are (in release) - 4-5 ms for native and 17-21 ms for vector of vector.
In debug, it's 15 ms / 938 ms. 7. Originally Posted by anon Which means that the vector version was faster?!
That doesn't surprise me, because I've heard vectors are pretty fast. Although you'd have thought the plain array would have a slight advantage. I wonder if it's because the array is on the stack. 8. Code:
```x = -288423680
a: 6.75
x = -288423680
v: 5.36```
64-bit Linux. gcc 4.2.3. Core 2 Duo @ 3.2ghz. Compiled with just a simple "-O3".

EDIT
Interestingly, it's faster (5.23s, 4.78s) if I compile it to a 32-bit binary (-m32). 9. That doesn't surprise me, because I've heard vectors are pretty fast. Although you'd have thought the plain array would have a slight advantage. I wonder if it's because the array is on the stack.
I doubt so. The only difference would be in time taken to allocate the memory, which is not included in the timing (in the constructor). 10. I can't run Elysia's version, since apparently DWORD and timeGetTime are Windows-only.

After doing some hacking, including defining timeGetTime using the standard gettimeofday -
Code:
```#include <vector>
#include <iostream>
#include <sys/time.h>

typedef int DWORD;

const int iterations = 1000000; // 1 million
const int arraysize = iterations / 1000;
int array[arraysize][arraysize];
std::vector< std::vector<int> > varray(arraysize, std::vector<int>(arraysize));

DWORD timeGetTime() {
timeval tv;
gettimeofday(&tv, 0);
DWORD rtn = tv.tv_usec/1000;
rtn += tv.tv_sec*1000;
return rtn;
}

int main()
{
int sum = 0;

DWORD dwTick = timeGetTime();
for (int i = 0; i < arraysize; i++)
for (int j = 0; j < arraysize; j++)
array[i][j] = i * j + j;
for (int i = 0; i < arraysize; i++)
for (int j = 0; j < arraysize; j++)
sum += array[i][j];
std::cout << "Took " << timeGetTime() - dwTick << " ms.\n";

dwTick = timeGetTime();
for (int i = 0; i < arraysize; i++)
{
for (int j = 0; j < arraysize; j++)
varray[i][i] = i * j + j;
}
for (int i = 0; i < arraysize; i++)
for (int j = 0; j < arraysize; j++)
sum += varray[i][j];
std::cout << "Took " << timeGetTime() - dwTick << " ms.\n";

std::cout << sum << std::endl;
}```
The results -
Code:
```Took 2 ms.
Took 10 ms.```
On a second thought, you are including the memory allocation/moving time in the vector version (in push_back). This is not fair comparison.

*edit*
I editted the code to fix that. The cout statement at the end is so the compiler won't optimize everything out. That, I think is why matsp has it in his version, too.

the results -
Code:
```Took 3 ms.
Took 1 ms.
1391646332```
The number of significant figures also seem a bit too few... blah too lazy to fix that . #define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0
Ok, that brought vector's time down to 8 seconds.

I wouldn't have thought that they'd kill STL performace completely with default settings. 12. MinGW on a 32-bit XP machine...

x = -288423680
a: 38.515
x = -288423680
v: 477.266
-O3

x = -288423680
a: 10.266
x = -288423680
v: 7.719
Might I suggest this machine could be a little faster in general? 13. After doing some hacking, including defining timeGetTime using the standard gettimeofday -
gettimeofday() isn't ANSI standard, of course, but it's BSD and POSIX according to my man page, which I guess is what you were referring to . . . .

 matsp's original program on an AMD64 processor under 64-bit Debian GNU/Linux Lenny:
Code:
```x = -288423680
a: 68.82
x = -288423680
v: 145.68```
That was compiled with
Code:
`g++ vecarray.cpp -o vecarray`
I was too lazy to test with -O2 or -g. [/edit] 14. gettimeofday() isn't ANSI standard, of course, but it's BSD and POSIX according to my man page, which I guess is what you were referring to . . . .
Ah, thanks for the info. Stand corrected. I always thought it's standard. 15. As to the original question, there are a few factors.

One attribute of 2D arrays is that all memory is contiguous (rows are laid end to end in memory), which is not true of vector<vector>'s -- each element of a vector is guaranteed to be contiguous, but that does not make the whole 2D arrangement of elements contiguous because each vector in the vector<vector> allocates it own 1D vector separately.

The other factor that affects relative performance of a 2D array versus a vector<vector> is how memory is managed (by the compiler, by the runtime library, by the operating system, by the hardware). Any of these factors can affect the performance associated with a 2D array or with a vector<vector>. For this reason, the best choice between a 2D array and a vector<vector> will vary .... sometimes one will be better, sometimes the other. Hence people will get different results depending on compiler, compiler settings, library, operating system, available memory, ..... Popular pages Recent additions 