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