C++의 동시성

 

C++11부터 thread 클래스를 공식적으로 지원하여 멀티 스레드 프로그램을 만들 수 있게 되었다.

 

싱글 스레드로 작업하기

스레드를 만드려면 std::thread 클래스의 인스턴스를 만들고, 인자로 함수를 전달하면 된다.

이후 std::join()을 호출해서 스레드가 작업을 완료할 때 까지 메인 스레드를 대기시키면 된다.

 

void threadProc()
{
    std::cout << "thread ID: ";
    std::cout << std::this_thread::get_id() << '\n';
}

std::thread thread1(threadProc);
thread1.join();

 

스레드의 흐름은 정확히 예측할 수 없고, 스레드간의 실행 순서가 달라지거나 겹칠 수 있다.

 

 

멀티 스레드로 작업하기

두 개 이상의 스레드(메인 스레드 제외)를 동시에 실행한다. 

 

std::thread threads[5];

for (int i = 0; i < 5; ++i) threads[i] = std::thread(threadProc);
for (auto& thread : thread) thread.join();

 

인자로 람다 표현식을 넘겨주는것도 당연히 가능하다.

 

 

 

 

뮤텍스를 이용한 스레드 동기화

 

동기화 문제 해결하기

스레드 내에서 공유 자원을 사용하면 동기화 문제가 발생할 수 있다.

하나의 자원을 여러 스레드에서 접근하여 값을 변경시킬 때, 동시에 접근하면 의도하지 않은 결과가 나올 수 있다.

뮤텍스를 이용하면 공유 자원에 접근하는 스레드를 하나로 제한시킬 수 있기 때문에 동기화 문제가 해결될 수 있다.

 

int counter = 0;
std::mutex mtx;
std::thread threads[5];

for (int i = 0; i < 5; ++i) {
    threads[i] = std::thread([&counter, &mtx]() {
        mtx.lock();
        ++counter;
        mtx.unlock();
    });
}

for (auto& thread : threads) thread.join();

 

주의할 점으로는 뮤텍스를 lock으로 잠궜다면 사용한 이후 반드시 unlock으로 풀어주어야 한다. 그렇지 않으면 뮤텍스가 반환되지 않아서 다른 스레드들은 뮤텍스를 영원히 기다리게 된다.

 

 

자동으로 잠금 해제하기

만약 뮤텍스의 unlock을 잊었거나 예외 발생 등으로 잠금이 해제되지 못하고 유효범위를 빠져나온다면 문제가 발생한다.

이 문제는 뮤텍스의 잠금과 해제를 자동으로 해주는 자원 관리 클래스 std::lock_guard<mutex>를 사용하면 된다.

 

...
threads[i] = thread([&counter, &mtx]) {
    for (int i = 0; i < 10000; ++i)
    { // lock_guard의 유효 범위
        std::lock_guard<std::mutex> guard(mtx);
        ++counter;
    } // lock_guard의 유효 범위
}

 

선언 및 초기화 될 때, 생성자에서 뮤텍스를 잠그고 소멸자에서 잠금을 해제하기 때문에 실수로 잠금 해제를 하지 않거나 예외가 발생해도 유효범위를 빠져나갈 때 소멸자가 호출되어 자동으로 잠금이 해제된다.

 

 

recursive_mutex로 데드락 방지하기

하나의 뮤텍스로 여러 개의 lock_guard를 사용하면 데드락이 발생한다.

 

struct Math {
public:
    void multiplexer(int i) { std::lock_guard<mutex> lock(mtx); ... }
    void divisor(int i) { std::lock_guard<mutex> lock(mtx); ... }
    void runAll(int a) {
        std::lock_guard<std::mutex> lock(mtx);
        multiplexer(a); // 안에서 lock_guard가 또 사용된다
        divisor(a);
    }
private:
    std::mutex mtx;
};

 

두 곳의 함수에서 동일한 뮤텍스를 사용하여 lock_guard 객체를 생성하기 때문에 데드락에 빠진다.

이 때, lock_guard의 템플릿 인자로 mutex 대신 recursive_mutex를 사용하면 동일한 뮤텍스로 한 번 이상의 잠금 처리를 하면서 데드락도 방지할 수 있다.

