Template Meta Programming으로 matrix 라이브러리 만들기 (1)

최근 몇 주 동안 C++로 개인 matrix library를 만드는 개인 프로젝트를 진행하였다. 프로젝트의 목표는,

1. C++ 17/20 feature들 써보기
2. 템플릿 공부
3. Unit test, documentation 작성
4. 다음 개인 프로젝트에 쓸 수 있을 정도까지 만들기

정도이고, 이 포스트를 작성하는 시점에서 계획했던 목표를 얼추 이룬 것 같아서, 프로젝트를 진행하며 느낀 점이나 배운 것을 기록하는 겸, 또 정보 공유 목적으로 포스트를 작성한다. https://github.com/pjessesco/peanut

GitHub - pjessesco/peanut: Simple header-only C++20 matrix library using expression templates

이 포스트는 프로젝트에 대한 자세한 내용보다는, 논문으로 치면 motivation이나 idea에 가까운 내용을 다룬다.

1. Template 

C++ 에는 개발자가 특정 자료의 type을 추상화하고 컴파일러가 필요할 때마다 type을 추론해서 그에 맞는 코드를 생성하는 기능이 있는데, 이를 template이라고 한다. 가장 많이 사용되는 STL 중 하나인 vector를 예로 들어보자.

std::vector<int> a;   // std::vector<int> 클래스 생성
std::vector<float> b; // std::vector<int> 클래스 생성

int, float를 갖는 vector를 생성하는 코드이다. <> 사이에는 int, float 말고도 임의의 자료형이 들어갈 수 있고, 당연하게도 모든 경우에 대해 vector가 정의되어 있지 않다. 컴파일러가 std::vector<int>, std::vector<float> 를 정의하는 코드를 컴파일 시간에 생성해 위 코드가 실행될 수 있다. 

여기서 중요한 점은 이 작업이 컴파일 시간에 진행된다는 것이다. 여기서 오는 단점이 몇 가지 있는데, 필요한 코드 생성을 하기 때문에 컴파일되는 바이너리 파일이 커질 수 있고 컴파일 시간이 늘어날 수 있다. 그런데... 이때까지 template을 쓰면서 이런 단점을 크게 체감해본 적은 없는 것 같다. 또 코드를 직접 생성하기 때문에, 실제 프로그램 실행 시 수행되는 연산을 컴파일 시간으로 당겨올 수 있으면 그게 바람직한 방법이라고 생각한다.

2. Template Meta Programming

Meta라는 단어를 보면 (특히나 요즘) 떠오르는 단어가 많다. Template meta programming에서의 meta와 가장 비슷하게 쓰이는 meta는 '메타 인지'의 그것인 것 같다. 메타 인지를 내가 아는대로 간단하게 요약하면 "알고 있다는 걸 아는 것"인데, 음... 숲의 숲을 본다고 표현할 수 있을까? 

Metaprogramming을 그런 맥락에서 보면 프로그래밍을 하는 프로그래밍이라고 뭔가 생각할 수 있을 것 같다. C++에서 template meta programming은 template을 이용해 필요한 type을 생성하는 것을 넘어서, 연산에 필요한 코드를 생성해서 같이 컴파일을 해 실행 시간에 보통 수행되는 연산을 컴파일 타임에 수행하게 하는 기법을 말한다. 자세히 설명하는 자료가 많으니 이 포스트에선 넘어감.

3. Naive한 행렬 구현의 단점

쉽게 생각할 수 있는 행렬 구현을 살펴보자. 제일 naive 한 것보다는 살짝 더 나아가서 행렬을 구현하고자 하면 아래와 같이 구현할 수 있을 것이다. 

template <typename T, size_t Row, size_t Col>
    requires std::is_arithmetic_v<T>
struct NaiveMatrix{
    NaiveMatrix(const NaiveMatrix &mat){
        std::cout<<"constructor\n";
        m_data = mat.m_data;
    }

    template <typename ...TList> 
        requires std::conjunction_v<std::is_same<T, TList>...>
    NaiveMatrix(TList ... tlist) : m_data{std::forward<T>(tlist)...} {}

    NaiveMatrix operator+(const NaiveMatrix &o) const{
        NaiveMatrix tmp(*this);
        for (int i = 0; i < Row*Col; ++i) {
            tmp.m_data[i] += o.m_data[i];
        }
        return tmp;
    }

    std::array<T, Row*Col> m_data;
};

Element의 자료형 (int/float 등), 행/열의 수를 템플릿 인자로 받는 NaiveMatrix 클래스이다. Template을 이용해 컴파일러가 필요한 코드를 직접 생성하게 해서 개발자가 직접 Matrix22f, Matrix33f, Matrix44i 등을 직접 만들 필요가 없어졌다. 

