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 하게 짜면 망한다(???).

Published by

rein

나는 ...

3 thoughts on “Google Go: 간단한 성능 평가”

  1. 병렬 프로그래밍에 대해 관심을 가지고 공부하고 있습니다.
    serial code보다 parallel code의 성능이 확연히 높아서 참 신기합니다.
    병렬 프로그래밍 언어 Go에 대해서도 들어본적이 있는데 이미 테스트 해보셨네요. ^^
    현재 TBB를 공부하고 있습니다.
    질문이 있습니다…
    TBB, OpenMP, MPI의 차이점이 뭔가요? ^^…

    좋은 날 되세요 ㅎㅎ.

    1. 이 포스팅의 내용에서 좀 많이 벗어나는 얘기라 간단히 설명하자면,

      세 가지 모두 병렬화를 위한 라이브러리로 멀티 스레딩의 복잡성을 최대한 감추면서 성능을 올리자라는 점은 같습니다.(MPI는 좀 다를지도 모르지만)

      그렇지만 병렬화를 위해 선택하는 방법에 큰 차이가 있습니다. 사용할 수 있는 환경(특히 메모리 모델)에서도 차이가 크고요…
      TBB는 태스크라는 추상화 개념을 쓰고, 라이브러리 내부에서 멀티스레딩하는 형식으로 복잡성을 줄이자는 거고,
      OpenMP는 소스코드에 적절한 directive를 넣어서 “컴파일러가 최대한 자동으로” 병렬화해서 복잡성을 줄이자는 얘기지요.

      MPI는 좀 접근 방식이 많이 다른데, 일단 이건 개별 노드(분산된)가 있는 환경에서, 이 노드들이 “어떻게 데이터를 주고 받아서 병렬 연산을 할지”에 초점이 맞춰져 있습니다.
      뭘 해준다기보단, “이런 행동 방식을 보장”한다 정도라서… 그리고 이건 어쩔 수 없이 굉장히 명시적인데(특히 OpenMP에 비해서), 덕분에 전반적인 성능과, 노드 수(CPU 수나 머신 수)가 늘어났을 때의 성능 향상은 가장 좋습니다.

Leave a Reply