컴파일 타임에 타입 선택하기

 

template<typename T>
struct datatype {
    using type = T;
};

using t = typename datatype<int>::type; // 컴파일 타임에 데이터 타입 선택
t myVar = 123;

 

템플릿 매개변수로 받은 타입을 저장하고 해당 타입 사용 시, 재정의해서 사용한다.

 

template<bool predicate, typename TrueType, typename FalseType>
struct IfElseDataType {};

template<typename TrueType, typename FalseType>
struct IfElseDataType<true, typename TrueType, typename FalseType> { // 템플릿 부분 특수화
    using type = TrueType;
};

template<typename TrueType, typename FalseType>
struct IfElseDataType<true, typename TrueType, typename FalseType> { // 템플릿 부분 특수화
    using type = FalseType;
}

IfElseDataType<SHRT_MAX = 2147583647, short, int>::type myVar; // false이므로 int 선택

 

조건식에 따라 데이터 타입을 선택할 수도 있다.

 

 

 

 

템플릿 메타프로그래밍으로 흐름 제어

 

조건에 따라 다음 작업 결정

void trueStatement() { std::cout << "true statement is run." << '\n'; }
void falseStatement() { std::cout << "true statement is run." << '\n'; }

if (2 + 3 == 5) trueStatement();
else falseStatement();

 

보통 조건을 처리할때는 if-else 구문을 사용해서 위와 같이 처리한다.

 

template<bool predicate>
class IfElse {};

template<>
class IfElse<true> { // 템플릿 특수화
public:
    static inline void func() { trueStatement(); }
};

template<>
class IfElse<false> { // 템플릿 특수화
public:
    static inline void func() { trueStatement(); }
};

IfElse<(2 + 3 == 5)>::func();

 

템플릿 특수화를 사용하면 템플릿 매개변수에 조건식을 넣어서 원하는 조건을 정확하게 처리할 수 있다.

 

 

구문 선택

일치하는 구문을 선택하는 switch문 역시 템플릿 특수화로 바꿔서 구현할 수 있다.

 

int Square(int a) { return a * a; }

template<int val> // switch-default
class SwitchTemplate {
public:
    static inline int func() { return Square(0); }
};

template<>
class SwitchTemplate<1> { // switch-case 1
public:
    static inline int func() { return Square(1); }
};

template<>
class SwitchTemplate<2> { // switch-case 2
public:
    static inline int func() { return Square(2); }
};


int output = SwitchTemplate<2>::func();

 

 

루프에 적용하기

재귀로 구현하고 루프를 빠져나올 조건이 될 특수화 템플릿이 하나 이상 반드시 존재해야한다.

 

void printNumber(int i) { std::cout << i << '\t'; }

template<int limit>
class DoWhile {
public:
    static inline void func() {
        PrintNumber(limit);
        DoWhile<run == true ? (limit - 1) : 0>::func();
    }
private:
    static const bool run = (limit - 1) != 0;
};

template<>
class DoWhile<0> { // 템플릿 특수화. 루프 탈출 조건
public:
    static inline void func() {} // 아무것도 하지 않는다
};


DoWhile<100>::func();

 

 

 

 

컴파일 타임에 코드 실행

 

컴파일 타임 상수 얻기

template<int num>
struct fibonacci {
    static const int value = 
        fibonacci<num - 1>::value + fibonacci<num - 2>::value; // 상수 계산
};

template<>
struct fibonacci<1> { // 템플릿 특수화
    static const int value = 1;
};

template<>
struct fibonacci<0> { // 템플릿 특수화
    static const int value = 0;
};


std::cout << fibonacci<25>::value << '\n';

 

enum이나 static은 컴파일 타임에 만들어지기 때문에 문제없이 상수 연산이 가능하다.

 

 

컴파일 타임에 클래스 생성

 

template<int lastNumber, int secondLastNumber>
class IsPrime {
public:
    static const bool primeNumber = (
        (lastNumber % secondLastNumber) &&
        IsPrime<lastNumber, secondLastNumber - 1>::primeNumber);
};

