GPG Study 1.2
TMP를 이용한 빠른 수학연산
템플릿 메타 프로그래밍 (TMP)
- 템플릿 : Generic한 프로그래밍을 목표로 만들어진 C++ 문법
template<class T> //For Ani Type T
void GenericFinc(T param) //About T Type Param
{ param.DoSomething(); } //Call DoSomething()
템플릿 메타 프로그래밍
템플릿의 타입추론이 컴파일 시간에 이루어진다는 것을 응용하여 컴파일 시간에 가능한 중간작업들을 미리 처리하는 프로그래밍 방법론. 템플릿을 일종의 Pre-Compiler로 사용하여 최적화한다. 컴파일 시간은 보다 길어지지만, 런타임의 수행시간이 짧아지게 프로그래밍 할 수 있다. 여기에 템플릿 특유의 Generic한 파워가 합쳐지면서 엄청난 생산성 향상을 가져올 수 있다. (잘 읽고 잘 쓸 수 만 있다면...)
STL, Boost 등의 유명 C++ 라이브러리들이 이 TMP를 적극 활용하고 있다. 기존 C++만 알던 사람들은 아예 다른 언어라고 생각할 수 있을 정도로 다른점이 많다. (실지로 다른 언어라고 말하는 사람도 많이 봤다.) 알면 알수록 신기하고 새로워서 자꾸 들어가려고 하다보면 나같은 초보 프로그래머들이 주화입마에 걸리기 쉬우니 조심하면서 들어갈 것.
TMP로 피보나치
- 일반 C++(머글)에서 피보나치 수열 만드는 코드
int Fibo(int n)
{
if ( n <= 0 )
return n;
else
return Fibo( n - 1 ) + ( n - 2 );
}
//실제로 쓸일은 없을 확률이 높다...
- TMP로 피보나치 미리 계산하는 코드
//템플릿 구조체를 활용하여 숫자 n마다 하나씩 Fib 템플릿 구조체를 만든다.
template< unsigned N >
struct Fib
{
enum{ //상수 멤버 변수처럼 enum을 사용한다.
Val = Fib<N-1>::Val + Fib<N-2>::Val,
};
}
//템플릿 특수화를 사용 0, 1 예외 케이스에 대한 Fib 구조체를 만든다.
template<> //템플릿 특수화는 템플릿 인자를 빼고
struct Fib<0> //여기에 특수화된 인스턴스를 넣는다.
{
enum {Val = 0,};
};
template<>
struct Fib<1>
{
enum {Val = 0,};
};
잘 모르겠으면 위 설명을 다시 똑띠 읽어보고, 그래도 모르겠으면 앞으로 설명할 내용을 눈에 힘주고 읽어본뒤, 그래도 모르겠으면, 구글링 or Effective C++ 템플릿 프로그래밍 파트부터 읽어보는 것을 추천한다.
GPG 책에서 설명하는 내용을 다시 천천히 따져보면서 넘어가자.
여기서 중요한 포인트는 템플릿 구조체
Fib
의enum Val
이다. TMP에서 enum은 컴파일 타임에 미리 값이 정해지고, 이름이 있는 상수라는 점에서 자주 변수로 활용된다. 잘 기억하자.Fib<unsigned N>
에서 N은 위의Class T
와 같은 의미, 즉 템플릿 인자로 사용되었다. TMP에서 템플릿 인자는 마치 함수의 인자처럼 사용된다. 이 값은 컴파일시점에 알 수 있는 실제 값이어야 한다.Fib<N>
에서Val
은 재귀적으로 정의되었다. 아래 코드를 템플릿 구조체에서 멤버변수(enum이지만...)를 가져오는 방식 (Fib<n-1>::Val
) 을 배울 수 있다.
Val = Fib<N-1>::Val + Fib<N-2>::Val
Fib<N>
시점에서 Val을 추론하기 위해서는Fib<N-1>
과Fib<N-2>
가 필요하다. 그리고Fib<N-1>
을 알기 위해서는 ... 그러다가 결국 우리가 특수화한 0, 또는 1 에 도달하여 컴파일 시간에 파악할 수 있는 값이라는 것을 깨닫게되고 다시 길을 돌아서... 뭐 이런 재귀적인 방식으로 TMP에서Fib<N>
의Val
값을 가져오는 것이다. >Fib::Val >= Fib::Val + Fib::Val >= Fib::Val + Fib::Val + Fib::Val + Fib::Val >= 1 + 0 + 1 + 1 + 0 >= 3- 이 모든것이 컴파일 시점에서 처리된다. 만약 우리가 템플릿을 사용하여 피보나치 매크로를 만든다면 (
#define FIBO(n) Fib<n>::Value
) 런타임에서만큼은 recursion 함수보다 매우 빠른 속도로 원하는 값을 가져올 것이다.
TMP로 Factorial
- Factorial in 머글 C++
unsigned Facto( unsigned n )
{
if( n <= 1 )
return 1
else
return n * Facto( n - 1 );
};
- Factorial in TMP
//N에 대한 재귀적 정의
template< unsigned N >
struct Facto
{
enum{
Val = N * Facto< N - 1 >::Val,
};
};
//Base
template<>
struct Facto<1>
{
enum{ Val = 1 };
};
//함수같이 템플릿을 매크로사용
#define FACTO(n) Fact<n>::Val
TMP로 삼각함수
앞서 언급한 피보나치나 팩토리얼같은 코드는 학교에서 배우는 C++ 연습문제에나 나올법하다. 이런 코드를 게임에서 실제로 쓸일은 거의 없을 것이라고 생각한다. 하지만 삼각함수는 다르다! 삼각함수는! 게임 개발을 좀하다보면 이리 돌리고 저리 돌리고 여기저기에 삼각함수 쓸일 매우 많다. 하지만 이 계산을 직접 하라고 시키면 제법 오래걸리는 명령이다. 이때 TMP가 출동하면 어떨까?
- T
- M
- P
삼각함수는 테일러 급수의 전개를 통해서 얻을 수 있다. 이론적인 내용은 다 떼고 결론만 설명쓰면 다음과 같다.
수학적 정리
0 <= theta < 2*pi 인 각도 theta에 대하여, sin (theta) = theta - (theta^3/3!) + (theta^5/5!) + ....
전개식을 재귀적인 형태로 변경하면
sin (theta) = x * term(0); term(n) = 1 - theta^2 / (2n + 2) / (2n + 3) * term( n + 1);
삼각함수 in 머글 C++
double Sin( double fRad )
{
const int iMaxTerms = 10; //정확도
return fRad * SinIter( fRad, 0, iMaxTerms);
}
double SinIter( double fRad, int i, in iMaxTerms )
{
if( i > iMaxTerms ){
return 1.0;
}
else{
double calcValue = (fRad*fRad / (2.0*i+2.0) / (2.0*i+3.0);
return 1.0 - calcValue * SinIter(fRad, i+1, iMaxTerms));
}
}
- 삼각함수 in TMP
template< double R >
struct Sin
{
enum{ MaxTerms = 10 };
static inline double sin()
{
//Val이 아니라 Val()이라는 것이 의아할 수 있다.
//더 아래의 코드를 보자.
return R * SinIter<R,0,MaxTerms>::Val();
}
}
template< double R, int I, int MaxTerms >
struct SinIter
{
//enum으로 Iteration에 필요한 세가지 변수를 사용한다.
enum
{
//Continue해도 되는지에 대한 boll값이라고 생각하자.
Continue = (I + 1) != MaxTerms,
//다음번 SinIter에서 index
NextI = (I + 1) * Continue,
//다음번 SinIter에서 maxTerms
NextMaxTerms = MaxTerms * Continue
};
//static inline 함수를 통해서 컴파일 시간에 Val값을 계산!
//enum으로 value를 결정하는 것과 유사하다.
//Val을 재귀적으로 계산하여 최종 sin값을 구한다.
static inline double Val()
{
static int calcValue =(R*R/(2.0*I+2.0) / (2.0*I+3.0);
return 1 - calcValue * SinIter<R*Continue, NextI, NextMaxTerms>::Val();
}
};
TMP와 컴파일러
TMP는 사실 컴파일러가 어디까지 재귀순환을 지원해줄 수 있느냐에 따라서 될수도 있고 안될 수 도 있다. VS에서는 이것을 도울 수 있는 옵션을 제공한다. #pragma inline_depth(255)
과 inline_recursion(on)
을 사용해 보자.
혹은 좀더 주화입마에 빠질 욕심이 있는 분은 inline depth를 적게 사용하는 템플릿 프로그래밍을 고려할 수 있다. 재귀 호출 없이 TMP를 짤 수 도 있다는 것이다. 하지만 자세한 내용은 독자에게 패스한다. [GPG 1.2 목록 1.2.2참조]
어떤 컴파일러는 부분특수화를 잘 지원하지 못한다고 한다. VC6 수준의 설명이라 이제 오래전 이야기로 넘어가도 될 것 같다. 템플릿 인자로 부동 소수점을 받았을 때의 지원 여부도 생각할 만하다. C++ 표준에는 부동소수점을 템플릿 인자로 받을 수 없다고 나와있다. 그래서 double에 대한 참조로 템플릿 인자를 받는 방법을 생각할 수 있다.
TMP와 행렬 (마지막)
3D게임 프로그래밍에서 행렬연산은 정말로 자주사용된다. 행렬 연산에 핵심적인 몇가지 함수를 TMP로 구현하면 상당한 속도향상을 가져올 수 있다. GPG에서는 단위행렬, 전치행렬, 행렬곱의 예제가 나와있다. 행렬의 TMP에서 핵심적인 로직은 대부분 단위행렬에 있기 때문에 (양이 상당하기에 전부다 소개하기는 힘에 부치기에) 단위 행렬만 소개하고 여기서 마치기로 한다.
- 단위행렬 in 머글 C++
//머글 C++
matrix33& matrix33::identity()
{
for (unsigned c = 0; c < 3; c++)
for (unsigned r = 0; r < 3; r++)
{
col[ c ][ r ] = ( c == r ) ? 1.0 : 0.0;
}
return *this;
}
단위행렬 in TMP 의사코드
단위 행렬 그냥 짤땐 쉬운데 TMP로 짜려면 좀 고민이 필요하다. 열과 행을 루프로 돌리는 방식이 기존의 일차원 반복과는 좀 다르기 때문이다. 의사코드로 먼저 공간을 한번 채워본다.
Maxtix( N x N ) matrix; // 정방행렬만
for ( int i = 0 ; i < N x N ; i ++ )
{
//N이 3인 경우의 예시도 곁들인다.
int m = i % N; // 0, 1, 2, 0, 1, 2, 0...
int n = (i / N) % N; // 0, 0, 0, 1, 1, 1, ...
if( m == n )
matrix(m, n) = 1.0f;
else
matrix(m, n) = 0.0f;
}
단위행렬 in TMP 리얼 코드
배운 TMP 방식의 총집편이자 이 TMP소개글에서 가장 어려운 보스몹이기도하다. 음식과 영약 도핑을 잊지말도록 하자.
//TMP버전
template< class Mtx, unsigned N > struct IdMtx
{
//Mtx를 인자로 받아서 값을 채워 돌려주는 TMP함수
//함수내에서 IdMtxImpl라는 sub-TMP함수를 다시호출하는 방식을 사용한다.
//하나의 템플릿 클래스로 재귀처리를 하기 어려운 경우 wrapper클래스를 사용한다.
static inline void eval( Mtx& mtx )
{
IdMtxlmpl< Mtx, N, 0, 0, 0 >:: eval( mtx );
}
};
// 행렬의 각 성분을 배정한다.
// 템플릿 인자는 각각 행렬, N(의사코드에서 그거),Column , Row, Index
template< class Mtx, unsigned N, unsigned C, unsigned R, unsigned 1 >
struct IdMtxlmpl
{
enum
{
NextI = 1 + 1, //Next Index
NextR = NextI % N, //Next Row
NextC = NextI / N % N //Next Column
} ;
//실제 추산함수
static inline void eval( Mtx& mtx )
{
//C 랑 R값만 비교하면 값 추정은 끝난다.
mtx[ C ][ R] = ( C == R ) ? 1.0 : 0.0;
//그리고 다음번 I, C, R값을 가지고 다음 행렬값으로 이동하여 다시 추산한다.
IdMtxlmpl< Mtx, N, NextC, NextR, NextI >::eval( mtx );
}
} ;
//3x3, 4x4 행렬을 위한 특수화
//반복 수행을 종료할 boundary case를 만들어둬야 무한루프에 빠지지 않는다.
tempLate<> struct IdMtxlmpl< matrix33, 3, 0, 0, 3*3 >
{
static inLine void eval( matrix33& ) {}
};
tempLate<> struct IdMtxlmpl< matrix44, 4, 0, 0, 4*4 >
{
static inLine void eval( matrix44& ) { }
};
//매크로
#define IdentityMtxT( txType , Mtx, N ) IdMtx< MtxType, N >::eval( Mtx )
'컴퓨터 > GPG Study' 카테고리의 다른 글
GPG Study 3.8 Fuzzy 논리 (0) | 2015.07.17 |
---|---|
GPG Study 1.7 자원과 메모리 관리 (0) | 2015.07.01 |