Back to General and Gameplay Programming

STL Vectors VS. Standard Arrays

General and Gameplay Programming Programming

Started by psyjax September 14, 2004 07:46 PM

25 comments, last by MaulingMonkey 19 years, 7 months ago

122

September 16, 2004 04:46 AM

Quote:Original post by petewood
Quote:Original post by Russell
The answer is "it depends". Creating a "normal" P.O.D. array on the stack is essentially "free". If you start creating vectors of objects in the same way, you may think it is basically the same situation, but using a vector this way is not "free". The vector has to allocate memory and check to see if it needs to grow every time you add something.

Apples and Oranges.

You're not going to be using a stack array in this way and if you don't use the vector in this way the performance will be the same.

Use containers in appropriate ways and they are as efficient as you'll need.

I strongly disagree.
Sometimes you do want stack-based arrays for performance (and not putting too much stress on the allocator).
That's why boost::array exists to extend the STL.

Dmytry

1,151

September 16, 2004 05:22 AM

Old test code,adapted to test vectors and arrays.

// test#include <iostream>#include <fstream>#include <cmath>#include <vector>#include <assert.h>typedef __int64 INT64;typedef unsigned __int64 UINT64;typedef __int32 INT32;typedef unsigned __int32 UINT32;static const double pi=(3.1415926535897932384626433832795);volatile INT64 frdtsc(){	UINT32 resultL,resultH;	__asm{		push eax			push edx			rdtsc			mov resultL,eax			mov resultH,edx			pop edx			pop eax	};	return resultL+ (((INT64)(resultH))<<32) ;};UINT32 rseed=94564567;inline float random(){    rseed *= 0x08088405;    rseed += 1 ;    return (float)((UINT32)(rseed))/((float)((UINT32)0xFFFFFFFF));}static const int iterations=40*1000*1000;#define test(a) {	INT64 _startclocks_;	INT64 _endclocks_;	for(int _n_=0; _n_<iterations ;_n_++){a;}	_startclocks_=frdtsc();	for(_n_=0; _n_<iterations ;_n_++){a;}	_endclocks_=frdtsc();	cout<<( ((double)(_endclocks_-_startclocks_))/((double)(iterations)) )<<endl;}float SIN_TABLE[256];inline float SinUsingTable(float a){	return SIN_TABLE[255 & int(a*128.0/pi)];};/* array/vector testing */using namespace std;const int size2=14;const int size=1<<size2;vector<float> vec;float array[size];void resetarrays(){	for(int n=0;n<size;n++){array[n]=0.1f;vec.at(n)=0.1f;};}/* -- array/vector testing */int main () {	vec.resize(size,0.1f);	{for(int n=0;n<=255;n++){		SIN_TABLE[n]=sin(n*pi/128.0);}}	/*	rseed^=frdtsc();//randomize	rseed^=frdtsc()<<16;	*/		/*	float a;	a=0;	cout<<"testing empty:"<<endl;	test( {a+=20*random();} );	cout<<"I have to write to fool the optimizer:"<<a<<endl;		a=0;	cout<<"testing sin:"<<endl;	test( {a+=sin(20*random());} );	cout<<"I have to write to fool the optimizer:"<<a<<endl;	a=0;	cout<<"testing cos:"<<endl;	test( {a+=cos(20*random());} );	cout<<"I have to write to fool the optimizer:"<<a<<endl;	a=0;	cout<<"testing inverse"<<endl;	test( {a+=1/(20*random());} );	cout<<"I have to write to fool the optimizer:"<<a<<endl;	a=0;	cout<<"testing square root"<<endl;	test( {a+=sqrt(20*random());} );	cout<<"I have to write to fool the optimizer:"<<a<<endl;	a=0;	cout<<"testing sin made using lookup table"<<endl;	test( {a+=SinUsingTable(20*random());} );	cout<<"I have to write to fool the optimizer:"<<a<<endl;	*/	int n=0;	n=0;	resetarrays();	cout<<"testing array[]"<<endl;	test( {array[n]+=0.5-random();n=(n+1)&(size-1);} );	n=0;	//resetarrays();	cout<<"testing vector[]"<<endl;	test( {vec[n]+=0.5-random();n=(n+1)&(size-1);} );		n=0;	//resetarrays();	cout<<"testing vector.at"<<endl;	test( {vec.at(n)+=0.5-random();n=(n+1)&(size-1);} );		/*	*/		// fool advalced optimizers	float b;	for(n=0;n<size;n++){		b+=b*(vec.at(n))*0.0012345;		b+=b*(array[n])*0.001;		b+=array[n];		b+=vec.at(n);		b+=n;	};	cout<<"I have to write that to fool the optimizer:"<<b<<endl;	cout<<"Finished."<<endl;	char c;	cin>>c;	return 0;}

output:

