상세 컨텐츠

본문 제목

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

프로그래밍/테크닉

by 적분 ∫2tdt=t²+c 2019. 12. 25. 14:35

본문

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 등에서는 조금 다를 수도 있습니다.)


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

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

위는 float 타입이 메모리에 저장되는 방식을 보여줍니다. 최상위 비트는 부호를 나타내고, 하위 8비트는 지수부, 최하위 23비트는 가수부를 나타냅니다. 부호부를 s(0 혹은 1), 지수부를 e(0~255의 정수), 가수부를 f(0~223-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) 범위의 난수가 생성되게 됩니다. 이렇게 하면 비트 연산 몇번과 부동소수점 뺄셈 한 번이면 난수 생성이 끝납니다. 훨씬 빠르겠지요.



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

std::generate_canonicalfast_generate_canonical
프로그램 총 수행시간82.7s66.4s
실수 난수 생성에 소요된 총 시간33.1s16.8s

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

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

태그

관련글 더보기

댓글 영역