Back to General and Gameplay Programming

for loops and overhead?

Gammastrahler · 2002-06-03T22:42:30

hi, i´ve programmed a vector template class so that i can reuse my code for 2D, 3D or 4D vectors of different data types. therefore, most of the methods must use a for loop like this: template <unsigned int N, class T = float> float CVector<N, T>::Dot(const CVector &pVec) const { float result = 0; for (unsigned int i = 0; i < N; i++) result += v[i] * pVec.v[i]; return result; } my question is: do for loops have any significant overheads / performance drawbacks? thanks Gammastrahler

General and Gameplay Programming Programming

Started by Gammastrahler June 01, 2002 04:44 AM

22 comments, last by Gammastrahler 21 years, 10 months ago

Null and Void

1,088

June 03, 2002 08:10 PM

Here's my quicksort meta template. It's the first 'more than a bubble sort' sorting algorithm I've done as a meta template, so it probably could have been done more elegantly. I based it directly off a recursive quicksort I found online so that I could later compare them. Now, let's pray the source tag doesn't mangle it too badly

    template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR> struct InnerQSort_0;template <class Type, int LHold, int RHold, int Left, int Right, bool LnotR>struct InnerQSort_4 {	static inline void Go(Type Data[], Type &Pivot) {		Data[Right] = Data[Left];		InnerQSort_0<Type,LHold,RHold,Left,Right-1, (Left<(Right-1)) >::Go(Data,Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right>struct InnerQSort_4 <Type, LHold, RHold, Left, Right, false> {	static inline void Go(Type Data[], Type &Pivot) {		InnerQSort_0<Type,LHold,RHold,Left,Right, (Left<Right) >::Go(Data,Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR>struct InnerQSort_3 {	static inline void Go(Type Data[], Type &Pivot) {		if(Data[Left] <= Pivot)			InnerQSort_3<Type,LHold,RHold,Left+1,Right, ((Left+1)<Right) >::Go(Data,Pivot);		else			InnerQSort_4<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data,Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right>struct InnerQSort_3 <Type, LHold, RHold, Left, Right, false> {	static inline void Go(Type Data[], Type &Pivot) {		InnerQSort_4<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data, Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right, bool LnotR>struct InnerQSort_2 {	static inline void Go(Type Data[], Type &Pivot) {		Data[Left] = Data[Right];		InnerQSort_3<Type,LHold,RHold,Left+1,Right, ((Left+1)<Right) >::Go(Data,Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right>struct InnerQSort_2 <Type, LHold, RHold, Left, Right, false> {	static inline void Go(Type Data[], Type &Pivot) {		InnerQSort_3<Type,LHold,RHold,Left,Right, (Left<Right) >::Go(Data,Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR>struct InnerQSort_1 {	static inline void Go(Type Data[], Type &Pivot) {		if(Data[Right] >= Pivot)			InnerQSort_1<Type,LHold,RHold,Left,Right-1, (Left<(Right-1)) >::Go(Data,Pivot);		else			InnerQSort_2<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data, Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right>struct InnerQSort_1 <Type, LHold, RHold, Left, Right, false> {	static inline void Go(Type Data[], Type &Pivot) {		InnerQSort_2<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data, Pivot);	}};template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR>struct InnerQSort_0 {	static inline void Go(Type Data[], Type &Pivot) {		InnerQSort_1<Type,LHold,RHold,Left,Right, (Left<Right) >::Go(Data,Pivot);	}};template <class Type, int Left, int Right, bool LlessR> struct InnerQSort;template <class Type, int LHold, int RHold, int Left, int Right>struct InnerQSort_0 <Type, LHold, RHold, Left, Right, false> {	static inline void Go(Type Data[], Type &Pivot) {		Data[Left] = Pivot;		if(LHold < Left)			InnerQSort<Type, LHold, Left-1, (LHold<(Left-1)) >::Sort(Data);		if(RHold > Left)			InnerQSort<Type, Left+1, RHold, ((Left+1)<RHold) >::Sort(Data);	}};template <class Type, int Left, int Right, bool LlessR>struct InnerQSort {	static inline void Sort(Type Data[]) {		Type Pivot = Data[Left];		InnerQSort_0<Type,Left,Right,Left,Right, (Left<Right) >::Go(Data,Pivot);	}};template <class Type, int Left, int Right>struct InnerQSort <Type, Left, Right, false> {	static inline void Sort(Type Data[]) {	}};template <int Size, class Type>struct QuickSort {	static inline void Sort(Type Data[]) {		InnerQSort<Type,0,Size-1,(0 < (Size-1))>::Sort(Data);	}};

I know that it compiles in GCC (G++) 2.95.4 and up. But heed that warning I gave earlier, if you add more than 10 items to be sorted it tags a LOT of memory to compile it. You may also need to add something like this to the command line: -ftemplate-depth-2000

(I think that's the correct switch, I can't remember at the moment).

[edited by - Null and Void on June 3, 2002 9:11:00 PM]

Anonymous

June 03, 2002 09:34 PM

Say I wanted to have a general Vector class that is templated for the data type is stored and the space the vector resides in. If I want to specialize for float/2, float/3, float/4, can I provide an unspecialized interface and in the implementation provide specialized method implementations? An example of what I mean is below.

  #ifndef VECTOR_H#define VECTOR_Htemplate<typename T, unsigned int D>class Vector {public:	Vector();	Vector(const Vector& v);	// ...	T dot(const Vector& v);private:	T pts[D];};template<typename T, unsigned int D>Vector<T, D>::Vector(){    for (unsigned int i = 0; i < D; ++i)        pts[i] = 0.0;}template<>Vector<float, 2>::Vector(){    pts[0] = pts[1] = 0.0;}template<typename T, unsigned int D>Vector<T, D>::Vector(const Vector& v){    for (unsigned int i = 0; i < D; ++i)        pts[i] = v.pts[i];}template<>Vector<float, 2>::Vector(const Vector& v){    pts[0] = v.pts[0];    pts[1] = v.pts[1];}template<typename T, unsigned int D>T Vector<T, D>::dot(const Vector& v){    T product = 0.0;    for (unsigned int i = 0; i < D; ++i)        product += pts[i]*v.pts[i];    return product;}template<>float Vector<float, 2>::dot(const Vector& v) {	return pts[0]*v.pts[0]+pts[1]*v.pts[1];}

Or do I have to provide a full specialized implementation for float,2? Also what would a non-member (friend) version of dot() look like?

Shannon Barber

1,684

June 03, 2002 09:56 PM

According to the spec, you can partially specialize the template for the second parameter, as 2,3,4,... and leave the first one a template parameter.

According to Microsloth, you can''t (yet). Real Soon NowTM you should be able to when they release the next revision of the VS.Net compiler.

If you''re compiling with gcc you can use partial specialization

  template<typename T>Vector<T, 2>::Vector()]{}

And I think dot would look like this

  template<typename T>T dot(const Vector<T, 2>& lhs, const Vector<T, 2>& rhs){}

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

mcfly

151

June 03, 2002 10:42 PM

While we''re on the subject of abusing compilers with template meta programming I might as well contribute with a neat trick for data copying. It should only be used on POD types however since nothing more than a memory copy will be performed.

  template<class T> void copy(T& a,const T& b){#pragma pack(push,1)struct POD{    char data[sizeof(T)];};#pragma pack(pop)*reinterpret_cast<POD*>(&a) = *reinterpret_cast<const POD*>(&b); }

for loops and overhead?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

for loops and overhead?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines