[C++] 빠른 generate_canonical 함수 만들기

C++11 표준에서부터 랜덤 함수와 관련된 여러 라이브러리들이 추가되었는데요, 그 중 랜덤한 실수를 생성하기 위한 제일 기초적인 함수로 std::generate_canonical이 있습니다. 이 함수는 임의 부동소수점 타입의 수를 [0, 1) 범위 (0~1인데 0은 포함하고 1은 포함하지 않음)에서 임의로 생성합니다. 또한 이 때 생성할 난수의 최소 랜덤 비트를 템플릿 인자로 설정할 수 있게 되어있습니다. 이 함수는 제일 기본적인 실수 난수를 생성하므로, 이보다 더 복잡한 실수 난수들(정규 분포에서 뽑기, 베타, 감마 분포에서 뽑기 등)은 이 함수의 결과값을 바탕으로 사용합니다. 즉 랜덤 실수 생성의 기본 중의 기본이라 할 수 있습니다.

또한 깁스 샘플링과 같이 확률적 샘플링을 사용하는 프로그램을 짜게 되면 각 선택지의 가중치가 다른 이산 분포에서 표본을 추출해야 할 일이 잦은데, 이 역시도 generate_canonical을 사용합니다. (대표적으로 토픽 모델링 툴킷인 tomotopy에서도 이 함수를 매우 많이 호출합니다. 실행시간의 대략 40% 정도를 generate_canonical가 차지하지요) 따라서 generate_canonical 함수를 최적화하여 속도를 올리는 것만으로도 많은 경우 전체 속도를 크게 향상시킬수 있는데요, 이미 표준 라이브러리인 generate_canonical의 속도를 더 끌어올릴 수 있는 방법이 있을까요?

당연히 있으니깐 이렇게 포스팅을 작성했겠지요! generate_canonical함수는 다양한 난수 생성기에 대해서 작동해야 한다는 보장이 있으므로 특정 난수 생성기에 최적화된 코드를 사용할 수가 없다는 문제가 있습니다. 우리는 이 제약 조건을 완하하고 단순히 [0, 1) 범위의 float 실수를 생성하는 것으로 목표를 바꿔 코드를 최적화해보도록 하겠습니다.

