Re: std::vector slow?
David Klein wrote:
I wrote a simple template class Vec and when I compile with
optimization under Visual Studio 2005, std::vector takes 56% more
time. I would have thought that std::vector is much more optimized
than anything I could roll myself. Am I mis-using std::vector somehow?
Or is it really that inefficient?
VS2005 includes a standardlibrary that has several extra checks for
conditions that are called 'undefined behaviour' by the standard, i.e. an
implementation neither has to generate any particular behaviour nor
generate an error. Those checks cost time but they can be disabled. It is
not enough to make a release build though!
What I did is basically 2^10 loops of allocating a vector<int> of size
2^16, filling it, and finding the largest element.
[...]
const static int n = 2<<16;
const static int times = 2<<10;
The constants 'n' and 'times' are 2^17 and 2^11! ;)
template <class T> class Vec
{
public:
Vec(void)
{
mPtr = NULL;
mNElem = 0;
}
Vec(int size) : mNElem(0), mPtr(NULL)
{
if (size < 0) throw "Size < 0\n";
if (size > 0)
{
mPtr = new T [size];
if (mPtr == NULL)throw "Vec allocation failed\n";
mNElem = size;
}
}
~Vec(void)
{
if (mPtr) delete [] mPtr;
mPtr = NULL;
mNElem = 0;
}
int size(void) const { return mNElem; }
T &operator[](const int i) const { return mPtr[i];}
private:
T *mPtr;
int mNElem;
};
Remarks:
- 'void' in parameterlists is optional in C++
- prefer initialisation to assignment in the constructor
- copying and assignment are obviously broken, but I guess it's just an
example
- 'new' never returns null but throws bad_alloc instead
- 'delete' can be used on a null pointer, no need to check it before
- 'int' might be too small for the size of a vector, use 'size_t' instead
- the const operator[] is returning non-const references to the contained
elements
None of these cause any significant performance slowdown though, some rather
do the opposite. I just wanted to point those out.
for (int j=0; j<times; j++) {
s = 0;
vector<int> y(n);
for (int i=0; i<n; i++) {
y[i] = i;
}
for (int i=0; i<n; i++) {
if (y[i]>s) s=y[i];
}
}
[ similar code for Vec<int> ]
There are basically two things that are done here:
1. Allocating and releasing memory.
2. Access via operator[].
My guess is that the second one is the one causing the slowdown, because it
includes range checks in the VS2005 standardlibrary. Just step through it
with a debugger and you will see.
Uli
--
Sator Laser GmbH
Gesch??ftsf??hrer: Michael W??hrmann, Amtsgericht Hamburg HR B62 932
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]