🔒 Locked

Correct way?

Started by Twili Mar 5, 2009 at 10:04 AM 0 replies 750+ views

Original Post

Mar 5, 2009 at 10:04 AM

I am trying to time how long it take to iterate a list from the front and back and was wondering if I am doing it right (I am not sure if I am iterating right). LARGE_INTEGER LI1,LI2,LIF; QueryPerformanceFrequency(&LIF); double number = (double)LIF.HighPart * UINT_MAX + (double)LIF.LowPart; double fronti, revi, fq = 1.0/number; int f = LIF.LowPart; list l; list::iterator li; list::reverse_iterator lr; for (int N=10000; N<=100000; N=N+10000){ for (int a=0; a<N; a++) l.push_back(a); QueryPerformanceCounter(&LI1); // Time to iterate from the foward direction for(li=l.begin(); li!=l.end(); ++li); QueryPerformanceCounter(&LI2); // here is where we finish timing cout<<"\n"; fronti = ( ( (double)(LI2.HighPart)*UINT_MAX + (double)LI2.LowPart )- ( (double)(LI1.HighPart)*UINT_MAX + (double)LI1.LowPart ) )*fq; cout << "Iterating a list with "<<N<<" elements from the front takes " << fronti <<" seconds."<< endl; QueryPerformanceCounter(&LI1); //Time to iterate from the reverse direction for(lr=l.rbegin(); lr!=l.rend(); ++lr); QueryPerformanceCounter(&LI2); // here is where we finish timing cout<<"\n"; revi = ( ( (double)(LI2.HighPart)*UINT_MAX + (double)LI2.LowPart )- ( (double)(LI1.HighPart)*UINT_MAX + (double)LI1.LowPart ) )*fq; cout << "Iterating a list with "<<N<<" elements from the back takes " << revi <<" seconds."<< endl;}

Antheus

Mar 5, 2009 at 10:52 AM

I prefer something like this:

struct Timer {	Timer() {		QueryPerformanceFrequency(&f);		reset();	}	double elapsed_ms() const {		LARGE_INTEGER now;		QueryPerformanceCounter(&now);		return 1000.0 * (now.QuadPart - start.QuadPart) / f.QuadPart;	}	void reset() {		QueryPerformanceCounter(&start);	}private:	LARGE_INTEGER start;	LARGE_INTEGER f;};std::ostream & operator<<(std::ostream & os, const Timer & t) {	return os << t.elapsed_ms() << " ms";}

And then the benchmark code:

int main(){	Timer t;	std::string s;        t.reset();	for (int i = 0; i < 1000; i++) {		s.append(" ");	}	std::cout << t << " " << s.length() << std::endl;}

It is also a good idea to benchmark only code which has side-effects, otherwise compiler may determine that the loop itself is redundant, and remove it altogether (hence the s.length()).

for(li=l.begin(); li!=l.end(); ++li);

Statements such as this are completely meaningless, since the statement itself doesn't do anything.

To get a meaningful benchmark, there should be something inside the loop. Perhaps something like:

int z = 0;srand(argc);for(li=l.begin(); li!=l.end(); ++li) z += rand();std::cout << z;

srand depends on user supplied argument, so it's not known during compile-time, addition adds some meaningful body to the loop, so the loop is actually performed, and cout uses loop value, so that loop isn't completely omitted.

The running time of algorithm is T(n) = k * O(n) + C. The above adds C and perhaps k, but the important part (O(n)) remains intact. Ideally, one would also repeat the benchmark several times, then calculate the median, or test of statistic significance.

However, in case of such trivial examples as loop iteration, the best way still remains to analyze the generated assembly to determine the exact cost.

In general, effective benchmarks are surprisingly hard to not only perform, but also to evaluate. Hence most don't bother with such synthetic profiling, but prefer profiling actual code.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.