유전 알고리즘을 이용한 함수 최적화

 

뜬금없이 먼가 떠올랐을때 해봐야 직성이 풀리는 못된 버릇이 있다. 세살 버릇 여든 간다. 오늘은 코로나 뉴스를 보다가, 소시적 원서를 질러 독학했던 유전 알고리즘(Genetic Algorithm; GA)이 문득 떠올랐다. 당시에도 여러가지 해보고 싶은게 많았지만 본류 주제가 아니었기에 접고 있었다. 그 중 하나가 실수(real number)를 쉽게 다루는 방법에 대한 것이다. 다변수 목적 함수(multi-variable objective function)의 최적화 문제를 풀기 위한 GA가 단변수 목적 함수(uni-variable objective function)에 대한 GA보다 오히려 단순하다. 다변수 함수에서는 변수 각각을 유전자(gene)로 간주하면 되지만, 단변수 함수에서는 유전자를 어떻게 encoding 할 지 고민해야 한다. 논문들을 보면 실수를 string으로 encoding해서 유전자로 사용했었다. 하지만, 당시에도 컴퓨터가 기본적으로 모든 숫자들을 binary로 encoding해서 사용하고 있는데 또 다시 encoding하는 것이 굉장히 불합리하다고 생각했다. 흠, 그래서 이 문제도 해결하고 보다 일반적으로 함수 최적화 문제를 풀 수 있는 GA를 만들어 보기로 했다.

GA는 매우 단순하면서도 효율적인 최적화 알고리즘이다. TSP(Travelling Salesman Problem: 영업사원이 n개의 도시를 순차적으로 방문 후 돌아오는 최단 경로 문제로 n! 갯수의 거리계산이 필요)와 같은 NP-hard한 조합 최적화 문제도 빠른 시간 안에 준 최적(suboptimal) 경로 조합을 찾아낼 수 있어서 많이 활용되기 시작했다. GA는 구현하기도 쉬워서 장난감으로 갖고 놀기에 좋은데, 장난감 치고는 더 대단한 일을 할 수 있는 놈이다. 목적 함수와 주요 독립 변수만 알고 있다면 대부분의 경우 전역 최적값(global optimum)에 근접한 해를 구할 수 있기 때문이다. 목적 함수에 대한 제약 조건(constraints)들이 있다면 더더욱 정확한 최적값을 얻을 수 있다. 이것은 과거의 전통적인 최적화 기법들과는 상반되는 것들이다. 즉, 함수의 연속성, 미분 가능성, 단극성(unimodality) 등 전통적인 최적화 기법들이 요구하는 제약사항들을 GA가 모두 극복할 수 있기 때문이다. 가령, 인공신경망을 학습시키려면 cost/loss function에 대한 미분 가능 여부가 걸림돌이 된다. GA 관점에서는 복잡한 인공신경망 목적 함수를 최소화하는 weights 값들을 구하는 문제로 귀결된다. 더구나 인공신경망에서 항상 문제가 되는 local minima에 대한 문제도 GA가 해결해 줄 수 있다. 사실, 이 부분도 소시적에 시도해 보고 싶었던 것 중의 하나였다. 인공신경망을 GA로 학습시키는 것 말이다. 혹시나 해서 구글링해 보니, 최근까지도 연구가 진행되고 있다. Reinforcement Learning에서도 학습 시키기 위해서 미분 가능하지 않은 목적 함수들을 채용할 수 있다는 점에서 매우 고무적이다. 인공신경망을 GA로 학습시킬 수 있다면 Deep Learning에도 굉장히 큰 변화를 가져올 것이다. 학습 시간을 줄이는 것은 물론이고 다양한 cost function을 사용할 수 있을 것이기 때문이다. 또한, real-time dynamic learning까지 가능할 수도 있다.

사실, 실생활에서 단변수 목적 함수를 사용할 일은 거의 없다. 흔히 사용되는 1차(1st order 또는 linear) 최소 제곱(자승)법(Least Squares Method/Regression)도 2변수 목적함수를 최적화하는 문제가 된다. 편미분을 이용해서 주어진 데이터를 가지고 최적의 직선 방정식(y = ax + b)을 구할 수 있다. 가령, 날짜별 코로나 신규 확진자 추이 데이터를 가장 잘 반영한 직선 방정식을 전통적인 최적화 기법으로 쉽게 구할 수 있다는 야그다. 하지만, 이 직선으로 내일 신규 확진자가 몇명일지 추정하기는 쉽지 않을 것이다. 시간별 확진자 수는 비선형적으로 증가하기 때문이다. 즉, 고차(higher order/non-linear) 목적 함수에 대한 최적화 문제로 귀결된다. 목적 함수가 비선형이 되는 순간 전통적인 최적화 기법들은 많은 제약이 뒤따르게 된다. 하지만, 단변수 목적 함수는 GA를 이해하고 알고리즘 자체를 개선하는데 매우 도움이 되기 때문에 단변수 함수 최적화에 GA를 사용하는 것 자체도 의미가 있다. 우리가 함수 그래프를 그려 볼 수 있는 것은 기껏해야 독립 변수가 2개까지인 경우이다. 독립 변수가 2개이면 3차원 그래프를 보아야 한다. 3차원 그래프도 유용하지만 2차원 그래프를 보면 훨씬 쉽게 함수를 이해할 수 있다. 이것이 단변수 함수 최적화가 갖는 의미다.

Genetic Algorithm(GA)

먼저, 알고리즘 자체를 간단히 살펴 보자. GA는 찰스 다윈의 자연선택설을 모방하여, random 염색체 군에서 선택(selection) - 교합(crossover) - 돌연변이(mutation)를 통해 새로운 세대의 염색체 군을 만드는 과정을 반복함으로써 세대가 지날수록 우량 염색체만 살아 남도록 하는 알고리즘이다. 자연의 진화 방식에 내재된 최적화 기법을 모사한 진화적 알고리즘(evolutionary algorithm) 중 하나이다. 이 때문에 GA를 흔히 meta-heuristic(반 경험적) 알고리즘이라 한다. 인공신경망과 유사하게 수학적으로 해석하기도 쉽지 않고 그렇다고 경험적으로 증명되었다고 치부해 버릴 수도 없다는 의미이다. 실제 GA 구현 방법은 차이가 날 수 있지만 원리는 동일하다. 아래는 GA의 대략적인 순서다. 