먼저 generate_canonical 함수가 어떻게 구현되어 있는지 살펴볼까요? (MSVC 2017에 포함된 코드입니다. gcc, clang 등에서는 조금 다를 수도 있습니다.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

template<class _Real,     size_t _Bits,     class _Gen> _Real generate_canonical(_Gen& _Gx) {     // 먼저 _Real 타입의 가수부의 비트수를 파악합니다.     const size_t _Digits = static_cast<size_t>(numeric_limits<_Real>::digits);     // 그래서 생성해야할 랜덤 비트의 수를 결정합니다.     const size_t _Minbits = _Digits < _Bits ? _Digits : _Bits;       // 난수 생성기가 생성하는 랜덤 최솟값과 최댓값을 파악합니다.     const _Real _Gxmin = static_cast<_Real>((_Gx.min)());     const _Real _Gxmax = static_cast<_Real>((_Gx.max)());     // 그 차이에 1을 더한값이 실제 난수 생성기가 생성하는 난수의 가짓수입니다.     const _Real _Rx = (_Gxmax - _Gxmin) + static_cast<_Real>(1);       // 난수 가짓수를 바탕으로 총 몇번 난수를 생성해야     // 원하는 랜덤 비트를 확보할 수 있는지 파악합니다. (Kx값)     const int _Ceil = static_cast<int>(_STD ceil(         static_cast<_Real>(_Minbits) / _STD log2(_Rx)));     const int _Kx = _Ceil < 1 ? 1 : _Ceil;       // 이 부분 전까지는 컴파일 타임에 다 연산이 마무리됩니다.     // 다음 부분만이 실제 런타임에 수행되는 연산입니다.           _Real _Ans = static_cast<_Real>(0);     _Real _Factor = static_cast<_Real>(1);       // 앞서 파악한 Kx값만큼 루프를 돌며 난수를 생성합니다.     // 하위비트부터 차례로 더해나가 전체 값을 생성한뒤 _Factor로 나누어     // 0~1 사이의 난수를 생성합니다.     for (int _Idx = 0; _Idx < _Kx; ++_Idx)     {         _Ans += (static_cast<_Real>(_Gx()) - _Gxmin) * _Factor;         _Factor *= _Rx;     }       return (_Ans / _Factor); }</p>

보다시피 범용성을 위해 여러 제약 조건들을 지키다 보니 불필요한 부분이 많습니다. 우리는 어차피 float만 생성할것이고, 우리가 사용할 난수 생성기는 어차피 한번에 최소 32비트( [0, 2^32) 범위의 수 )를 생성한다는 가정을 붙이면 윗 부분은 다 생략할 수 있습니다. 간략해진 fast_generate_canonical 함수를 살펴보시죠.

1 2 3 4 5 6 7 8 9 10

template<class _Gen> float fast_generate_canonical(_Gen& _Gx) {     // 이 값은 언제나 [0, 2^32) 사이에 있습니다.     uint32_t rand_bits = _Gx();           // rand_bits를 2^32로 나누면 [0, 1) 범위의 수가 생성됩니다.     // powf 함수는 어차피 컴파일 타임에 계산되어 최적화될테니 걱정 안하셔도 됩니다.     return rand_bits / std::powf(2, 32); }

코드가 확 줄었죠. 그런데 아쉬운 점이 있습니다. 가장 비싼 연산인 나눗셈과 부동소수점으로의 캐스팅이 포함되었다는 것이죠. 얘를 좀더 개선할 순 없을까요? IEEE754의 부동소수점 포맷을 유심히 살펴보면 나눗셈 없이도 난수 생성이 가능하다는 걸 알 수 있습니다.

위는 float 타입이 메모리에 저장되는 방식을 보여줍니다. 최상위 비트는 부호를 나타내고, 하위 8비트는 지수부, 최하위 23비트는 가수부를 나타냅니다. 부호부를 s(0 혹은 1), 지수부를 e(0~255의 정수), 가수부를 f(0~2²³-1의 수)라고 하면 위 표현이 나타내는 부동소수점의 값은 다음과 같습니다. (단 정규값일 경우에만 해당합니다. 비정규값의 경우 표현법이 다릅니다.)

우리는 [0, 1) 범위의 실수를 생성하고 싶으므로 s는 신경 쓸거 없이 0으로 두면 되겠습니다. 가수부는 항상 [1, 2) 의 값을 가지며 이 가수부의 크기를 지수부가 조절합니다. 그런데 이 방식대로라면 [0, 1)의 값을 생성하기가 쉬워보이지 않는군요. 0은 특수한 값이라서 모든 비트를 0으로 설정해야 합니다. 반면 0.5는 f=0, e=126로 설정해야하죠. 0.25의 경우 f=0, e=125로 잡아야하구요. 0.75는 f=2^22, e=126으로 설정해야합니다. [0, 1)사이에서 고른 분포를 가지도록 각 비트들을 세팅하는건 복잡해보입니다.

그래서 목표를 약간 수정하여 [1, 2)를 생성하도록 합시다. 이 경우 e=127로 항상 고정하면 되고, 가수부인 f는 자유롭게 랜덤비트를 세팅하면 됩니다. 그럼 [1, 2) 범위에서 고른 난수가 생성됩니다. (무작위성은 딱 23비트만큼이 됩니다. 좀더 큰 무작위성을 원한다면 double을 쓰셔야겠네요.) 그리고 최종적으로 이렇게 생성된 난수에서 1을 빼주면 우리가 처음에 원하던 [0, 1) 범위의 난수가 생성되게 됩니다. 이렇게 하면 비트 연산 몇번과 부동소수점 뺄셈 한 번이면 난수 생성이 끝납니다. 훨씬 빠르겠지요.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

template<class _Gen> float fast_generate_canonical(_Gen& _Gx) {     // 공용체를 이용해 정수 u를 수정하면     // 부동소수점 f도 수정되도록 해보겠습니다.     union     {         float f;         uint32_t u;     };       // 먼저 랜덤 비트를 잔뜩 생성합니다.     u = _Gx();     // 하위 23비트만 그대로 남기고     // 지수부는 127로 설정합니다.     u = (127 << 23) | (u & 0x7FFFFF);     // f에서 1을 빼면 원하는 범위인 [0, 1)의 난수가 생성됩니다.     return f - 1; }

속도는 얼마나 빨라졌을까요? 개발중인 tomotopy LDAModel에 적용하여 테스트해보았습니다. 총 약 42만단어가 포함된 3000개의 문헌을 80개의 토픽으로 분류하는 작업을 수행했습니다.

	std::generate_canonical	fast_generate_canonical
프로그램 총 수행시간	82.7s	66.4s
실수 난수 생성에 소요된 총 시간	33.1s	16.8s

std::generate_canonical이 전체 수행 시간 중 차지하는 비중은 약 40%였습니다. 굉장히 큰 병목이었던 셈이죠. 시간으로 따지면 약 33초가 std::generate_canonical 실행에 쓰였는데, 이를 fast_generate_canonical로 개량하자 약 17초로 2배 가까이 빨라졌습니다. 이정도면 엄청난 공짜 점심이네요.

여기서 사용한 트릭은 사실 uniform real distribution을 생성하기 위해 예전부터 유구히 사용되어 오던 트릭입니다. 다만 float 혹은 double 타입에만 적용될 수 있으며 여타 다른 부동소수점 포맷에 대해서는 잘 작동하지 않을 수 있기 때문에 c++ 표준에서는 이런 트릭을 이용한 구현을 택하지 못하는 걸로 보입니다. 따라서 돌다리도 두드려보고 건너야하듯, 최적화를 위해서는 표준 라이브러리도 두드려보고 해부해보는게 필요하겠습니다.