template<int number>
class IsPrime<number, 1> { // 템플릿 부분 특수화
public:
    static const bool primeNumber = 1;
};

template<int number>
class PrimeNumberPrinter {
public:
    void func() { // 객체로 만들어지기 때문에 static이 아니어도 된다
        printer.func(); // number부터 1까지 이동
        if (primeNumber) std::cout << number << '\t';
    }
private:
    PrimeNumberPrinter<number - 1> printer;
    static const bool primeNumber = IsPrime<number, number -1>::primeNumber;
};

template<>
class PrimeNumberPrinter<1> { // 템플릿 특수화
public:
    void func() {}
private:
    static const bool primeNumber = false;
};


PrimeNumberPrinter<500> printer;
printer.func();

 

클래스라고해서 상수와 다른건 없다. 결국 '컴파일 타임' 에 생성되어야 하는 것은 똑같기 때문이다.

 

타입이 다른 객체가 컴파일 타임에 500개 생성되기 때문에(=코드 500개 생성) 컴파일이 오래 걸린다.

디스어셈블리를 확인해보면 실제로 코드가 500개 생성되어 메모리에 잡히는 것을 확인할 수 있다.

덧붙여서 위와 같은 코드는 꼬리 재귀가 아니기 때문에 템플릿 매개변수의 값이 크다면 콜스택이 부족해진다. 최적화가 잘 된 코드는 아니고 예제에만 충실한 코드이다.

 

 

 

 

메타프로그래밍의 장점과 단점

 

장점

◾ 템플릿 메타프로그래밍은 불변성이 있어서 기존 타입을 수정할 수 없으므로 부작용도 없다.

◾ 메타프로그래밍으로 구현하면 가독성이 더 좋아진다.

◾ 코드 반복을 줄일 수 있다.

◾ 컴파일러에 따라 생성된 코드에 인라인을 적용시켜서 성능을 높일 수 있다.

 

단점

◾ 구문이 꽤 복잡해질 수 있다.

◾ 컴파일 시간에 코드를 실행하기 때문에 컴파일 시간이 더 오래 걸린다.

◾ 디버깅이 어렵다. 컴파일에 코드가 생성되므로 디버거가 런타임에 코드를 찾기가 어렵다.

메타프로그래밍 소개

 

간단하게 설명하면 '코드를 사용해서 코드를 생성하는 기술' 이다.

C++ 템플릿 메타프로그래밍(TMP)은 튜링 완전하다.

재귀를 많이 사용하고 불변 변수를 사용한다.

 

 

매크로를 사용한 코드 전처리

#define MAX(a,b) (((a) > (b)) ? (a) : (b))

C언어에서 사용되던 그 매크로 맞다. 매크로는 전처리기에 의해 컴파일 타임에 실행된다.

위의 코드처럼 매개변수가 있는 C 매크로는 메타함수라고 부르며 메타프로그래밍의 한 예다.

 

 

표준 라이브러리의 템플릿 메타프로그래밍 자세히 보기

컴파일러는 템플릿으로 인스턴스를 생성할 때 코드를 생성한다.

 

 

 

 

템플릿 메타프로그래밍

 

템플릿 메타프로그래밍에서 타입 다루기

매크로는 매개변수가 호환되는 타입인지 확인할 수 없는 반면, 템플릿은 C++ 타입 시스템에 통합되어 있기 때문에 타입 확인이 가능하다.

템플릿 메타프로그래밍을 사용하는 더 좋은 방법은 필요한 타입의 매개변수에 대해서만 동작하도록 코드를 작성하는 것이다.

템플릿 메타프로그래밍은 가변 변수가 없다. 즉, 초기화된 변수의 값을 바꿀 수 없다는 의미이다.

대신 변수에서 필요한 것은 접근할 수 있는 이름이고 typedef(또는 using)로 재정의한 이름을 주로 사용한다.

 

 

템플릿 메타프로그래밍에서 값 처리

template<int A, int B>
struct Multiplexer {
    static const int result = A * B;
    /* enum { result = A * B } */
    /* 이런 방법도 있다 */
};

int i = Multiplexer<2, 3>::result; // 6

 

 

 