1. 유전자들(genes)을 염색체(chromosome)로 encoding

2. random 염색체들로 population 생성 및 fitness(우량도/적합도; 목적 함수 계산 값) 계산

3. fitness가 높은 순(또는 cost가 낮은 순)으로 염색체 정렬

4. 우량한 염색체들을 선택 교배(mate)시켜서 새로운 세대(generation) 생성

   4-1. elite 염색체 일부 복제하여 신세대 생성

   4-2. 상위 fitness 염색체들 간 random 교합(crossover) 후 신세대 생성 및 fitness 계산

   4-3. 돌연변이(mutation)로 신세대 생성 및 fitness 계산

5. 3 ~ 4의 과정을 사전에 정한 최대 세대 수 또는 종료 조건 만족시까지 반복

참고로, 대부분의 최적화 문제들은 cost를 최소화하는 것이기 때문에 GA의 fitness를 cost로 전환하여 사용하는 것이 좋다. fitness를 최대화하는 것은 cost를 최소화하는 것과 같다. 물론 목적 함수에 -1을 곱해서 사용해도 된다. 부가적으로 GA의 용어들을 최적화 용어로 대치하자면, 유전자는 목적 함수에 영향을 주는 요인이다. 다변수 함수라면 독립변수 각각에 해당된다. 염색체는 유전자들의 결합체이다. 교배시 필요한 하나의 개체이다. 다변수 함수에서는 최적 해의 후보 값 vector가 된다. 이 독립변수 vector 조합으로 목적 함수에 의해 fitness 값을 계산할 수 있게 된다.

GA에서는 난수(random number)들이 중요한 역할을 한다. 초기 염색체 population이 GA가 최적 해를 찾는데 큰 영향을 준다. 최적해의 후보를 탐색하는 관점에서 보면 가능한 모든 범위에서 균일한 난수가 생성되는게 좋다. 이 들이 대표 선수가 되어 좋은 유전자를 후대에 물려주게 된다. 하지만, GA 자체는 빠른 알고리즘이기 때문에 여러 번 돌려 보는게 더 나을 수도 있다. GA의 가장 큰 단점은 알고리즘 종료 조건을 설정하기 어렵다는 것이다. 처음엔 모두 다른 염색체들로 시작했는데 세대가 늘어날수록 우량 염색체가 다수를 차지하게 된다. 수렴하다가 더 좋은 값으로 바뀔 수도 있기 때문에 세대간 목적함수 값을 비교하기 어렵다. 목적함수 평균값에 대한 오차나 우량염색체 비율 등이 종료조건 후보가 될 수는 있지만 실제 돌려 보면 최대 세대수를 정해 놓고 돌리는게 더 나을 경우가 많다. 이것은 돌연변이를 사용해야 하기 때문에 발생하는 문제이다. 다른 최적화 알고리즘들과 마찬가지로 GA에 영향을 주는 매개 변수들이 있다. population 염색체 개체 수, crossover 확률, mutation 확률, 최대 세대 수, 탐색 구간 같은 것들이다. 좋은 방법은 처음엔 부정확하지만 빠르게 GA를 한번 돌려서 suboptimal 해를 구하고 나서 탐색 구간을 좁혀준 후 GA를 한번 더 돌리면 매우 정확한 값을 얻을 수 있다.

GA에서 실수형(real-number type) 단변수 및 다변수 사용

GA의 단변수는 64bit 실수를 사용하면 되므로 c++에서는 double type을 사용하면 된다. 앞서 얘기했듯이 컴퓨터는 이미 실수를 binary로 encoding해서 사용하고 있다. 우리는 이 놈이 염색체라고 보고 유전자들을 어떻게 선택 - 교합 - 돌연변이 시킬지를 알아내면 된다. 64bit encoding된 실수의 binary 형식을 알기 위해 Wikipedia를 참조할 필요가 있다.

아래는 교배(mate)함수를 구현한 것이다. size가 1일때가 Wikipedia를 참조해서 만든 단변수일 때 교배 방법이고 다변수에 대해서도 일관된 logic을 적용하였다. 너무나 간단한데 첨엔 이게 잘 돌아갈까 스스로 의심도 했지만 실제 GA를 돌려보니 단변수 함수의 전역 최적 해의 근사값을 너무도 잘 구해 내더라. 수치 해(numerical solution)로써 정확도 면에서도 손색이 없을 정도다. 참고로, Real64 type은 double과 uint64_t의 union type이다. 즉, 유전자 조작은 bit 연산으로 수행하고 fitness(목적 함수) 계산시에는 걍 double 값을 사용하겠다는 것이다. 좀 관심이 있는 사람들은 아래의 logic에서 몇가지 특이 사항을 발견할 수도 있을 것이다. 다변수의 경우엔 변수 갯수만큼 실수형 배열이나 아래와 같이 vector를 사용하면 된다.

  Chromosome mate(const Chromosome& another) {
    if(size == 1) {
      Real64 chro;
      for(int i = 52; i < 64; ++i) {
        float p = random_int(0, 100) / 100.0;
        if(p < (1 - pMutation) / 2) chro.i |= chromosome.i & (1 << i);
        else if(p < 1 - pMutation) chro.i |= another.chromosome.i & ( 1 << i);
        else chro.d = mutate();
        //else chro.i |= (chromosome.i ^ (1 << i)) & (1 << i);
      }
      //unsigned nan = (chro.i >> 52);
      //if(nan == 0x7ff || nan == 0xfff) chro.i ^= (1ul << 52); // NaN or INF
      return Chromosome(chro);
    }
    else {
      std::vector<double> gv;
      for(int i = 0; i < size; ++i) {
        float p = random_int(0, 100) / 100.0;
        if(p < (1 - pMutation) / 2) gv.push_back(xv[i]);
        else if(p < 1 - pMutation) gv.push_back(another.xv[i]);
        else gv.push_back(mutated_gene(i));
      }
      return Chromosome(gv);
    }
  }