행렬 간 덧셈을 표현하는 operator+()를 살펴보자. 현재 matrix는 그대로 두면서 두 matrix의 값을 합한 새로운 matrix를 return 하는 함수이다. 현재 matrix를 복사한 후, Row*Col 반복문을 돌면서 element를 더하고, 생성한 행렬을 return 한다. 여기까지 보면 큰 문제는 없어 보인다. 이제 아래와 같은 use-case에 대해 어떤 일이 일어날지 생각해보자.

NaiveMatrix<int, 100, 100> mat1{1,2,3,4,...10000};

auto mat = mat1 + mat1 + mat1 + mat1 + mat1 + mat1 + mat1 + mat1 + mat1 + mat1 + mat1 + mat1;

constructor
constructor
constructor
constructor
constructor
constructor
constructor
constructor
constructor
constructor
constructor

operator+() 가 하나씩 실행될 때마다 행렬을 매번 복사하는 것을 알 수 있다. 또한 m_data의 각 element에 대해 덧셈을 하는 Row*Col 반복문도 N번 실행될 것이다. 이 작업은 특히 행렬의 크기가 커지면 커질수록 효율이 떨어지게 된다. 매번 복사를 하는 것을 피하고 싶으면 다음과 같은 구현을 생각해볼 수 있다 (템플릿 생략).

// Omit template
NaiveMatrix sum_6(const NaiveMatrix &m1,
                  const NaiveMatrix &m2,
                  const NaiveMatrix &m3,
                  const NaiveMatrix &m4,
                  const NaiveMatrix &m5,
                  const NaiveMatrix &m6){
    NaiveMatrix mat;
    for(int i=0;i<Row*Col;i++){
        mat.m_data[i] = m1.m_data[i] + m2.m_data[i] + m3.m_data[i] +
                        m4.m_data[i] + m5.m_data[i] + m6.m_data[i];
    }
}

모든 operand를 인자로 받아, 한 반복문에서 모든 인자의 element의 합을 구한다. 이렇게 하면 불필요한 복사를 할 필요가 없이 위의 코드보단 효율적으로 행렬 합을 계산할 수 있다.

하지만 컴퓨터에겐 효율적일 수는 있어도 개발자에겐 그렇지 않다. 현실적으로 모든 경우에 대한 함수를 만들 수 없기 때문이다.

4.. TMP로 얻을 수 있는 것 (Expression Template)

앞서 TMP는 연산에 필요한 코드를 생성하는 기법이라고 했다. 바로 전 구현의 문제점은 사람이 모든 경우에 대한 함수를 만들 수 없다고 했는데, 이를 TMP로 해결할 수 있을까?

사실 TMP, 그 중에서도 expression template이라고 불리는 기법은 행렬을 다루는 라이브러리에서 많이 쓰이는 기법이다. 제일 많이 쓰는 라이브러리 중 하나인 eigen은 물론, armadillo 등 여러 라이브러리가 이와 같은 아이디어를 채택해 구현하였다. 아이디어를 간단하게 요약해보면 다음과 같다. 프로그래밍 언어론까진 아니더라도 오토마타 수업을 들었으면 이해하기가 조금 수월할 것이다.

우선 모든 행렬/연산을 각각의 클래스로 나타낸다. 구현/detail은 제외하고 예를 들어보자.

class Expression{};

class Matrix : Expression{}; // Matrix

template <typename E1, typename E2>
class MatrixSum : Expression{}; // +

행렬 (Matrix), 행렬 덧셈(MatrixSum) 이 모두 Expression을 상속받고 있고, MatrixSum은 추가로 템플릿 파라미터 두 개를 받는다. 여기서 E1, E2에는 다른 expression 타입이 들어갈 것이다. 위 클래스들을 이용해 아래와 같이 표현한다.

// MatrixSum<Matrix, Matrix>
auto mat1 = mat + mat;

// MatrixSum<MatrixSum<MatrixSum<Matrix, Matrix>, Matrix>, Matrix>
auto mat2 = mat + mat + mat + mat​

 

이렇게 expression tree를 구성함으로써 얻는 다른 이점은, 저 MatrixSum<MatrixSum<...>> 타입의 객체를 만드는 시간과 그걸 evaluation하는 것을 분리할 수 있다는 것이다. 위의 예시에서도 (mat + mat + mat + mat) 부분이 실행되는 시점에는 인스턴스를 생성할 뿐 실제 덧셈을 수행하지 않는다. 이렇게 생성한 객체만 가지고 있다가 실제 계산한 값이 필요한 시점에 한 번만 계산하도록 구현이 가능하다. 이렇게 함으로써 불필요한 복사 연산을 줄일 수 있음에 더해 반복문을 여러 번 실행할 필요도 없게 된다. 이를 lazy evaluation이라고 한다.

armadillo / eigen

이어지는 포스팅부터 내가 실제로 어떻게 구현했는지 자세히 다룰 예정이다.

Reference

https://hpac.cs.umu.se/teaching/sem-accg-14/Armadillo.pdf

https://conradsanderson.id.au/pdfs/sanderson_curtin_armadillo_pasc_2017.pdf