Printable View
hi,
I've just tried to measure the performance of the std::vector vs traditional array, and I'm quite surprised to see that initializing a vector is WAY longer than initializing an array:
takes 0.42...sCode:std::vector<int> x(100000000);
takes 0.00...sCode:int* a=new int[100000000];
Why is there such a huge difference? With such a difference, I guess people only use std::vector when they need features such as insert?
Ujl
I guess it has something to do with initilization of integer.
std::vector will initilize it with ZERO but the traditional array will not
>>With such a difference, I guess people only use std::vector when they >>need features such as insert?
your forgetting about the memory management. Vector will take care of all memory allocation & deallocation for you.
Vinod
There is absolutely no need for vector to initialize elements to 0. Now I'm REALLY glad I created and use my own Array class.
You're probably right. Do you know if there is a way to just allocate memory without initializing the vector?
thanks for your help
I don't mind giving the code out:
PHP Code://faster than vector w/o malloc. About 1.5 times faster than vector with malloc!
//use pointers instead of classes when using malloc.
template < typename T >
class aArr
{
protected:
uint capacity;
public:
T* _Items;
bool cppAllocation;
uint Count;
aArr()
{
Reset();
}
aArr(uint initCapacity, bool cppStyleAllocation= 0)
{
Reset();
capacity= initCapacity;
cppAllocation= cppStyleAllocation;
if(cppAllocation)
_Items= new T[capacity];
else
_Items= (T*)malloc(initCapacity*sizeof(T));
}
/*aArr(const T &item) //ambiguous when item is uint
{
Reset();
Add(item);
}*/
~aArr()
{
Del();
}
void Del(uint initCapacity= 0)
{
if(_Items)
{
if(cppAllocation)
delete[]_Items;
else
free(_Items); //free is 2x faster than delete[]
_Items= 0;
}
Count= 0; capacity= 0;
}
void Reset()
{
_Items= 0;
Count= 0;
capacity= 0;
cppAllocation= 0;
}
T& operator[](uint ind)
{
return _Items[ind];
}
T& Ind(uint ind)
{
return _Items[ind];
}
void Add(const T& d)
{
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
if(cppAllocation)
_Items[Count]= d;
else
memcpy(&_Items[Count], &d, sizeof(T));
++Count;
}
void Ins(uint where, aArr < T* > &arr)
{
if(!arr.Count) return;
if(!Count || where >= Count)
{
for(uint i= 0; i < arr.Count; ++i)
Add(arr[i]);
return;
}
if(Count+arr.Count >= capacity)
Resize(Count < 10 ? 20+arr.Count : Count*1.5f +arr.Count);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
if(cppAllocation)
{
for(uint i= 0; i < arr.Count; ++i)
_Items[where+i]= *arr[i];
}
else
memcpy(&_Items[where], arr[0], sT*arr.Count);
memcpy(&_Items[where+arr.Count], buf.Ptr(), sTemp);
//free(temp);
Count += arr.Count;
}
void Ins(uint where, const T& d)
{
//aArr<T*> arr; arr.Add(&d);
//Ins(where, arr);
//return;
if(!Count || where >= Count)
{
Add(d);
return;
}
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
if(cppAllocation)
_Items[where]= d;
else
memcpy(&_Items[where], &d, sT);
memcpy(&_Items[where+1], buf.Ptr(), sTemp);
//free(temp);
++Count;
}
void Rem(aArr < uint > & arr)
{
T* temp= _Items;
capacity= Count;
if(cppAllocation)
_Items= new T[capacity];
else
_Items= (T*)malloc(capacity*sizeof(T));
uint count= Count;
Count= 0;
uint removed= -1;
for(uint i= 0; i < count; ++i)
{
for(uint j= 0; j < arr.Count; ++j)
{
if(i == arr[j])
{
removed= i;
break;
}
}
if(removed == -1)
{
Add(temp[i]);
}
else
{
removed= -1;
}
}
if(cppAllocation)
delete[]temp;
else
free(temp);
}
void Rem(uint ind)
{
aArr < uint > arr(1);
arr.Add(ind);
Rem(arr);
}
void RemAll()
{
Del();
}
void Resize(uint newSize)
{
capacity= newSize;
if(cppAllocation)
{
T* temp= _Items;
_Items= new T[capacity]; memcpy(_Items, temp, Count*sizeof(T)); delete[]temp;
}
else _Items= (T*)realloc(_Items, newSize*sizeof(T));
if(capacity < Count)
Count= capacity;
}
private:
static int _ascending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return 1;
if(*((T*)v1) < *((T*)v2)) return -1;
return 0;
}
static int _descending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return -1;
if(*((T*)v1) < *((T*)v2)) return 1;
return 0;
}
public:
void Sort(char A_D= 'A')
{
if(A_D == 'A') qsort(&_Items[0], Count, sizeof(T), &_ascending);
else qsort(&_Items[0], Count, sizeof(T), &_descending);
return;
const int tSize= sizeof(T);
void* hold[tSize];
for(int i= 0; i < Count; ++i)
{
for(int j= 0; j < Count-1; ++j)
{
if((A_D == 'A' && _Items[j] > _Items[j+1]) || (A_D == 'D' && _Items[j] < _Items[j+1]))
{
Swap(&_Items[j], &_Items[j+1], tSize, &hold);
}
}
}
}
aStr ToStr()
{
aStr s;
for(uint i= 0; i < Count; ++i)
{
s= s << _Items[i] << "\n";
}
return s;
}
};
Thanks a lot!
for allocating int's use malloc/calloc and realloc and free(look on msdn)
for objects use this method. its does not use a buffer.
Code:void ReSize(int*& Src, int OldSize, int NewSize)
{
if(OldSize == NewSize)
return;
int* arr = new int[NewSize];
int* iarr = arr;
int* isrc = Src;
for(int* iend = arr + NewSize < OldSize ? NewSize : OldSize; iarr != iend; ++iarr, ++isrc)
*iarr =*isrc;
delete[] Src;
Src = arr;
}
int* a=new int[100 000 000];
ReSize(a, 100 000 000, 50 000 000);
delete[] a;
you have some serious issues here memcpy() cannot be used for copieing ojects. also using bool is not safe and also is slower. free is faster because it does not call object destructors.Quote:
Originally Posted by aewarnick
aewarnick, in your case, there is absolutely no need to use the vector constructor that creates elements and zero initialises them. Dont complain about 'unnecessary' initialisation when you request for it.Quote:
There is absolutely no need for vector to initialize elements to 0. Now I'm REALLY glad I created and use my own Array class.
Ujl, create an empty vector, then reserve the space you want.Quote:
Do you know if there is a way to just allocate memory without initializing the vector?
Of course, x is still empty, so you still have to insert/push_back the elements.Code:std::vector<int> x;
x.reserve(100000000);
aewarnick, you need to go home and rethink your code. Your exposure of private mechanisms as public interface is rather disturbing. Your operator[] lacks a const version, and you use identifiers reserved to the implementation.Quote:
I don't mind giving the code out
There is no point in having uninitialized array. This difference doesn't count.Quote:
Originally Posted by aewarnick
imho thats very untrue. there is no point in initializing it.Quote:
Originally Posted by RoboTact
Code:std::vector<int> x(100000000);
int y = x[5];//you know this is 0. no point in this
Um, how does this even factor into the discussion?Quote:
Originally Posted by Mitsukai
read th thread
Sorry, but I cannot make out what you are trying to say.Quote:
Originally Posted by Mitsukai
Um, you gave a code snippet without explaining how does it support your claim that "thats very untrue. there is no point in initializing it". Now you throw an ad hominem attack against me. I do not see how is it that I have to "take a forum tutorial and how to read a discussion tutorial".Quote:
take a forum tutorial and how to read a discussion tutorial i also suggest you take a tutorial on how to have common sense. good luck googling.
If there is no point in initializing it, what point is there in allocating it?Quote:
Originally Posted by Mitsukai
also take a how to read a C++ comment tutorial
to have an dynamic array ofcourse. initialization shuld be done by the user not by the implention. and can cost serious CPU cycles decreasing a computers life time unnesesary.Quote:
Originally Posted by RoboTact
I have read your source comments, of course, but I find them inadequate in explaining your position.Quote:
also take a how to read a C++ comment tutorial
Does my example not show how one can pretty much delay initialisation?Quote:
to have an dynamic array ofcourse. initialization shuld be done by the user not by the implention. and can cost serious CPU cycles decreasing a computers life time unnesesary.
The thing is, if you store objects in a vector, then the objects should have some value, i.e. they must be initialised. The equivalent of what the original poster was asking for is to reserve the space, and then insert values later.
And in this case allocation without initialization IS implementation detail. And laserlight showed how to advise implementation on that.Quote:
Originally Posted by Mitsukai
If vectors did not initialize all of their elements to zero, you would
run into the same problems you do when you don't initialize an array.
IMO, all arrays and vectors should be initialized, whether by the user
or by it's implementation automatically. If they aren't then you run the
risk of accidentally using some garbage value stored in one of the
uninitialized elements in a calculation.
An example would be this..
In the first example, the sum will be unaffected because all of the arrayCode:#include <vector>
#include <iostream>
using namespace std;
int main(){
int sum = 0;
int intArray1[10];
for ( int i=0; i < 10; i++ )
intArray1[ i ] = 0;
intArray1[0] = 1;
intArray1[1] = 2;
intArray1[2] = 3;
intArray1[3] = 4;
intArray1[4] = 5;
for( int i=0; i < 10; i++ )
sum += intArray1[ i ];
cout << sum << endl;
//*******************************
sum = 0;
int intArray2[10];
intArray2[0] = 1;
intArray2[1] = 2;
intArray2[2] = 3;
intArray2[3] = 4;
intArray2[4] = 5;
for( int i=0; i < 10; i++ )
sum += intArray2[ i ];
cout << sum << endl;
cin.get();
return 0;
}
elements were initialized to zero. In the second example, the sum spits
out an incorrect value because the last five elements were left
uninitialized with some garbage values. If your array was huge, say a
million elements, you could easily cause an integer overflow with this.
I think it is worth the performance sacrifice to initialize an array or vector
in order to avoid a great deal of problems later on down the road.
how has this todo with initialisation, it dont.Code:If your array was huge, say a million elements, you could easily cause an integer overflow with this.
so what if you get garbage values? having a array initialised 0 is basicly the same thing. its garbage. its something you will never really work with. its always initialised to something before used. thus making it a double initialisation. Wasting lots of CPU cyclesQuote:
with some garbage values
new calls constructors. they already have a "value". thus making it a triple initialisation. By new, by vector, by user. again wasting lots lots of cpu cycles.Quote:
then the objects should have some value
see post #20...Quote:
And in this case allocation without initialization IS implementation detail
The question hasn't been asked yet.Quote:
Originally Posted by Ujl
Did you time a release (optimized) build, or a debug build? If you timed a debug build, then this whole discussion is pointless.
Regards,
Paul McKenzie
That is if you do not intend to have a zero initialised vector. For example, one could have an int vector of a million 10s:Quote:
so what if you get garbage values? having a array initialised 0 is basicly the same thing. its garbage. its something you will never really work with.
Basically, if you choose to use the constructor that accepts an integer stating the number of elements the vector should contain, you get a vector with that number of elements, initialised to whatever value you set, or some zero or default value if none is given.Code:std::vector<int> x(1000000, 10);
Constructors perform default initialisation.Quote:
new calls constructors. they already have a "value".
That is correct. However, if you have 0 there's advantage of determinism of incorrect behaviour if you'll stumble upon one. And anyway you shouldn't use either method: values you don't work with shouldn't be accessible at all. vector with reserved part gives both advantages.Quote:
Originally Posted by Mitsukai
You really should cool down.Quote:
Originally Posted by Mitsukai
that is still garbage. you know you initialised it to 10.Quote:
Originally Posted by laserlight
so?Quote:
Originally Posted by laserlight
I'm glad you did -- it shows why usage of standard classes such as vector are important in proper, bug-free developmentQuote:
Originally Posted by aewarnick
Your class lacks a copy constructor, and an assignment operator. It also lacks the proper overload of operator [] (there should be two overloads, not one). The memcpy() does not work if the object is non-POD, i.e.
Even for int, this simple code snippet causes memory corrution when main() terminatesCode:#include <string>
//...
aArr<std::string> s; // error if used for this type
I could go onto other issues with it, but the lack of copy constructor and assignment operator are big problems.Code:int main()
{
aArr<int> a1(10);
aArr<int> a2 = a1; // pointers point to same memory
} // your dead here
Regards,
Paul McKenzie
Do you know how to read? Did you even look at my example? If you did,Quote:
how has this todo with initialisation, it dont.
then you would understand it has everything to do with initialization.
If in my example, the array had a million elements which were
uninitialized and you attempted to sum them you would more
than likely cause an integer overflow because they contain garbage
values whose values are unknown.
If it were initialized to all zeroes, then your calculation wouldn't
be affected at all. Likewise if you wanted to multiple all of the elements
together and you initialized all of the elements to one, your results
wouldn't be affected.
There is a simple reason reason to initialize an array, and that's becauseQuote:
so what if you get garbage values? having a array initialised 0 is basicly the same thing. its garbage. its something you will never really work with. its always initialised to something before used. thus making it a double initialisation. Wasting lots of CPU cycles
if left uninitialized you just don't know what the elements contain. This
opens up the risk to negatively affecting a calculation down the road.
It is not going to waste CPU cycles. The array is allocated in memory
and whatever values those particular places in memory contain at that
moment in time the array will contain. By saying this is a double
initialization, you are implying that simply creating an array takes O(N) time.
No, it doesn't. By initializing the elements to some value which you know
guarantees the "safety" issue of your program in which you assure that
it is not going to, or at least not likely to, make a calculation mistake.
Gah, you always ask the right questions :)Quote:
Did you time a release (optimized) build, or a debug build? If you timed a debug build, then this whole discussion is pointless.
It isnt garbage since in this case the programmer requires a vector of a million 10s.Quote:
that is still garbage. you know you initialised it to 10.
This is very untrue, and your whole post is based around this argument.Quote:
Originally Posted by dcjr84
It shuld be initialised. But not by vector. By user. having an array of 0's is also garbage.
... so you just created million 10's while you only need the number 10, good job.Quote:
Originally Posted by laserlight
If the user writes:Quote:
It shuld be initialised. But not by vector. By user. having an array of 0's is also garbage.
Then the user is creating a vector of a million 0s. It is as simple as that. What the user requests be done surely cannot be garbage.Code:std::vector<int> x(1000000);
If I only need the number 10 stored in a variable, I would write:Quote:
... so you just created million 10's while you only need the number 10, good job.
If I needed an int vector with a capacity of million elements, the first of which I currently know to be 10, I would write:Code:int x = 10;
The above vector only has a size of 1, and rightly so since only 1 int is what I need at the moment.Code:std::vector<int> x;
x.reserve(1000000);
x.push_back(10);
This is, frankly, much ado about nothing.
you know im not going to discuss anymore, if you guys dont even want to try think my position fine, stay one minded. :)
dcjr84
I disagree with your reasoning. Having initialized values is important, but not because it allows sloppy code to work. In your case you better should have array initialized to something like minimum possible value of integer to show error right when it occurs. Having consistent result guarantees repeatability of error behaviour.
Vectors, and especially arrays, should always be
initialized. period. Doesn't matter if its by the user or done
automatically by it's implementation. The performance impact is
negligible.
And even if it did reduce performance; I would rather
have a program that runs at 50% speed but is guaranteed to
an extremely high percentage to never make a mistake
in calculation because it might at some point use an unintialized
garbage value from an array or vector, than have one that runs
at 100% speed but the results might be incorrect at some point
because there is the possibility it might use an uninitialized element
from an array or vector.
yes i very agree. but in my opinion this is a user fault not an array object fault.Quote:
Originally Posted by RoboTact
More generally, nondetermenistic behaviour shouldn't be exposed. If said uninitialized value lurks shot within object and isn't visible outside it, fine, as far as object itself works right.Quote:
Originally Posted by dcjr84
This is an programmers fault in this case. And will not happen in good desgined software. Doesnt mather if it is a vector or not having 0's is still garbage and will get wrong calculations if software is not rightly designed. Besides arrays are almost never used for calculations, but mostly for storing objects for games. POD's for images, files etc.Quote:
Originally Posted by dcjr84
Using vector will only decrease performance, and if this is not visible, the cpu cycles will waiste energy, and decrease computer's life time.
There is no fault in question, is there? ;)Quote:
Originally Posted by Mitsukai
:eek:Quote:
Originally Posted by Mitsukai
You should reconsider level of conviction in such assertions.
I guess i late in game now :)
The sicussion went somewhere else than original post. though first i agree with Paul we need to find out how these timing taken.
>>yes i very agree. but in my opinion this is a user fault not an array object fault.
The evolution of all programming language is based on easy to use & hard to make mistkes by "user". There no need to use C++. We can do all things in C & assembly. Lets imagine handling memory managment in C for all the objects than using C'tor & D'tor. "user" is more likely to make the mistakes in C. In think there is no harm in providing automatic initilation to some value rather than having uninitiliaze. I bet for most of the application the overhead is very very less.
Vinod
But, if you use vector::reserve, then it does create an uninitialised array. It's just that you can't randomly access the values until you put something in it, and then only the values that you've added. This is a good thing. Plus, as has already been pointed out to you, your "vector replacement" is seriously flawed.Quote:
Originally Posted by aewarnick
Again, this is negligible. Hundreds if not thousands of cpu cycles areQuote:
Using vector will only decrease performance, and if this is not visible, the cpu cycles will waiste energy, and decrease computer's life time.
probably wasted every minute of every day by your computer for a
multitude of reasons: bad CPU scheduler decisions, etc, etc. I highly
doubt that using a vector is going to decrease your computers lifetime
by so much that it would even be noticeable.
I did the test on a release build. My main objective is to have an array with a member _size. It is easy to implement but if std::vector is as fast as a simple array class, I'll use it.Quote:
Originally Posted by Paul McKenzie
I've also compared how fast it was to assign values to an array and to copy it to another array:
is still more than 20% faster thanCode:int* a=new int[size];
int* b=new int[size];
for(int i=0; i<size;i++) a[i]=i;
memcpy(b,a,size*sizeof(a));
push_back is quite slow, but I can't do:Code:std::vector<int> x;
std::vector<int> y;
x.reserve(size);
y.reserve(size);
for(int i=0; i<size;i++) x.push_back(i);
y.assign(x.begin(), x.end());
because the iterators returned by x.begin() and x.end() are not incremented, and I can't use assign or copy....Code:for(int i=0; i<size;i++) x.[i]=i;
Do you see any way to make that faster using vector?
Thanks again to everybody for your help
Ujl
this is very very very wrong first of al sizeof(a) must be sizeof(int) second you do not use memcpy with newCode:memcpy(b,a,size*sizeof(a));
Then, you should not program in C++.Quote:
Originally Posted by dcjr84
There are lots of much safer languages (at the cost of a small performance overhead).
Try Ada... Or Common LISP if you need a high level of expressivity.
It is true that having determistic behaviour can be good... But there must be a way to escape that! There should be a way to create an uninitialized vector (if the type in the vector is POD)... Probably with a special constructor (thus, the default choice would be reproductibility rather than performance).
On some OS, it may seriously reduce speed, because of cache reasons, and need for physical allocation.
If a big bunch of memory is allocated and not accessed, the OS may be able to avoid the physical allocation of the memory...
Of course, it is very unlikely to affect by a great factor the overall performance of the program.
But, on the other side, during a long time, C++ had the principle of zero-overhead : Even a 3% performance penalty (compared to plain C) was inacceptable.
There is a correct solution:
Instead of writing manually, a buggy array class, simply download STLPort, and add, manually, a constructor to std::vector...
Thus, you'll benefit from the implementation quality of STLPort, with the additional feature you want.
But you can't use memcpy with non-POD data, so you immediately lose out by taking that route.
Remember Herb Sutter's wise advice: correct is better than fast.
Do not concern yourself at the design/initial coding stage with these sort of matters. In the vast majority of cases, the "inefficiency" that you're worrying about will not manifest itself, because the program will actually slow down somewhere completely unexpected.
Get the program correct first, then use a profiler to tell you where the time is going and attack those areas. Really, honestly, truly: premature optimisation is the root of many, many problems.
Boost has a fixed array class. Maybe you should check it out.Quote:
Originally Posted by Ujl
This test assumes you are using POD types. The equivalent test in vector is this:Quote:
I've also compared how fast it was to assign values to an array and to copy it to another array:
Code:int* a=new int[size];
int* b=new int[size];
for(int i=0; i<size;i++) a[i]=i;
memcpy(b,a,size*sizeof(a));
Except for initialization, a vector can really be treated as an array of T, just as my code above demonstrates.Code:std::vector<int> x;
std::vector<int> y;
x.reserve(size);
y.reserve(size);
for(int i=0; i<size;i++)
x.push_back(i);
y = x;
// or if you want to use memcpy
// y.resize(size);
// memcpy(&y[0], &x[0], sizeof(int) * size);
In general, the address of the first element of a vector is your array. Then you do with it what you want, just like arrays.Quote:
Do you see any way to make that faster using vector?
Also, the loop to initialize the vector can be replaced by the std::generate_n() algorithm, but I don't know if this will make the code faster or not.
Regards,
Paul McKenzie