전체 알고리즘을 구현하는 것은 별로 어렵지 않기 때문에 관심이 있는 사람들은 직접 구현해 보길 권한다. 흠, 나는 자주 바퀴를 다시 발명하기를 권하는데 일반적으로는 권장하지 않는 가이드이다. 하지만 고집하는 이유는, 자신이 만든 것에 사람들은 애착을 느끼게 되고 이것이 삶이나 행동에 큰 변화를 줄 수 있다는 믿음 때문이다. 더구나 직접 만들어 보면 남의 것을 사용하던 때와 굉장히 다르다는 것을 깨닫게 된다. 기존의 바퀴에 개선의 여지가 여전히 많다는 것도 자연스럽게 깨칠 수 있다. 이런 것은 누가 가르쳐 줄 수도 없는 것들이다. 

GA 테스트 결과

아래 그래프는 단변수 목적 함수인 y = (x^4 + 2*x^3 - 3*x^2 + 13)^2 - 5를 구글링해서 Firefox로 capture 한 것이다. 흠, 우연히 그래프를 우클릭했는데 capture 기능을 발견해서 당장 써먹는다.

이 함수의 전역 최소값은 아래 그래프에서 GA가 72번째 세대에서 수렴한 [x', Cost'] = (-2.188332, -4.63122) 값과 거의 일치함을 알 수 있다.

이 함수말고도 주기 함수나 불연속 함수 등 몇가지 단변수 함수의 전역 최소값 구하기를 GA로 돌려 보았는데 너무도 잘 찾을뿐 아니라 값들도 상당히 정확하다. 주기 함수의 경우 범위에 대한 constraint를 주면 더 정확한 x 값을 찾아낸다.

