Vector vs. array V2.

In reference to the thread on
delete[]
and this old thread:
Vector vs. array.

I have updated the code to use dynamic memory allocation for the array model.

Here is the code I used (generally unmodified from previous test, aside from adding extra code to do the dynamic memory allocation):

Code:

#include <iostream>
#include <iomanip>
#include <vector>
#include <ctime>

const int size = 128;

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

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

class D: public B
{
private:
	int **parr;
public:
	D()
	{
		parr = new int*[size];
		for(int i = 0; i < size; i++)
		{
			parr[i] = new int[size];
			for(int j = 0; j < size; j++)
			{
				parr[i][j] = i * j;
			}
		}
	}
	~D()
	{
		for(int i = 0; i < size; i++)
		{
			delete [] parr[i];
		}
		delete [] parr;
	}
	int sum() {
		int s = 0;
		for(int i = 0; i < size; i++) 
			for(int j = 0; j < size; j++)
				s += parr[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;
	D d;
	TIME_IT(func, a);
	TIME_IT(func, v);
	TIME_IT(func, d);
}

Key:
a - fixed size array on the stack.
v - vector of vector.
d - dynamically allocated 2D array.

Result: g++ -O2 -fomit-frame-pointer -funroll-loops

Code:

x = -802947072
a: 12.031
x = -802947072
v: 11.297
x = -802947072
d: 12.907

Result: Visual Studio .Net (VC++ version 7.0, cl version 13.00)

Code:

x = -802947072
a: 6.218
x = -802947072
v: 10.75
x = -802947072
d: 7.891

As you can see (and as I expected), the dynamic variant ends up closer to vector, but still slightly slower than the fixed size array.

--
Mats

Your classes aren't equivalent. At first glance I'd say you need to size the vector in the constructor's initializer list. I don't have time to go into too much detail beyond that though.

Also, do you have VC++ 7.1 or later? 7.1 is generally considered to be the first good implementation of the standard library for VC++.

Could you add a single block of memory with manual address calculation as another test case? And increase size to 2048, to increase the effect that caching problems create?

I'd also increase the number of iterations to get better accuracy, and also check what the difference is if you call vector::reserve() to set it to the size it will end up with before starting the tests.

Your classes aren't equivalent. At first glance I'd say you need to size the vector in the constructor's initializer list.

This test doesn't time the creation and destruction of the objects (should be negligible because it happens once, whereas the objects are used 1000000 times).

And increase size to 2048,

If size was increased, wouldn't it be too much for the stack array?

>> and also check what the difference is if you call vector::reserve() to set it to the size
To be equivalent you would set the size in the constructor.

However, using reserve and push_back could theoretically be an optimization (although I doubt it would matter for POD types) because it avoids a default construction of all the objects. The equivalent for that with new[] involves placement new, but I don't think it's necessary to go that far with the timing.


>> This test doesn't time the creation and destruction of the objects
Oops, I made the same mistake last time. I think that information would be pertinent, though.

>> If size was increase, wouldn't it be too much for the stack array?
We're really trying to compare vector versus dynamic array, though (at least that was the context of the other thread from R.Stiltskin).

The STL implementation may be a point, but the construction phase is not what I'm measuring. It only measures the time it takes to sum all the numbers in the array/vector.

--
Mats

i tried running the same program on VS2005, release mode, and something really bazaar happens. the vector fails completely. i had to reduce the loop to 100000. here are the results:

Code:

x = 778698752
a: 0.578
x = 778698752
v: 4.812
x = 778698752
d: 0.578

VC++ 2005 and later have iterator checks turned on for operator[] even in Release mode. You need to turn that off (I don't know the flag off the top of my head).

Originally Posted by Daved

VC++ 2005 and later have iterator checks turned on for operator[] even in Release mode. You need to turn that off (I don't know the flag off the top of my head).

weird, i put

Code:

#define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0

at the top of my program and it didn't make a difference.

I extended the size to 2048 x 2048 array/vector size. As the vector is guaranteed to be a contiguos block, I don't expect any difference between reserve/resize.

Visual studio results:

Code:

x = 2097152000
v: 13.859
x = 2097152000
d: 13.766

I omitted the static array variant, as it does indeed use more stack space than an application is allowed to use...

This is fewer iterations and bigger blocks of memory, so I guess the overhead of memory reads reduce the efficiency of the processor -> less difference between the two implementations. (Becuase in both cases, the cache-hit rate is lower, and the processor spends more time waiting for the memory to be read). From that perspective, a smaller size is "better", because the processor can cache the memory, and we no longer depend on the external bus to bring data in at a rate about 10x slower than the processor itself.

--
Mats

When I compile it with VC++ 2008 express I get 3 warnings about the TIME_IT calls in main():

Code:

warning C4127: conditional expression is constant

Originally Posted by cpjust

When I compile it with VC++ 2008 express I get 3 warnings about the TIME_IT calls in main():

Code:

warning C4127: conditional expression is constant

Is that the "do ... while(0)" that is complains about? Try removing that - it's the only "condition" in the entire line, so I can't think of what else it may be.

I just have this habit of using "do while" around macros, really.

--
Mats

Originally Posted by matsp

I just have this habit of using "do while" around macros, really.

that caught my eye when i first read the source...what's the reasoning behind this? thanks.

Originally Posted by bling

that caught my eye when i first read the source...what's the reasoning behind this?

A trick so that you can do things like use an if statement with no else block in a macro without potentially breaking the code that uses the macro.