템플릿 메타프로그래밍에서 조건 처리

template<typename A, typename B>
struct CheckingType {
    static const int result = 0;
};

template<typename X> // 템플릿 특수화
struct CheckingType<X, X> {
    static const int result = 1;
};


if (CheckingType<UnknownType, int>::result) {
    /* UnknownType이 int면 result가 1이므로 여기 실행 */
}
else {
    /* UnknownType이 int가 아니면 result가 0이므로 여기 실행 */
}

 

 

템플릿 메타프로그래밍에서 재귀 처리

template<int I>
struct factorial {
    static const int value = I * factorial<I - 1>::value;
};

template<>
struct factorial<0> { // 템플릿 특수화
    static const int value = 1;
};

int fact10 = factorial<10>::value;

 

재귀함수에서의 종료 조건은 템플릿 특수화를 통해서 구현할 수 있다.

또한 템플릿 매개변수는 반드시 상수여야만 한다.

당연한 이야기겠지만 컴파일 타임에 코드가 생성되기 때문에 변수가 대입될 수 없다.

표현식 평가

 

즉시 평가

대부분의 명령형 언어에서 사용되고 코드를 바로 실행한다.

 

int i = (x + (y * z));

 

직관적이다. y * z를 먼저 계산하고 그 결과를 x에 더한다.

 

int OuterFormula(int x, int yz) { return x + yz; }
int InnerFormula(int y, int z) { return y * z; }

int result = OuterFormula(x, InnerFormula(y, z));

 

함수로 작성하면 위와 같다. OuterFormula 호출 시, InnerFormula가 호출되어 결과값을 반환하여 인자로 넘겨준다.

 

 

지연 평가

int OuterFormulaNonStrict(int x, int y, int z, std::function<int(int, int)> yzFunc)
{
    return x + yzFunc(y, z);
}
int InnerFormula(int y, int z) { return y * z; }

int result = OuterFormulaNonStrict(x, y, z, InnerFormula);

 

InnerFormula 함수를 함수 객체로 넘겨서 코드의 실행 순서를 바꾼다. + 연산자를 먼저 처리하고 (y * z)는 나중에(지연) 처리된다.

인자로 넘겨진 함수 객체는 호출되기 전까지 실행을 지연하므로 결과적으로 실행 순서가 변경된다.

 

코드의 실행 순서

 

 

 

 

지연 평가에 필요한 기술

 

처리 흐름 늦추기

template<class T>
class Delay {
public:
    Delay(std::function<T()> func) : m_func(func) {}
    T fetch() { return m_func(); }
private:
    std::function<T()> m_func;
};

 

생성자의 매개변수로 함수를 받는다. 해당 함수는 fetch가 호출되지 않는 한 실행되지 않는다. (인스턴스 생성X)

 

Delay<int> multiply([a, b]() { ... });
Delay<int> division([a, b]() { ... });

int c = multiply.fetch();
int d = division.fetch();

 

multiply와 division 인스턴스가 생성될 때, 생성자에 넘겨준 람다 표현식은 인스턴스 생성 시점에 같이 인스턴스화 되지 않고 명시적인 호출 시점에 인스턴스화 되면서 호출이 이루어진다.

 

 

메모이제이션으로 값 캐싱

함수 호출 결과를 저장해 두었다가 동일한 입력이 발생하면 저장된 결과를 반환해준다.

 

template<class T>
class Memoization
{
public:
    Memoization(std::function<T()> func)
        : m_func(func), m_subRoutine(&forceSubroutine), m_recordedFunc(T()) {}
    T fetch() { return m_subRoutine(this); }

private:
    std::function<T const& (Memoization*)> m_subRoutine; // fetch에 의해 호출되는 함수 객체
    std::function<T()> m_func; // 연산이 담길 함수 객체
    mutable T m_recordedFunc; // 값 저장 변수

    static T const& forceSubroutine(Memoization* d) { return d->doRecording(); }
    static T const& fetchSubroutine(Memoization* d) { return d->fetchRecording(); }