독립변수가 2개인 경우까지는 그래프 구글링을 통해 대략 최적값이 맞는지 확인할 수 있다. 아래는 Rosenbrock 함수로 알려진 z = 100*(x^2-y)^2 + (1-y)^2 함수를 구글링한 것이다. 전역 최소값 [x', y', z'] = (1, 1, 0) 또는 (-1, 1, 0)이다. 이 놈은 local minima에 빠져서 global 최소값을 찾기 어려운 놈으로 테스트하기 좋은 2변수 함수이다. 구글링해보면 이놈을 어떻게 보는게 좋을지도 고민하게 되는 상당히 난감한 놈이다. 이 놈을 GA로 돌려 보면 초기 난수 분포에 따라 최종 결과가 달라지긴 하지만 전역 최소값에 근사한 값들을 어려움없이 잘 찾아낸다.

간단한 데이터를 가지고 GA로 linear regression을 해 보니 대체로 잘 된다. 변수 범위를 지정하면 편미분으로 구한 정확한 값과 거의 일치하더라. 구글링해 보니 고차(higer-order) regression 문제도 GA로 해결한 사례들이 꽤 있더라.

3변수 이상 다변수 목적함수인 경우에도 GA를 많이들 써먹고 있다. GA 테스트는 할 수 있지만 결과가 맞는지는 남들이 구한 최적 값과 비교해야 하는 난감함이 따른다. 구글링해서 한가지 돌려 봤는데 잘 맞더라. 흠, 아무튼 이제 Deep Learning에 GA를 테스트할 일이 남았는데 언제쯤 할지는... Deep Learning 분야는 상대적으로 학습이 잘됐는지 확인할 수 있는 방법들이 있어서 오히려 편할 수 있다. 

참고로, 3변수 이내에서는 population 크기를 1000으로 하고 1000세대까지 웬만한 PC에서 돌려도 거의 1분 내에 답을 찾을 것이다.

c++20 Coroutine 배우기

올해 말까지는 c++20 표준이 공표될거라 해서 Big 4라 불리는 놈 중 하나인 Coroutine에 대해 배워 보기로 했다. 이 놈에게 관심을 가진 이유는 비동기 처리를 쉽게 할 수 있어 보여서다. 이를 테면 Signal & Slots를 callback을 사용하지 않고 구현할 수도 있을까 하는 궁금증... 

결론적으로 모든 것을 대체할 수는 없다는 생각에 이르렀지만 활용 범위는 꽤 늘어날 듯 싶다. 당장 게임 같은 곳에서는 UI와 로직을 분리할 수 있어서 꽤나 유용할 듯 싶다. 이외에도 이벤트 처리, generator, lazy-evaluation 알고리즘, 네트워크 등의 비동기 I/O에 활용될 수 있다. Asio 네트워크 라이브러리에서는 10년 전부터 매크로를 이용해서 c++20의 코루틴 구현 방식인 stackless 코루틴을 사용해왔단다. 세상엔 대단한 넘들이 많다. c++20의 코루틴은 pointer를 처음 배우는 것만큼 배우기도 쉽지 않다. 뭐, 알고 나면 별거 아닌게 되지만...

코루틴에 대해 제대로 정리하려면 너무 길어지므로, 이 글은 간단한 예 하나 만들어 본 것을 정리하는데 그친다. c++20의 코루틴이 복잡한 이유는 컴파일러가 생성해 주는 일종의 coroutine framework에 맞추어서 코딩해야 하기 때문이다. 숨겨진 로직이 많다는 것이다. 나중에 cppcoro와 같은 라이브러리가 표준으로 채택되면 사용자들은 동작 방식보다는 활용 방법만 배우면 될 것이다.   

코루틴 이해

Coroutine은 원래 main 루틴이 아닌  모든 subroutine을 포함하는 개념이란다. 좁은 의미로는 진입 지점을 여러 개 가질 수 있는 함수가 코루틴이다. 기존 함수는 시작(by-call)과 끝(return)만 있는데, 중단(suspend)했다가 다시 재개(resume)할 수 있는 기능이 추가된 함수로 이해하면 된다. suspend/resume이 필요한 이유는 실행 흐름을 비동기(asynchronous) 방식으로 제어하기 위해서이다. 결국, 코루틴은 실행 흐름을 논리적으로 제어하기 위한 함수이다. 좀 깊이 들어 가면 선점형(pre-emptive) 스케쥴링과 협력적(cooperative) 스케쥴링에 의한 multi-tasking 개념을 이해해야 한다. Thread와는 독립적인 개념인데, 기본적으로는 하나의 thread로 멀티태스킹을 할수 있다고 보면 된다. 비동기 네트워크 서버가 단일 쓰레드로 다수의 클라이언트를 처리하는 것을 떠올리면 된다.

3가지 키워드인 co_await, co_yield, co_return 중 하나라도 사용된 함수는 코루틴이 된다. main() 함수는 코루틴이 아니므로 3가지 키워드를 직접 사용할 수 없다. 코루틴 framework은 Promise Interface, Awaitable Interface, Coroutine Handle의 3가지 API를 이해해야 한다.  앞의 두 인터페이스는 사용자가 작성해야 한다. Handle은 컴파일러 내장 함수이고 <coroutine> 표준헤더를 참고하면 된다. Promise Interface는 코루틴 객체 class 내에 정의하여 코루틴의 동작 방식을 제어한다. Awaitable Interface는 co_await 키워드가 어떻게 동작할 지 정의하기 위한 것이다.  Handle은 코루틴의 재개(resume)와 소멸(destroy), 현재 상태(done), 메모리상의 위치(address) 등에 대한 인터페이스이다. 3가지 키워드는 3가지 API를 적절하게 사용하기 위해 필요한 것이다.

코루틴 사용 예

class SimpleTask
{
public:
  struct promise_type;
  using coro_handle = coroutine_handle<promise_type>;
  struct promise_type {
    auto get_return_object() { return SimpleTask{coro_handle::from_promise(*this)}; }
    auto initial_suspend() { return suspend_never{}; }
    auto return_void() { return suspend_never{}; }
    auto final_suspend() { return suspend_always{}; }
    void unhandled_exception() { std::terminate(); }
  };

  SimpleTask(SimpleTask&& r) = default; // ensure copy elision
  ~SimpleTask() { if(m_handle) m_handle.destroy(); }
  bool resume() { if(!m_handle.done()) m_handle.resume(); return !m_handle.done(); }

private:
  explicit SimpleTask(coro_handle handle) : m_handle(handle) {}
  coro_handle m_handle;
};

// For AsyncTimer, the total time required for coro_simple() should be 3 seconds???
// If you think so, try to make it~!!!
SimpleTask coro_simple()
{
  std::cout << "Hello\n";
  co_await 3s;
  std::cout << "  after 3 sec ...\n";
  co_await 2s;
  std::cout << "  after 5 sec ...\n";
  co_await 1s;
  std::cout << "  after 6 sec ...\n";
  std::cout << "Coroutine~!\n";
}

int main()
{
  std::cout << "+++ Start\n";
  SimpleTask task = coro_simple();
  while(task.resume());
  std::cout << "--- End\n";
}

위의 소스에서 coro_simple() 함수에 co_await 키워드가 사용됐으므로 코루틴이다. 코루틴 반환 객체(간단히, 코루틴 객체)인 SimpleTask class내에 정의된 promise_type이 Promise Interface이다. 일반 함수와 달리 SimpleTask를 return하는 부분이 안보이지만 컴파일이 잘 된다. 실제로 SimpleTask객체를 promise.get_return_object() 인터페이스 함수를 통해 코루틴 최초 중단 시와 완료 시 내부에서 반환하기 때문이다. co_await 키워드만 사용했지만 함수 맨 끝에 co_return이 있는 것과 같다. 일반 void 함수 끝에 return을 사용하지 않아도 되는 것과 유사하다. 사실, SimpleTask class는 미래엔 라이브러리로 제공될 부분이다. 사용자는 그것들을 이용하는 방법만 알면 된다.

c++은 너무 유연해서 코루틴도 일반 함수처럼 동작할 수 있지만, 기본적으로 코루틴은 한 번 이상 중단/재개가 일어난다고 보면 된다.  코루틴이 중단 된다고 프로그램이 중단되는 것이 아니다. 중단하는 이유는 원하는 결과를 기다리기 위한 것이다. 코루틴이 비동기적이라고 하는 이유이다. 가령 위의 co_await 3s; 부분은 코루틴을 중단하고 3초간 기다리라는 것이다. 중단되면 실행흐름이 caller인 main() 함수로 돌아간다. while 문에서 코루틴을 재개해서 중단된 지점에서 다시 시작하도록 한다.

Promise Interface

Promise Interface는 promise_type을 통해 코루틴 실행시 중단 및 재개 지점에서 호출되는 interface method 들을 정의하고 코루틴 자체의 동작 방식을 제어한다. std::future<>와 함께 쓰이는 std::promise<>와 유사하지만 좀더 확장된 개념으로 보면 된다. promise_type 객체는 "약속"이라는 이름과 같이 비동기 함수 호출시 어떤 상태 값을 넘기기로 사전에 약속한 객체라고 이해하면 될듯하다.

즉, 컴파일러가 코루틴 키워드 하나를 만나면 Promise Interface를 통해 아래의 pseudo-code와 같은 전체 코루틴 골격을 만들어 준다. 사용자가 작성한 코루틴 코드 전후로 뭔가를 co_await 하고 있다.

코루틴 함수가 호출되면 필요시 Coroutine Frame을 heap에 allocation 하고 promise_type 객체를 생성하는 등 컴파일러가 해주는 일이 많은데 아래 소스의 링크를 참고하자. 참고로 Coroutine Handle은 Coroutine Frame에 대한 pointer이다. 아래의 로직에서 initial/final suspend() 함수 내에서 코루틴이 중단/재개 될 수 있다고 보면 된다.

// Psuedo-code for Coroutine
// - source: https://lewissbaker.github.io/2018/09/05/understanding-the-promise-type

{
  co_await promise.initial_suspend();  // 사용자 코드 실행 전 뭔가 기다린다.
  try
  {
    <body-statements>                  // 사용자 코드(coro_simple() body) 실행
  }
  catch (...)
  {
    promise.unhandled_exception();     // 예외 처리
  }
  
FinalSuspend:
  co_await promise.final_suspend();    // 사용자 코드 실행 후에도 뭔가 기다린다. 
}

Awaitable Interface

이제 Awaitable Interface도 마저 예를 통해 보자. 3가지 키워드 중 co_await는 overloading이 가능한 단항 연산자(unary operator)이다. 위의 코루틴 pseudo-code에서도 co_await가 뭔가 중요한 일을 하고 있다. Awaitable은 co_await 연산을 적용할 수 있는 c++20 Concept(특정 조건들을 충족하는) type이다. Awaiter type은 Awaitable type의 3가지 Interface 함수를 구현한 Concept type이다. 아래 소스에 3가지 함수가 나타나 있다. 이들은 코루틴이 중단 후 caller에게 돌아갈 지 아니면 코루틴을 재개(resume)할지 제어하기 위한 것이다.

참고로, 아래의 소스는 co_await 연산자 overloading을 통해 시간이 입력값인 경우 AsyncTimer로 동작하도록 하기 위한 것이다. 생각보다 AsyncTimer가 코루틴에서 제대로 동작하도록 만들기 어렵다는 것을 알았다. 그래도 나름 간단하게 사용할 수 있어서 편한 점도 있다. 보통은 코루틴 객체 class 내부에서 co_await 연산자를 오버로딩함으로써 해당 객체로 부터 Awaiter 객체를 얻어내면 되는데 시간은 코루틴 객체가 아니지만 co_await 할 수 있어야 하기 때문에 전역 co_await 연산자를 오버로딩한 것이다.

// Overloaded co_await operator for time duration - AsyncTimer. (e.g. co_await 3s;)
// Do you have a better way for AsyncTimer to be used along with coroutine?
// A thread for timer can be used, but if the coroutine is resumed all the left code resumed
//   before the timer expires - how to suspend again and return to the caller?
template <typename TR, typename TP>
inline auto operator co_await(const std::chrono::duration<TR, TP>& duration) noexcept
{
  struct TAwaiter {
    using TClock = std::chrono::high_resolution_clock;
    using TTime = decltype(TClock::now());
    std::chrono::duration<TR, TP> duration;
    TTime start;
    TAwaiter(const std::chrono::duration<TR, TP>& d) : duration(d), start(TClock::now()) {}
    bool await_ready() noexcept { return duration.count() < 1; } // for 0 or negative time
    auto await_suspend(coroutine_handle<>) noexcept {} // just suspend and return to caller
    auto await_resume() noexcept {                     // sleep for left time when resumed
      if(duration.count() < 1) return;
      auto te = std::chrono::duration_cast<std::chrono::microseconds>(TClock::now() - start);
      std::this_thread::sleep_for(duration - te);
    }
  };
  return TAwaiter{duration};
}

co_await <expr> 구문은 <expr>을 evaluation 한 후, Awaiter 객체를 얻어 아래의 pseudo-code에 보인 Awaitable Interface 로직에 따라 제어 흐름이 동작하도록 한다. 가령, 아래는 promise.initial_suspend()를 실행한 결과 값에 co_await 연산을 적용해서 Awaiter 객체를 얻은 후, 아래의 pusedo-code 로직에 따라 결과 값을 얻는다. 결과 값/type은 await_resume()이 반환하는 값/type이다.

co_await promise.initial_suspend(); 

앞의 SimpleTask class에서 이 함수는 suspend_never 객체를 return하고 있다. 이 놈은 suspend_always와 함께 <coroutine> 헤더에 정의된 가장 기본적인 Awaitable type이다. 아래의 pseudo-code 로직을 적용하면, 

• co_await suspend_never{};   => 코루틴을 중단시키지 않고 즉시 재개
• co_await suspend_always{}; => 코루틴을 중단시키고 caller에게 제어 흐름을 넘김

이라는 뜻이 된다.

마지막 키워드인 co_yield <expr>의 의미는 아래와 똑같다.

co_await promise.yield_value(<expr>);

yield_value(<expr>) 함수는 co_return <expr> 키워드가 사용하는  return_value(<expr>) 또는 return_void() 대신 사용해야 하는 Promise Interface 함수이다.

// Psuedo-code for "co_await <expr>;" statement.
// - source: https://blog.panicsoftware.com/co_awaiting-coroutines

Awaiter&& awaiter = get_awaiter(promise, <expr>);
if (!awaiter.await_ready()) {
  <suspend-coroutine>              // suspend 상태에서만 코루틴 resume() 및 destroy() 가능
  try { // for a <result type> of awaiter.await_suspend(coroutine_handle)
    if constexpr <void type> 
      awaiter.await_suspend(coroutine_handle);
    if constexpr <bool type> {
      bool await_suspend_result = awaiter.await_suspend(coroutine_handle);
      if(!await_suspend_result) goto <resume-point>;
    }
    if constexpr <coroutine_handle type> { // tail-call optimization 적용됨
      another_coro_handle = awaiter.await_suspend(coroutine_handle<promise_type> h);
      another_coro_handle.resume();
    }
    <return-to-caller-or-resumer>  // 여기에 닿지 않고 코루틴이 완료되면 handle이 자동 소멸됨
  } catch (...) {
    std::exception_ptr exception = std::current_exception();
    if(exception) std::rethrow_exception(exception);
  }
}

<resume-point> :
return awaiter.await_resume();     // co_await type을 여기서 결정

위의 로직을 컴파일러가 노래로 알려 주었다.

< 함께 기다려 (co_await something) > - c++20 컴파일러가 인간들에게.

무언가 함께 기다리는 것은              무언가 함께 기다리는 것은
그것을 핑계로                                 가슴이 아파도
잠깐 쉬게 하려는 것.                        홀로 보내야만 하는 것.

준비된 이에게는                              기약없이 떠나지만
선물 주어                                        언젠가는 함께
기꺼이 다시 시작하도록,                  기꺼이 다시 시작하도록,

아니면                                            시련은
잠시 그 자리에 멈춰 세워,                거세지만 내 의지로 맞서,

마음을 비우거나 진실한 이는            어둡고 거친 길에 지치고 외로워도  
사랑하는 이에 돌아 가도록,              잠시나마 쉴 수 있도록,
새 꿈을 가진 이엔                             끝없이 펼쳐진 갈래길을 헤매어도  
희망 찾아 떠나 가도록,                    가다 보면 만날 수 있도록,
거짓된 이도                                     또 다시는
선물 주어 다시 시작하도록.              그 누구도 기다리지 않도록.

c++ Type Erasure 활용

 

이전 글에서 만든 표준 c++ 기반의 Slot Delegate를 이용해서 예전에 만들었던 Signal 부분도 표준 c++로 바꾸려다 보니, 또 다른 종류의 Type Erasure를 사용하면 쉽게 해결되는 부분을 발견하였다. 그것은 Slot이 shared_ptr<>인 경우 Signal container에서 자동으로 life-cycle을 tracking 해서 dangling pointer를 없애주는 부분이다.

이 놈도 Delegate 만큼이나 흥미로운 놈이다. c++17의 std::any와 비슷하지만 사용법이 다르다. 옛날 옛적엔 서로 다른 type의 객체를 컨테이너에 가두고 뺑뺑이 돌리기 위해 void*를 사용했었는데, 이제는 이 놈을 사용하는게 좋겠다. 아래에 std::shared_ptr<>를 가지고 AnySharedPtr 라는 Type Erasure를 구현한 예를 보였다. 사용하기는 편하지만, 이 놈의 단점은 객체를 저장하기 위해 memory allocation이 필요하고 이에 따라 성능에도 악영향을 준다. 아무튼 Signal에서 shared_ptr<>가 reset 되거나 scope을 벗어나는 경우, p.get()과 p.use_count() 정보 만으로도 해당 Slot을 자동 제거해 줄 수 있다. 

이 놈이 재미있는 것은 Delegate 처럼 상속을 사용하지 않는다(내부에서만 사용함). std::function<> 류의 Delegate은 함수형의 any callables를 대신하기 위해 사용되는데 비해, 이 놈은 std::any와 같이 any 객체에 사용될 수 있다. 하지만, std::any와는 달리 std::any_cast<>를 사용할 필요가 없다. 돌려서 말하면, Delegate와 마찬가지로 type이 지워져서 객체 type을 정확히 알아야 하는 경우엔 사용할 수가 없다. 

또한, Visitor Pattern을 사용하지 않고도 공통 interface만 있으면 서로 다른 유형의 객체를 std::vector<>와 같은 컨테이너에 담아서 반복 작업을 돌릴 수 있다. 아래의 예를 보는게 이해가 빠를 것이다.

#include <memory>

// Type Erasure for any type of std::shared_ptr<>s.
//
// - typical usage: save any types to a container and iterate some common works.
//   std::vector<AnysharedPtr> shared_pointers;

class AnySharedPtr
{
  class Concept
  {
  public:
    auto clone() const { return std::unique_ptr<Concept>(clone_impl()); }

    // Interface methods for Any types. (e.g. std::shared_ptr<> here)
    // - the return type is limited to basic POD types: the original type is erased.
    virtual void* get() const = 0; // NB: the original pointer type is erased.
    virtual long use_count() const = 0;

  protected:
    // Virtual constructor idiom
    virtual Concept* clone_impl() const = 0; // virtual copy constructor - base return
  };

  template <typename TM>
  class Model : public Concept
  {
  public:
    Model(TM&& obj) : m_model(std::forward<TM>(obj)) {}

  protected:
    // Virtual constructor idiom
    Model* clone_impl() const override { return new Model(*this); } // covariant return

    // Interface methods for Any types. (e.g. std::shared_ptr<> here)
    void* get() const override { return m_model.get(); }
    long use_count() const override { return m_model.use_count(); }

  private:
    TM m_model;
  };

public:
  // The rule of five is applied to use std::unique_ptr<> as a member variable.
  AnySharedPtr() = default;
  AnySharedPtr(const AnySharedPtr& rhs) : m_concept(rhs.m_concept->clone()) {}
  // Non-const constructor is required here to prevent the perfect forwarding constuctor.
  AnySharedPtr(AnySharedPtr &rhs) : AnySharedPtr(static_cast<const AnySharedPtr&>(rhs)) {}
  AnySharedPtr(AnySharedPtr&&) = default;
  template <typename TM> // perfect forwarding constructor
  AnySharedPtr(TM&& obj) : m_concept(std::make_unique<Model<TM>>(std::forward<TM>(obj))) {}
  ~AnySharedPtr() = default;

  AnySharedPtr& operator=(const AnySharedPtr& rhs)
  { m_concept = rhs.m_concept->clone(); return *this; }
  AnySharedPtr& operator=(AnySharedPtr& rhs)
  { return operator=(static_cast<const AnySharedPtr&>(rhs)); }
  AnySharedPtr& operator=(AnySharedPtr&&) = default;
  template <typename TM> // perfect forwarding assignment operator
  AnySharedPtr& operator=(TM&& obj)
  { m_concept = std::make_unique<Model<TM>>(std::forward<TM>(obj)); return *this; }

  // Interface methods for Any types. (e.g. std::shared_ptr<> here)
  void* get() const { return m_concept->get(); }
  long use_count() const { return m_concept->use_count(); }

private:
  std::unique_ptr<Concept> m_concept; // storage for type erasure
};

int main()
{
  std::shared_ptr<int> si = std::make_shared<int>(10), si_copy1 = si, si_copy2 = si_copy1;
  std::shared_ptr<std::string> ss = std::make_shared<std::string>("hello"), ss_copy = ss;
  
  std::vector<AnySharedPtr> any_ptrs;
  any_ptrs.push_back(si); any_ptrs.push_back(ss);
  for(auto p : any_ptrs) { std::cout << "Ptr: " << p.get() << ", " << p.use_count() << '\n'; }
  
  return 0;
}

Slot - Delegate의 재 발명

Signals and Slots를 구현해 본지 2년이 됐는데 문득 아쉬웠던 부분 들이 떠올라서 심심삼아 바퀴를 다시 발명해 보기로 했다. Signals and Slots는 Multicast Delegate와 비슷한 개념이다. Delegate의 특별한 응용 분야라고 생각할 수도 있다. 그래서, 일단 Delegate 구현시 부족했던 부분을 다시 채워 보기로 했다.

이전 버전에서는 Slot이 독립적인 Delegate 역할을 하는데는 한계가 있었다. 가장 찜찜했던 부분은 역시나 표준 c++을 따르지 않는 것이었다. 문제는 표준 c++에서 멤버 함수의 pointer를 직접 저장할 수 있는 방법이 없다는 것이다. Template을 이용해서 멤버 함수를 컴파일러가 바인딩하도록 해주면 실행 속도도 빨라지고 문제가 해결되긴 하지만 Delegate 사용시 interface가 매우 불편하다. 궁극적으로 Qt의 Signals and Slots 스타일로 사용할 수 없다. 사실, reinterpret_cast<>나 union을 이용해서 type-punning(억지로 형 바꾸기)한 변수들을 사용하는 부분은 모두 표준 c++에 위배된다. 억지로 바꾸려다 형 한테 맞는다???

흠, 혹시나해서 구글링해 보니 그 간에도 수 많은 넘들이 자신 만의 Delegate을 발명하고 있더라. Delegate가 흥미로운 놈인건 사실이다. 특히나 c++을 배우고 있다면 한번 쯤 자신의 바퀴를 발명해 보기 바란다. c++ 언어 자체가 계속 버전업 되다 보니 새로운 방식으로 도전해 보는 이들도 있다. 이를 테면 c++20의 concept을 활용해 볼 수도 있겠다. 여기서는 너무 멀리는 가지 않고 c++17의 if constexpr와 std::invocable을 이용해서 코드를 단순화 시켰다. 

근본적인 문제를 해결했는데, c++ 표준에서 함수/멤버 함수 pointer는 void* 포인터로 저장할 수 없지만, object instance는 void* 포인터로 저장할 수 있다는 점을 이용한 것이다. void*는 객체를 저장하기 위한 포인터이기 때문에, 비객체 포인터를 void*에 강제 할당하는 것은 표준 c++에서 벗어난다. 여기를 보면 c++ 객체에 대해 올바르게 이해할 수 있다. 또, 억지로 형 바꾸기를 하면 안되는 이유도 알 수 있다.  즉, 함수/멤버 함수 포인터를 객체 class로 감싸주면 void*에 저장할 수 있게 된다.

void*에 데이터를 저장하게 되면 객체들의 type을 모두 잃어 버리게 되는데, template type deduction을 이용해서 type을 복원해 주어야 한다. 형을 지웠다가 다시 쓸 수 있게 하는 넘들을 Type Erasure(형 지우개)라 하더라. Delegate Pattern에서는 inheritance를 사용하는데 다중 상속시 발생하는 문제와  virtual table 참조에 의한 성능 문제 때문에 자신 만의 Delegate를 만드는 넘들이 생겨났다. 

이렇게 만들어진 Delegate는 실상 std::function<>을 다시 발명한 것이다. 원래 std::function<>이 표준 Delegate인 셈이다. 하지만, std::function<>은 상당히 무겁고 느린 편이다. 더구나 안전을 보장하기 위해 모든 Callable 객체를 복사해 두기 때문에, Callable 객체들을 비교해야 한다면 추가적인 성능 부담이 생길 수 밖에 없는 구조다. 여기를 보니까 std::function<>을 다시 발명하고자 할 때 고려해야 할 점들을 잘 정리했더라. lambda도 Delegate의 역할을 일정부분 수행할 수는 있지만 Signals & Slots를 포함한 다양한 분야에 적용하는데 한계가 있다.

결론적으로, 아래와 같이  Slot이라는 나만의 Delegate를 다시 만들었다. SBO(Small Buffer Optimization) 라든가 Placement new라든가 하는 소소한 기법들이 들어가 있다. 사용법은 std::function<>과 거의 동일하고, 멤버 함수의 경우 std::bind<>를 사용하지 않고도 바로 초기화해서 사용할 수 있다. 

재미삼아 만들긴 했지만 이전 버전과 비교해서 여러가지 감안해도 두배 이상 소스가 늘어났다. 표준을 따르는게 얼마나 고된 일인가? 그니까 표준을 잘 만들어라~!!!

// Slot (Delegate or Callback) C++ Implementation
//
// This program is copyright (c) 2020 by Umundu @ https://zapary.blogspot.com .
// It is distributed under the terms of the GNU LGPL version 3, as detailed in
// https://opensource.org/licenses/lgpl-3.0.html .
//
// There are so many c++ Delegate implementaions. -  What's the point in this Slot?
// => Make simple interface without losing performance while keeping c++ standard.
//
//  o Simple usage can be extended to Signals and Slots(Qt) style interface: e.g)
//    Slot<double(int)> s1, s2(&obj, &Derived::doWork), s3([&c](int i){ return c+i; }), s4;
//    s1 = lambda; s4 = free_function; double result = s3(100);
//  o Comparison of two Slots is based on the IDs that are created from the source objects.
//  o Can be used as a light weight version of std::function<>.
//
//  * Compiler requirements: c++17 - supporting c++11 could be handy by replacing two parts:
//    - std::is_invocable_r<> => can be replaced to std::is_convertible<> things.
//    - if constexpr()        => can be replaced by using the SNIFAE.

#include <functional>
#include <memory>

template <typename T> class Slot;
template <typename TR, typename... TAs>
class Slot<TR(TAs...)>
{
  static constexpr size_t BufferMaxSize = 32;
  using TypeID = size_t;
  using TypePF = TR(*)(TAs...);
  using TypeCallback = TR(*)(void*, TAs&&...);
  using TypeCleaner = void(*)(void*);
  using TypeOPF = struct { TypePF pf; };

  // All the callables should be std::is_invocable_r<TR, TO, TAs...> OK.
  // Non-static member function is the most special citizen among the callables.
  // Comparing with the type of a function pointer(TypePF):
  //   Callables =>  |free fn|static member fn|lambda w/o capture|functor & lambda w/ capture
  //   is_same       |  yes  |      yes       |       no         |     no
  //   is_assignable |  yes  |      yes       |       yes        |     no
  template <typename T>
  using TypeIfFunction = typename std::enable_if<std::is_assignable<TypePF&, T>{}>::type;
  template <typename T>
  using TypeIfFunctor = typename std::enable_if<!std::is_assignable<TypePF&, T>{}
    && !std::is_same<std::decay<Slot>::type, std::decay<T>::type>{} // use default ctors.
    && std::is_invocable_r<TR, T, TAs...>{}>::type; // since c++17.

public:
  // Use default constructors for Slot according to the rule of zero.
  Slot() = default;
  Slot(const std::nullptr_t) noexcept : Slot() {};

  // for free functions, lambdas without capture and static member functions.
  template <typename TF, typename = TypeIfFunction<TF>>
  explicit Slot(TF pf) noexcept { bind(pf); }

  // for functors including lambdas with capture and std::function<>.
  template <typename TF, typename = TypeIfFunctor<TF>>
  Slot(TF&& pobj) noexcept { bind(std::forward<TF>(pobj)); }

  // for static member functions
  template <typename TB>
  explicit Slot(TB*, TypePF pmf) noexcept { bind(pmf); }

  // for non-static member functions
  template <typename TB, typename TO>
  Slot(TO* pobj, TR(TB::*pmf)(TAs...)) noexcept { bind(pobj, pmf); }
  template <typename TB, typename TO>
  Slot(const TO* pobj, TR(TB::*pmf)(TAs...) const) noexcept { bind(pobj, pmf); }

  Slot& operator=(TypePF pf) { bind(pf); return *this; }
  template <typename TF, typename = TypeIfFunctor<TF>>
  Slot& operator=(TF&& fn) noexcept { bind(std::forward<TF>(fn)); return *this; }

  explicit operator bool() const { return m_obj; }
  bool operator==(const Slot& rhs) const { return m_id == rhs.m_id; }
  bool operator!=(const Slot& rhs) const { return !operator==(rhs); }
  bool operator==(const std::nullptr_t) const { return !m_obj; }
  bool operator!=(const std::nullptr_t) const { return m_obj; }

  TypeID id() const { return m_id; }
  TR operator()(TAs&&... args) const noexcept { return emit(std::forward<TAs>(args)...); }
  TR emit(TAs&&... args) const noexcept
  {
    if(!m_obj) return TR();
    if(m_callback) return m_callback(m_obj, std::forward<TAs>(args)...);
    return (*static_cast<TypeOPF*>(m_obj)->pf) (std::forward<TAs>(args)...);
  }

protected:
  void bind(TypePF pf) noexcept
  {
    m_id = hash(reinterpret_cast<void*>(pf), nullptr);
    // Using storage for function pointer types is a design choice(cf. using template).
    // NB: type-punning by reinterpret_cast<> for a function pointer violates the c++ standard.
    store<TypeOPF>(std::move(TypeOPF{pf}));
  }

  template <typename TF, typename = TypeIfFunctor<TF>>
  void bind(TF&& fn) noexcept
  {
    using typeF = typename std::decay<TF>::type;
    // NB: any valid objects can be referenced to the generic pointer(void*).
    //   - functions, member functions and references are not objects.
    //   - so their pointers can't be converted to the generic pointer.
    m_obj = &fn;
    auto pmf = &typeF::operator();
    m_id = hash(m_obj, reinterpret_cast<void*>(reinterpret_cast<void(*&)()>(pmf)));
    m_callback = callFunctor<typeF>;
    // Storage is required for RValue lambdas with capture.
    // LValue functors including lambdas with capture can be called directly.
    if constexpr(!std::is_reference<TF>{}) store<typeF>(std::move(fn)); // since c++17.
  }

  template <typename TB, typename TPMF>
  void bind(TB&& pobj, TPMF&& pmf) noexcept
  {
    using typeTB = typename std::decay<TB>::type;
    using typeMF = struct { typeTB obj; typename std::decay<TPMF>::type pmf; };
    // Somthing weird but possible way.
    m_id = hash(pobj, reinterpret_cast<void*>(reinterpret_cast<void(*&)()>(pmf)));
    m_callback = callMember<typeMF>;
    // Using storage for non-static member functions is a design choice.
    // This is trade-off in using interfaces between fast but inconvenient template style
    // versus rather slow but more convenient std::function<> style.
    // NB: type-punning by reinterpret_cast<> for pointer to member functions violates
    //     the c++ standard.
    store<typeMF>(std::move(typeMF{std::forward<TB>(pobj), std::forward<TPMF>(pmf)}));
  }

private:
  size_t hash(const void* obj, const void* pmf) const
  { return reinterpret_cast<size_t>(obj) ^ reinterpret_cast<size_t>(pmf); }

  template <typename TF>
  static TR callFunctor(void* vobj, TAs&&... args) noexcept  // Why static?
  { return (static_cast<TF*>(vobj)->operator())(std::forward<TAs>(args)...); }

  template <typename TP>
  static TR callMember(void* vobj, TAs&&... args) noexcept   // Why static? => Your homework!
  {
    TP* pobj = static_cast<TP*>(vobj);
    return (pobj->obj->*pobj->pmf)(std::forward<TAs>(args)...);
  }

  template <typename TF>
  void store(TF&& fn)
  {
    using typeF = typename std::decay<TF>::type;
    // Use a fixed small buffer for normal cases - so called SBO(Small Buffer Optimization).
    if constexpr(sizeof(typeF) <= BufferMaxSize) {  // since c++17.
      m_size = sizeof(typeF);
      if(m_cleaner) m_cleaner(&m_buffer);
      new (m_buffer) typeF(std::move(fn));
      m_obj = m_buffer;
      m_cleaner = cleaner<TF>;
    }
    // Allocate heap memory only if the current buffer does not fit.
    else {
      if(sizeof(typeF) > m_size || m_data.use_count() > 1) {
        m_size = sizeof(typeF);
        m_data.reset(operator new(m_size), deleter<TF>);
      }
      else m_cleaner(m_data.get());
      new (m_data.get()) typeF(std::move(fn));
      m_obj = m_data.get();
      m_cleaner = cleaner<TF>;
    }
  }

  template <typename T>
  static void cleaner(void* p) { static_cast<T*>(p)->~T(); }
  template <typename T>
  static void deleter(void* p) { static_cast<T*>(p)->~T(); operator delete(p); }

private:
  void* m_obj{nullptr};                    // object pointer
  TypeCallback m_callback{nullptr};        // callback pointer
  TypeCleaner m_cleaner{nullptr};          // pointer to a storage cleaner
  char m_buffer[BufferMaxSize];            // small buffer storage
  std::shared_ptr<void> m_data{nullptr};   // big data storage
  size_t m_size{0};                        // size of data storage
  TypeID m_id{0};                          // Slot id
};