Thread: 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

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

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.

Release, with Code::Blocks selected best optimization (no other needed).

Try adding
#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.

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).

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 .

Try adding
#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.

Originally Posted by cyberfish

On a second thought, you are including the memory allocation/moving time in the vector version (in push_back). This is not fair comparison.

It may not be, but I pushed for a more general scenario. We're more likely to just let the vector manage the memory instead of pre-allocating, so I used push_back instead of resize.

Originally Posted by anon

I wouldn't have thought that they'd kill STL performace completely with default settings.

They do range checking by default, and I can't really say it's a bad thing, since it's more secure. But it leaves you the option to disable that, which is a very fine thing, indeed.
Actually, in release, if you try to access an out-of-bounds element in the vector, with range checking OFF, the compiler will completely optimize away that line of code.

I tried a test by preallocating vector and the result was that they were pretty equal, or vector was faster!
4-6 ms for vector, and 4-7 ms for native array.

Originally Posted by Elysia

They do range checking by default, and I can't really say it's a bad thing, since it's more secure. But it leaves you the option to disable that, which is a very fine thing, indeed.

It's a horrible thing. I've heard some serious horror stories about the compatibility problems when a binary-only library links against the "secure" STL and the client code wants the unsafe version because secure version is just too damn slow. Well, no can do, sorry. No mixing of the two. You get to beg the library vendor for a version linking against the unsafe version.

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?

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 . . . .

[edit] 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]