본문 바로가기
컴퓨터/GPG Study

GPG Study 1.2 TMP를 이용한 수학연산

by 김짱쌤 2015. 6. 22.

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

삼각함수는 테일러 급수의 전개를 통해서 얻을 수 있다. 이론적인 내용은 다 떼고 결론만 설명쓰면 다음과 같다.

  • 수학적 정리

    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