testing array[]139.489testing vector[]130.137testing vector.at126.827I have to write that to fool the optimizer:-9.5376e+028Finished.result 2 (changed order of tests)testing array[]139.1testing vector[]130.132testing vector.at126.984I have to write that to fool the optimizer:-1.07918e+013Finished.

i haven't believed my code and tried moving array to the end of testing sequency,then to the middle, etc.(thought it random generator). Same result.
Strange. Really strange. Must be odd pipeline issue or caching-related thing.

edit: As this shows, when you add one more instruction, speed changes in so odd way that it doesn't matter, and that instruction _may_ decrease speed, but as well may increase, and second happens often enough.

and yes, vector have slower features such as resizing but you just can't resize normal array.
edit2: in minutes after posting it i was rated by -15. But it's real test results i got! No kidding!

[Edited by - Dmytry on September 16, 2004 5:22:21 AM]

snk_kid

1,312

September 16, 2004 05:43 AM

Quote:Original post by swiftcoder
Yes and No, STL is implemented primarily for reliability

no it isn't just that.

Quote:Original post by swiftcoder
(i.e. extensive exception checking)

Where the only operation i think of that throws an exception is vector's at method, STL containers are written with exception safe code.

Quote:Original post by swiftcoder
, and I'm afraid that speed sometimes suffers.

That would be your user-defined type's fault not STL containers, blame it on your written or implicitly defined copy constructor's so slow initialization for that.

Also blame it on irresponsible usage & lack of thought.

Quote:Original post by swiftcoder
If you write a simple list or vector implementation, with just the basic functions, you can reliably find 10-15% speed gains.

yes gain 10-15% speed gains for schematically incorrect/silly behaviour.

Lets make a scenario shall we, lets say we write a hand made list we have an operation that lets you add elements to the list we decide to try and be more efficent so we store pointers to the instance.

Okay fine we begin to use this list in some function some where we add an element that was declared in the scope of that function, opps you have dangling pointer syndrome when the function's scope is ended, another thing is you cannot use this operation on literals.

Okay we make some changes the list now passes by constant reference and then copy constructs the instance on the heap and adds it to the list this deals with both isssues. Oh Wait a minute thats what standard library containers do already oh well....

And before anyone says that they would use something else other than the generic memory operators new/delete or a different memory model well that is an invalid arguement because you can use custom allocators.

Quote:Original post by swiftcoder
However, it doesn't supply those convienient std::out_of_bounds exceptions :(

only method i can think that does that is the "at" method of vector.

Qw3r7yU10p!

819

September 16, 2004 06:06 AM

Quote:Original post by Tramboi
I strongly disagree.
Sometimes you do want stack-based arrays for performance (and not putting too much stress on the allocator).
That's why boost::array exists to extend the STL.

What are you disagreeing with?

Russell said the vector has to check to see if it needs to grow which, if you were using it like your c-style array, isn't true.

If you're disagreeing with my statement that "they are as efficient as you'll need" then that's a different point.

Max_Payne

757

September 16, 2004 06:17 AM

Quote:Original post by Magmai Kai Holmlor
This results in code that has an exploitable buffer - for example all those security fixes for IE.
If the array isn't constant, use std:vector or write buggy code.

Thats totally irrelevant. IE had flaws because of poor, lazy coding. The errors in there would have been easily avoided by any competent programmer. Stupid mistakes like not doing bound checking at all. On that note, you're going to need to perform bound checking with std::vector<> as well... I don't use std::vector<> everywhere, I use C strings, and my code has very few bugs (and they are rarely related to those things).

Anyhow, did you learn to program with Java or something? You seem to have the "the language should think for you" mentality.

What makes a competent programmer is mostly the seriousness. If you simply don't care about writing safe code, your code will have bugs, no matter what language and programming techniques you use.

Looking for a serious game project?
www.xgameproject.com

Dmytry

1,151

September 16, 2004 08:05 AM

have someone else checked my benchmark ?
I still don't really believe in results.
btw, as about lazy coding.....standard c lib are developed by lazy programmers as well.

MaulingMonkey

1,729

September 16, 2004 08:58 AM

Well, I tried timing assignment over operator[] on vectors vs standard arrays, but time() returns results in seconds, and my linux box makes programs that segfault immediately on load whenever I try to make built-in arrays around 10-million elements or so (and no, a 1M array of 10 ints each dosn't work either).

That said, it took less than a second for my program to eat through:

int size = 10000000; //10 millionstd::vector< int > my_array( size );for ( int i = 0 ; i < size ; ++ i ) my_array = i;</pre><br><br>on my old 600mhz debian box, so I really wouldn't worry too much psyjax. You might suffer a performance hit (probably small) in debug mode, but your compiler should optimize it all away in release mode. If it dosn't, by god man, upgrade compilers.

STL Vectors VS. Standard Arrays

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

STL Vectors VS. Standard Arrays

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines