메타 함수, 템플릿 1

메타 함수(Meta Function)은 컴파일 타임에 실행되는 함수가 아니라, 컴파일러에서 사용되거나 템플릿 메타 프로그래밍에서 사용하는 함수나 클래스 템플릿을 가리키는 용어이다.

 

즉, 런타임에서가 아니라, 컴파일 타임에 그 값이 미리 계산이 되어서 알 수 있다.

 

C++ 의 메타프로그래밍에는 반복문 구조가 없어 재귀적으로 템플릿을 구현해야한다는 것을 기억하자.

 

솔직히 처음부터 복잡한 코드를 보면 이게 코드가 맞나 싶을 정도로 어지러운 코드도 많은 것 같다.

 

간단한 예시부터 이해해보자.

---

피보나치 수열의 n번째 수 구하기

 

피보나치 수열은 다음과 같다.

1, 1, 2, 3, 5, 8, ...

 

그리고 그 공식은 arr[i] = arr[i-1] + arr[i-2] 이다.

 

위 수열에서 n번째 값은 구하기 위해서 여러가지 방법을 사용할 수 있다.

 

첫 번째로 재귀로 구현하는 방법이다.

unsigned long long fibonacci_recur(const unsigned long long n)
{
	if (n == 1 || n == 2) return 1;
	else return fibonacci_recur(n - 1) + fibonacci_recur(n - 2);
}

매우 간단하지만, 대부분 비효율적인 코드라고 생각할 것이다. 같은 인자로 함수를 여러번 호출하여 중복되는 불필요한 계산을 하기 때문이다. 또한 위 코드로 값이 큰 n 값을 계산하려고 하면 스택 오버플로우가 발생하거나 시간이 많이 걸리는 것을 알 수 있을 것이다.

 

두 번째로 중복되는 계산을 없애고 memoization을 이용(dp)해서 구현해보자.

unsigned long long fibonacci_memoi(const unsigned long long n)
{
	vector<unsigned long long> v(n + 1, 1);

	for (auto i = 3; i <= n; ++i)
	{
		v[i] = v[i - 1] + v[i - 2];
	}
	return v[n];
}

이런 구현이라면 불필요하게 반복되는 계산을 줄이고 O(n)에 해결할 수 있다!

매우 좋은 방법이다. 하나 아쉬운 점은 위 코드는 런타임에 실행되기 때문에 n값이 10'000'000정도만 가도 시간이 조금 걸리는 것을 볼 수 있다.

 

이번에는 메타함수를 이용하여 메타 프로그래밍을 해보자.

template<unsigned long long N>
struct fibonacci
{
	enum : unsigned long long { value = fibonacci<N - 1>::value + fibonacci<N - 2>::value };
};

template<>
struct fibonacci<1>
{
	enum : unsigned long long { value = 1 };
};

template<>
struct fibonacci<2>
{
	enum : unsigned long long { value = 1 };
};

나는 처음에 이런 템플릿 코드를 보았을 때 당황하고 신기해하기도 했다.

하나하나 따라가 보면 위 템플릿 구조체 3개는 재귀 구조를 이루고 있다는 것을 알 수 있다.

아래 1과 2에 대해서는 재귀 형식에서의 base case 이다.

fibonacci<1>::value = 1, fibonacci<2>::value = 1 이라고 선언해준 셈이다.

 

ex)

fibonacci<5>::value = fibonacci<4>::value + fibonacci<3>::value;

=> fibonacci<4>::value = fibonacci<3>::value + fibonacci<2>::value;

=> fibonacci<3>::value = fibonacci<2>::value + fibonacci<1>::value;

 

다시 확인해보면 알 수 있지만, 재귀 호출 코드를 템플릿화 시켜서 해준 것 뿐이다.

그렇다면 재귀 함수로 작성했을 때와 어떤 차이가 있을까?

 

먼저 C++에서의 제네릭은 어떻게 컴파일 되는지 생각해보면 된다.

컴파일러는 베이스가 되는 제네릭 템플릿 클래스를 기반으로 실제 코드에서 어떤 타입이 이 클래스를 기반으로 사용될 경우, 해당 타입에 대한 클래스 코드를 생성한다.

(예를 들어, vector<int>타입이 본문에 사용되고 있을 경우, 이 코드를 컴파일 시 컴파일러는 STL의 vector<T>에 기반하여 vector<int> 클래스 코드를 생성한다. => 템플릿 인스턴스화)

 

마찬가지로 위 피보나치 템플릿 구조체도 컴파일 시점에 미리 코드를 생성한다.

즉, fibonacci<5>가 컴파일 시점에서 식별될 경우, 위에서의 재귀와 동일하게 fibonacci<5>, fibonacci<4>, fibonacci<3>, fibonacci<2>, fibonacci<1>의 구조체가 컴파일 시점에 인스턴스화 되어 각 구조체의 value 값이 미리 결정이 된다.

따라서 fbonacci<5>::value는 런타임 시점에 계산되거나 결정된 것이 아니라 컴파일 시점에 미리 계산된 상수(or enum)이다.

 

템플릿 메타 프로그래밍으로 위와 같이 미리 계산하면 런타임에서 계산하는 시간이나 자원 사용을 줄일 수 있는 큰 장점이 있다.

다만, 위에서 언급되었듯이 복잡해질 수록 (위에서는 n값이 커질 수록) 템플릿 인스턴스화 양이 많아 지기 때문에 컴파일 시간이 길어질 수 있고, 심할 경우에는 컴파일러가 복잡하다고 컴파일을 거부(?)할 수도 있다.

 

실제로 n이 1000만 되어도... (하하)

 

 

마지막으로 각 실행시간을 비교해보자.

int main()
{
	{
		auto start = chrono::high_resolution_clock::now();
		auto value = fibonacci<100>::value;
		auto end = chrono::high_resolution_clock::now();
		auto time = chrono::duration_cast<chrono::microseconds>(end - start);
		cout << "fibonacci<100>::value = " << value << endl;
		cout << "Template Meta Programming::Duration: " << time.count() << endl;
	}
	{
		auto start = chrono::high_resolution_clock::now();
		auto value = fibonacci_recur(45);
		auto end = chrono::high_resolution_clock::now();
		auto time = chrono::duration_cast<chrono::microseconds>(end - start);
		cout << "fibonacci_recur(45) = " << value << endl;
		cout << "Recursive::Duration: " << time.count() << endl;
	}
	{
		auto start = chrono::high_resolution_clock::now();
		auto value = fibonacci_memoi(100);
		auto end = chrono::high_resolution_clock::now();
		auto time = chrono::duration_cast<chrono::microseconds>(end - start);
		cout << "fibonacci_memoi(100) = " << value << endl;
		cout << "Memoization::Duration: " << time.count() << endl;
	}
}

// output 
fibonacci<100>::value = 3736710778780434371
Template Meta Programming::Duration: 5

fibonacci_recur(45) = 1134903170
Recursive::Duration: 7683367

fibonacci_memoi(100) = 3736710778780434371
Memoization::Duration: 15

 

먼저 짚고넘어가야 할 것은 fibonacci<100>::value에 대해 걸린 시간은 무시해도 된다. (메모리 IO) 그리고 재귀 호출을 45로 한 경우 좀 더 커질 시 시간이 매우 오래걸리기 때문이다. 마지막으로 memoization을 이용한 함수에는 vector를 선언하고 초기화하는 내용까지 들어가 있다.

 

먼저 눈에 띄게 보이는 것은 재귀 호출이 매-----우 오랜 시간이 걸린다는 것이다. 함수 호출에 대한 오버헤드도 있을 뿐더러, 반복되는 계산을 하기 때문이다.

memoization을 이용했을 때는 반복문을 수행했던 횟수와 비례해서 시간이 걸린 것을 확인할 수 있었다. (물론 값은 같다.)

 

---

bitset이 1로 채워져 있나 확인하기

 

다음 코드는 size 만큼의 비트가 1로 되어 있을 때의 값을 확인할 수 있는 구조체이다.

Size 값에 따라 1로 채워져 있을 때의 값을 반환해 준다.

ex) Size = 8 => 255

template<int Size>
struct FullBits { enum { value = (1 << (Size - 1)) | FullBits<Size - 1>::value }; };

template<>
struct FullBits<1> { enum { value = 1 }; }; 

template<>
struct FullBits<0> { enum { value = 0 }; };

---

 

이렇게만 보면 굳이 템플릿 메타 프로그래밍으로 작성해야 되나? 라고 느낄 수 있겠다. 실제로 간단하게 실행했을 때는 시간이 얼마 차이가 안났기 때문이다. 그러나 수가 커질 수록, 식이 복잡해 질 수록 시간이 더 걸릴 수 있는 여지가 존재한다.

또한 계산 뿐만 아니라 다수의 값에 대한 관계를 설정하는데도 이용할 수도 있고  (Typecast 포스팅에서 다뤘었다.)  apply (C++17) 구현시에도 사용할 수도 있다.

 

정말 다양하게 활용될 수 있다... (생각해 내기가 어려운것 같다!!!...)