*오류 수정* C++와 C#, Java, 그리고 Node.js 정렬 성능 비교

조종국님께서 댓글에서 지적해주신 절사평균 오류가 수정되어 소스코드와 측정 결과가 업데이트되었습니다. 결과적으로 C# 이외의 언어들에 대한 정렬 성능 평가가 낮아졌습니다.
– 2014년 10월 17일 –

어제(2014년 6월 16일) 추가된 Java 코드가 공정하지 못했습니다. 예상보다 Java 코드가 느려서 검토해본 결과, 기존의 C++, C#, Node.js는 모두 rand() 네이티브 함수를 사용해 난수를 만들었기 때문에 난수 도메인의 크기가 15비트인 반면 Java 코드는 매개변수 없는 버전의 java.util.Random.nextInt() 함수를 사용했습니다. 이 포스트의 관심사는 언어별 정렬 속도가 아닌 최대한 유사한 코드를 이용한 CPU 집약적인 코드의 성능 비교이기 때문에 Java 역시 15비트 난수를 사용하도록 수정했습니다. 결과는 많이 달라졌습니다. 이것과 관련되어 수정된 부분은 별도 표시했습니다.
– 2014년 6월 17일 –

처음엔 귀찮아서 제외했지만 찝찝한 느낌이 사라지지 않아 Java를 추가했습니다.
– 2014년 6월 16일 –

며칠전 Swift의 -Ofast 컴파일러 설정에 대한 글을 접했습니다. 저는 아직 Swift에 대해 잘 모르고 실습 경험도 전혀 없지만 이 글에 의하면 -Ofast 설정은 약간은 도박적으로 코드의 제한을 풀어 성능을 극대화합니다. 결과적으로 정렬 작업에 대해 C 코드보다 약간 높은 성능을 보여준다고 하네요. 안정성을 담보로 하기 때문에 개발자의 주의를 강하게 요구하면서도 최소한의 성능 집약적 코드를 최적화하는 데에 이용 가치가 있을 수도 있겠습니다.

그렇다면 안정적 코드를 제공하는 ‘관리’ 개념을 가진 .NET 코드와 Java 코드는 어느 정도 성능을 보여주는지 C++ 코드와 비교해봤고 기왕 하는김에 성능 미신이 따라다니는 Node.js를 포함해 봤습니다.

사실, 2006년이었나요? C#에 제네릭 지원이 시작된 시점에 통계 패키지에 적합한 자료구조와 몇 가지 알고리즘에 대한 변형을 구현하면서 C++ 코드와 .NET 제네릭 코드에 대해 동일한 성능 비교 테스트를 수행한 적이 있지만 이젠 보고서가 어디에 있는지도 모르겠고 그동안 하드웨어가 비교할 수 없을 정도로 발전했으니 다시 한 번 해보고 싶었습니다.

1,000,000개의 32비트 정수형 난수 데이터를 정렬하는 데에 소요된 시간을 측정했습니다. 하드웨어 환경은 16 GB, i7 2.3 GHz 4 Core 맥북 프로에서 구동되는 3 GB 메모리와 CPU 4개를 할당한 Parallels 가상머신이고 OS는 Windows 8.1 64 bit 입니다.

C++와 C#에 대해서는 x86과 x64 플랫폼에 대해 테스트했고 각 언어 별로 2-way 및 3-way 분할 퀵 정렬과 기본적으로 내장된(built-in) 정렬 함수를 비교했습니다.

3-way 분할의 경우 Java에서 엄청난 성능 향상을 보여준다는 조언을 페이스북을 통해 얻어 추가했습니다.

각 테스트는 노이즈를 제거하기 위한 최소한의 작업으로 12회 반복한 후 소요시간의 최대값과 최소값을 제외한 절사평균을 취했으며 단위는 밀리초입니다.

구분(소스코드 링크) 2-way partition 3-way partition Built-in
C++ x86 62.5ms 61.0ms 67.3ms
C++ x64 64.2ms 57.8ms 62.6ms
C# x86 89.3ms 70.1ms 85.6ms
C# x64 80.9ms 68.3ms 67.6ms
Java 93.8ms 57.8ms 62.6ms
Node.js 125.0ms 138.9ms 217.3ms

결과를 정리해 보면 다음과 같습니다.

  1. 2-way 분할의 경우 C++에 비해 C#은 1.26배, Java는 1.46배, Node.js는 1.95배 시간이 소요되었습니다.
  2. 3-way 분할의 경우 C++에 비해 C#은 1.18배, Java는 1.00배, Node.js는 2.40배 시간이 소요되었습니다. Java가 아주 높은, C++와 동등한, 성능을 보여줬으며 Node.js는 오히려 2-way 분할보다 오래 걸렸습니다.

    Java가 왜 3-way 분할 퀵 정렬에 이토록 유리한지 Java 뜨내기인 저로서는 잘 모르겠지만 매우 흥미롭습니다.

  3. 64 bit Windows 위에서 x86 빌드가 x64 빌드보다 조금 느립니다. C# 프로젝트의 경우 /platform:anycpu32bitpreferred 컴파일러 옵션(Visual Studio에서 Build 탭의 ‘Prefer 32-bit’ 확인)은 성능에 불리하겠습니다.
  4. C#의 내장된 정렬 기능은 Array.Sort() 메서드인데, CLI 소소코드를 보면 내부적으로 comarrayhelpers.h 파일에 정의된 template<class KIND> ArrayHelpers 클래스의 QuickSort() 네이티브 함수가 사용됩니다. x86 빌드와 x64 빌드의 성능이 크게 차이가나고 심지어 x86 빌드의 경우 관리 코드와 성능이 비슷합니다.

    살짝 살펴봤는데 WRAPPER_CONTRACT 매크로를 의심해 봅니다. 이 매크로는 x86 빌드에서 __annotation(L"WRAPPER")가 사용되고 x64 빌드에서는 무시됩니다. 성능 프로파일링을 해본 것은 아니기 때문에 어디까지나 추측입니다.

  5. Java의 내장 정렬 기능은 java.util.Arrays.sort() 메서드이며 C# x64 빌드의 그것에 비해 비교적 높은 성능을 보여줍니다.
  6. Node.js는 아직 CPU 집약적인 작업에 유리하지 않지만 JavaScript가 정적 언어의 성능에 이정도로 가까이 접근했다는 것은 놀라운 일입니다. 내장 정렬 기능은 Array.prototype.sort() 함수이며 네이티브 구현임에도 불구하고 비교 콜백 호출이 부담을 줍니다.

테스트에 사용된 전체 코드는 여기에 있습니다. 다운받아 어렵지 않게 직접 실행해 볼 수 있습니다.

Advertisements

*오류 수정* C++와 C#, Java, 그리고 Node.js 정렬 성능 비교”에 대한 2개의 생각

  1. 조종국 (Jo, JongGuk) (@LazyZombie)

    average구하는 것에 조금 버그가 있는 것 같습니다.
    12번 돌려서 최고 빠른 값과 최고 느린 값 두개를 빼는것이 의도인것 같으신데
    c#외에는 최고 빠른 값과 최고 느린 값, 그리고 그 다음 느린 값을 빼고 그것을 10으로 나누게 되어 있습니다. (결국 9번을 샘플링 해서 10으로 나누게 되어 있는 것 같습니다)

    어떻든 언어간 기본적인 퍼포먼스 차이를 보여주셔서 도움이 많이 되었습니다.

    응답

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중