    T const& fetchRecording() { return m_recordedFunc; } // 저장된 값 반환
    T const& doRecording() {
        m_recordedFunc = m_func(); // 연산 값 저장
        // forceSubroutine=>doRecording으로 호출되던것을 forceSubroutine=>fetchRecording으로 변경
        // doRecording은 이후 호출되지 않는다.
        m_subRoutine = &fetchSubroutine;
        return fetchRecording();
    }
};

int a = 10;
int b = 5;
int multiplexer = 0;
Memoization<int> multiply_impure([&]() { return multiplexer * a * b; } );

for (int i = 0; i < 5; ++i) {
    ++multiplexer;
    std::cout << multiply_impure.fetch() << '\n';
}

 

외부 값을 참조 캡처하여 그 연산 결과를 반환하는 함수를 생성자에 넘겨준다.

반복문 내에서 multiplexer의 값이 변하기 때문에 본래라면 fetch를 호출할 때마다 다른 값이 반환되어야 한다.

하지만 fetch가 최초로 호출 될 때만 연산 및 그 결과값을 객체에 저장하고, 그 뒤에 fetch에서 호출하는 함수가 바뀌기 때문에 이후 호출되는 fetch는 저장된 값만을 동일하게 반환받는다.

 

메모이제이션을 사용할 때, 비순수 함수는 부작용이 발생할 수 있으므로 반드시 배제시켜야 한다.

결과값을 재사용 하기 때문에 최적화가 이루어진다.

 

덧붙여서 메모이제이션 수행 시 데이터가 한번 변하기 때문에 불변 객체가 아니라고 생각할 수도 있지만 외부에서 바라봤을때는 불변으로 보이기 때문에 불변 객체로 볼 수 있다.

 

 

메모이제이션으로 코드 최적화

동일한 인수를 가지고 같은 함수가 여러번 호출되었을 때, 만약 함수 내의 연산량이 많고 복잡하다면 그 연산들을 항상 수행하는 것은 성능적인 면에서 비효율적이다.

하지만 위에서 작성한 코드처럼 결과값을 캐싱해서 가지고 있는다면 성능의 최적화를 이룰 수 있다.

꼬리 재귀 이해하기

 

일반적인 재귀 함수와 다르게 꼬리 재귀는 함수 끝에서 자기 자신을 호출하는 것 외에 더 해야 할 일이 없다.

 

int factorialTail(int n, int i)
{
    if (n == 0) return i;
    return factorialTail(n - 1, n * i);
}

int factorial(int n)
{
    return factorialTail(n, 1);
}

 

기존 재귀함수에서 사용되던 n * factorial(n - 1)은 함수의 호출이 끝나도 연산이 남아있기 때문에 꼬리재귀가 아니다.

꼬리재귀로 구현하는 경우 콜스택이 소비되지 않는다. (단, 컴파일러의 최적화 옵션이 켜져있어야 한다)

 

 

 

 

함수형, 절차형, 백트래킹 재귀

 

표준 용어는 아니지만 함수형 재귀, 절차형 재귀, 백트래킹 재귀로 구분한다.

 

함수형 재귀

재귀적으로 문제를 풀면서 각 결과 값을 합치고 그 값을 반환한다.

앞서 다뤘던 팩토리얼, 피보나치가 이에 해당한다.

 

 

절차형 재귀

함수 내부에서 필요한 작업을 바로 처리하여 반환값이 없다.

 

void doPermute(const std::string& chosen, const std::string& remaining)
{
    if (remaining == "") std::cout << chosen << '\n';
    else {
        for (uint32_t u = 0; u < remaining.length(); ++u) {
            doPermute(chosen + remaining[u],
                remaining.substr(0, u) + remaining.substr(u + 1));
        }
    }
}

void permute(const std::string& s)
{
    doPermute("", s);
}

 

순열을 출력하는 함수의 경우 별도의 값 반환 없이 함수 내부에서 작업을 처리할 수 있다.

 

 

백트래킹 재귀

마치 ctrl+z(실행취소) 한것처럼 스택을 되감아서 돌아갈 수 있다.

미로찾기나 순열 등에 사용할 수 있다. DFS와 개념이 유사하다.

+ Recent posts