Speed Test: std::Vector vs Array
Mar/100
Most recently I have been working on a multithreaded ray tracer in order to port it to CUDA so I am not using any recursion. The first step is implementing the ray tracer without using any acceleration structure. So I simply test a ray with all the objects in a scene thus I needed to decide using whether an array or a vector.
As the current code strongly relies on the data structure I am using, I wanted to test the iteration speed of std::vector versus array.
Here is the code I used for testing.
-
-
#include <iostream>
-
#include <map>
-
#include <vector>
-
#include <array>
-
#include <stack>
-
#include <windows.h>
-
#include <math.h>
-
typedef DWORD TIME_TYPE;
-
-
-
#define BEGIN_TIMING(repeat) TIME_TYPE dwStartTime = timeGetTime(); for(int __i = 0; __i < repeat; __i++){
-
#define END_TIMING }; TIME_TYPE __ret = (timeGetTime() – dwStartTime); cout<< __FUNCTION__ << "\t\t: elapsed time =\t"<<__ret<<endl; return __ret;;
-
-
-
const unsigned int g_uiStartTestSize = 1000000;
-
const unsigned int g_uiStartRepeatCount = 1;
-
-
unsigned int g_uiTestSize = 0;
-
unsigned int g_uiRepeatCount = 0;
-
unsigned int g_uiNumOfTestSteps = 10;
-
using namespace std;
-
using std::map;
-
using std::vector;
-
-
class ClassA
-
{
-
public:
-
ClassA(){a=b=c=d=0;};
-
~ClassA(){};
-
double a;
-
double b;
-
double c;
-
double d;
-
};
-
-
-
-
vector<ClassA*>* classAVector;
-
ClassA** classAArray;
-
-
TIME_TYPE testFillInArray()
-
{
-
BEGIN_TIMING(1)
-
classAArray = new ClassA*[g_uiTestSize];
-
for(int i =0; i < g_uiTestSize; i++)
-
{
-
classAArray[i] = new ClassA();
-
}
-
END_TIMING
-
}
-
-
TIME_TYPE testFillInVector()
-
{
-
BEGIN_TIMING(1)
-
classAVector = new vector<ClassA*>();
-
for(int i =0; i < g_uiTestSize; i++)
-
{
-
classAVector->push_back(new ClassA());
-
}
-
END_TIMING
-
}
-
-
TIME_TYPE testDestroyArray()
-
{
-
BEGIN_TIMING(1)
-
for (int i = 0; i < g_uiTestSize; i++)
-
{
-
delete classAArray[i];
-
}
-
delete [] classAArray;
-
END_TIMING
-
}
-
-
TIME_TYPE testDestroyVector()
-
{
-
BEGIN_TIMING(1)
-
for (int i = 0; i < g_uiTestSize; i++)
-
{
-
delete (*classAVector)[i];
-
}
-
delete classAVector;
-
-
END_TIMING
-
}
-
-
TIME_TYPE testIterateVector(void)
-
{
-
BEGIN_TIMING(g_uiRepeatCount)
-
ClassA *pClassA;
-
-
/*
-
const int sz = classAVector->size();
-
for (int i = 0; i < sz; i++)
-
{
-
pClassA = (*classAVector)[i];
-
pClassA->a++;
-
pClassA->b++;
-
pClassA->c++;
-
pClassA->d++;
-
}*/
-
-
-
-
vector<ClassA*>::iterator it = classAVector->begin();
-
const vector<ClassA*>::iterator endIt = classAVector->end();
-
while(it != endIt)
-
{
-
pClassA = (*it);
-
pClassA->a++;
-
pClassA->b++;
-
pClassA->c++;
-
pClassA->d++;
-
it++;
-
}
-
-
END_TIMING
-
}
-
-
TIME_TYPE testIterateArray(void)
-
{
-
BEGIN_TIMING(g_uiRepeatCount)
-
ClassA *pClassA;
-
for (int i =0; i < g_uiTestSize; i++)
-
{
-
pClassA = classAArray[i];
-
pClassA->a++;
-
pClassA->b++;
-
pClassA->c++;
-
pClassA->d++;
-
-
}
-
END_TIMING
-
}
-
-
void verify()
-
{
-
cout<<"verifying"<<endl;
-
for (int i=0; i < g_uiTestSize; i++)
-
{
-
if( (*classAArray[i]).a != classAVector->at(i)->a )
-
{
-
cout << "error!:" << i <<endl;
-
}
-
}
-
}
-
-
TIME_TYPE testAll()
-
{
-
BEGIN_TIMING(1)
-
g_uiTestSize = g_uiStartTestSize;
-
for (int i =1; i <= g_uiNumOfTestSteps; i++)
-
{
-
g_uiRepeatCount = g_uiStartRepeatCount * i;
-
cout<< "repeat count =\t\t"<<g_uiRepeatCount<<endl;
-
cout<< "test size =\t\t"<<g_uiTestSize<<endl;
-
testFillInArray();
-
testFillInVector();
-
testIterateArray();
-
testIterateVector();
-
testDestroyArray();
-
testDestroyVector();
-
cout<<"———————————————"<<endl;
-
}
-
g_uiRepeatCount = g_uiStartRepeatCount;
-
for (int i =1; i <= g_uiNumOfTestSteps; i++)
-
{
-
g_uiTestSize = g_uiStartTestSize * i;
-
cout<< "repeat count =\t"<<g_uiRepeatCount<<endl;
-
cout<< "test size =\t"<<g_uiTestSize<<endl;
-
testFillInArray();
-
testFillInVector();
-
testIterateArray();
-
testIterateVector();
-
testDestroyArray();
-
testDestroyVector();
-
cout<<"———————————————"<<endl;
-
}
-
-
END_TIMING
-
-
}
-
-
-
-
-
int main(void)
-
{
-
testAll();
-
return 0;
-
}
-
-
Results
Results are striking indeed. If you compiling the code in Release mode without any run-time error checking and disabled exection support iterating a Vector by using std::vector<>::iterator is almost as fast as using array.
However testing them on debug mode shows the difference, iteration time is terribly slow on std::vector ; about 60 times slower.
Conclusion
std::vector is almost as fast as using a static array on release mode (using Visual Studio 2008) but terribly slow on debug mode. So if your code is running slow on the debug mode, don’t give up std::vector and give a go on the release mode.