Google Go: 간단한 성능 평가

수요일에 있을 팀 세미나 준비하면서, Google Go로 간단한 병렬 프로그램을 짜고, 직렬(serial;sequential) 구현과 성능을 비교 해봤다. 일단 간단히 여기에 정리. 모든 테스트는 x64 버젼의 MacOSX 를 돌리는 MacBook(2008년에 산 녀석)/dual-core 에서 이루어 졌다.

매우 간단하게 병렬화 되는 알고리즘인, quicksort를 가지고 성능 테스트를 했다. pivot을 그냥 순열 중간에서 찍어내는 단순 무식한 방법으로 만들었음.

이하에선 대략 배열 길이가 512 보다 작으면 그냥 순차 알고리즘만 동작하게 했음.

Naïve 하게 시작

우선 처음엔 fork-join 하는 형태로 좀 많이 naïve 하게 짜봤다: 정수 400만개 정렬 시켰더니, goroutine 수가 너무 많다고 뻗음. (이건 내 코드의 버그였음). 더 이상 fork하지 않고 도는 threshold를 좀 높게 잡고(8192?) 돌렸더니 대략 1200ms 정도 걸리더라. 단순하게 그냥 짠 알고리즘을 싱글 스레드로 돌리면 약 2000ms. 거의 2 배의 스피드업이 있긴하다.

그래도 이건 좀 아니다 싶어서(…), Work-stealing queue를 짜기 시작.

Work-Stealing Queue

완전히 다 구현한건 아니고, 배열을 둘로 쪼갠 순간 다음과 같이 동작하게 했다.

배열의 앞 부분은 work-stealing queue로 전달하고, 나머지는 그 goroutine이 직접 정렬하게 했다. 물론 이것도 재귀적으로 적용되니까 전부 한 goroutine에선 이루어지지 않는다.

Work-Stealing Queue를 간단하게 구현한다고(…) 좀 가짜로 만들었다. 일단 큐를 스레드 별로 두지 않았다. 다만 자기 자기 큐에서 꺼낼 때의 LIFO 동작을 흉내내려고 전부 큐에 넣는게 아니라 마지막에 분할한 부분 배열은 자기가 직접 정렬한다. 그리고 다른 스레드의 큐에서 꺼내는걸 따라(?)해서 큐에서 꺼내는건 FIFO…

처음에 작업 종료되는걸 감지할 방법을 못찾고 해매다가, Queue에 넣은 작업 갯수 만큼 종료 신호를 받게 했다. 이것도 단순히 빈 슬라이스를 응답으로 보내게 해서 이거 숫자를 셌다(…).

대략 1100ms 정도 걸린다. 총 goroutine 수가 입력에 비례하는게 아니라, 코어 수에 맞춰놔서 naïve 구현처럼 panic() 함수 호출되는 일은 없었음;;;

C++이랑 비교

C++의 <algorithm>에 있는 sort 랑 비교해봤더니 너무 큰 차이가 난다. 대략 700ms 좀 안 걸리게 돌더라. 이건 무려 싱글 스레든데;;; 사실 이건 내 구현이 sort() 함수의 introsort 보다 예상 성능 자체가 낮아서 생기는 일이기도 하지만;;
내가 짠 알고리즘을 싱글 스레드로 돌린 경우 1580ms 정도 걸렸다.  (cf. Go는 2000ms)

intel tbb의 tbb::parallel_sort()를 사용한 경우 대략 350ms 쯤 걸린다. linear-speedup? 이게 가장 빠르긴 하구나.

Go 쪽에 썼던 코드를 그대로 넣고 돌렸더니 대략 1600ms. 그래도 코어 2개 쓰는 쪽이 빠르긴 하지.

요약

Go(single-thread): 2000ms
Go (parallel) : 1100ms

C++(single-thread; same algorithm): 1600 ms
C++(single-thread; std::sort() ) : 700ms
C++(2-threads; tbb::parallel_sort() ):  350ms

간단한 감상: 좀 더 최적화 할 여지가 있어 보인다. 심심풀이로 실제 물리 코어 수 보다 더 많은 MACPROCS를 지정했더니 성능이 꽤 빨리 내려간다. 생각보다 channel 통한 통신의 오버헤드는 크지 않아서 만족스러웠다. fork-join 과 worker-thread 비슷하게 짠 게 큰 차이는 안나는걸 보니… 반대로 goroutine은 아무리 많이 만들어도(한 6만개 만들어도 잘 돈다) 괜찮긴 하더라..

+ naïve 하게 짜면 망한다(???).