VC++ hash_table의 엄청난 느린 속도 by object

hash table을 매우 자주 써야하는 프로그램을 만들고 있다. 그냥 별 생각없이 리눅스도 돌아가고 윈도우도 돌아가야하니 아직 STL 표준은 아니지만 VC++, GNU 공히 들어있는 hash_map을 썼다. 설마 얼마나 느리겠어 하면서 지금까지 잘 썼는데... 배신을 당했다. 일단, VC++의 hash_map 구현은 무척이나 황당하다. vector와 list를 내부적으로 쓰고 있다. 그래서 무진장 느리다. GNU 버전은 소스를 제대로 확인하지 않았으나 VC++ 만큼 황당하지 않고 훨씬 빠르게 구현되어있다.

그래서 직접 hash table 하나 만들려다 ATLMFC (#include <atlcoll.h>)로 쓸 수 있는 CAtlMap을 포팅하여 리눅스 윈도우 모두 사용할 수 있도록 했다. ATLMFC 컬렉션은 포팅하기가 상당히 쉽다. try, catch 같은 거 좀 무시하고 암튼 대충 작업하면 한 20분이면 잘 작동하게 포팅할 수 있다. CAtlMap의 해쉬 테이블은 교과서에서 배운 그 해쉬테이블의 구현과 완벽히 동일하다. 버킷이 1차원 배열로 할당되어있어서 바로 접근이 가능하며 충돌이 났을 땐 리스트로 연결이 된다.

그리고 VC++ hash_map, GNU hash_map, ATLMFC hash_map의 성능을 비교해봤다.

// perftest.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <iostream>
#include <string>

using namespace std;

#ifdef _WIN32
#include <hash_map>
using namespace stdext;
#else
#include <ext/hash_map>
using namespace __gnu_cxx;
#endif

#include "mySTL.h"


int main(int argc, char* argv[])
{
int size = atoi(argv[2]);
if (atoi(argv[1]) == 0)
{
hash_map map1;

for (int i = 0; i < size; ++i)
map1[i] = i;

for (int i = 0; i < size; ++i)
++map1[i];

for (int i = 0; i < size; ++i)
map1.erase(i);

for (int i = 0; i < size; ++i)
++(map1[i] = i);

cout << "STL: " << map1.size() << ", " << map1[size / 7] << endl;
}
else
{
mySTL::GHashMap map2;

for (int i = 0; i < size; ++i)
map2[i] = i;

for (int i = 0; i < size; ++i)
++map2[i];

for (int i = 0; i < size; ++i)
map2.RemoveKey(i);

for (int i = 0; i < size; ++i)
++(map2[i] = i);

cout << "mySTL: " << map2.GetCount() << ", " << map2[size / 7] << endl;
}
return 0;
}

컴파일러는 인텔 컴파일러로 윈도우 리눅스 비슷하게 최적화를 줬다. 윈도우는 32비트 결과이기는 하나 64비트로 컴파일해봐도 별반 차이가 없었음. 운영체제는 윈도우, 리눅스 모두 64비트.

 

자, 이제 MS STL hash_map의 놀라운 성능을 목격하시라! 생동감을 더 하기 위해 직접 캡쳐!!

몇 배인가 도대체?? 8배가 넘게 느린 것이다! 도대체 뭐 때매 이렇게 느린가? CPU/메모리 사용률을 한 번 위의 1천만 번이 아니라 5천만 번에 대해 찍어봤다.

이렇게 극명하게 차이가 났다. 보다시피 메모리 할당자가 멍청한 짓을 하거나 삽입, 접근 등 기본적인 작동이 데이터 개수가 많아지면 황당할 정도로 느려졌다. 할당자가 멍청한가 싶어서 테스트를 약간 바꿔서 해봤다. 십만 개의 데이터를 넣고 빼는 걸 백 번 반복하도록 해봤다. 그래도 매우 느렸다. 원인은 밝히기 귀찮아서 포기.

50만 개에서 5천만 개까지 테스트를 해보고 그래프를 그려봤다. y축 단위는 초.

이번에는 64비트 RHEL에서 돌려봤다.

황당하지 않고 무난한 속도로 작동한다. 그래도 ATLMFC의 해쉬를 포팅한 것이 조금 더 빠르다.

참고로 ATLMFC에도 STL처럼 trait 클래스를 확장할 수 있어서 임의의 타입에 대한 해쉬, 크기 비교 연산 등을 모두 재할당할 수 있어 사용성이 무척 높다. 그런데, ATLMFC도 황당한 점이 있는데 CAtlArray 즉, 벡터에 대응되는 녀석도 삽입이 엄청 느리다. 특히 아이템 개수 많아지면 이거 완전히 지수 함수로 시간이 더 걸리는 듯.

결론: VC++ STL의 hash_map은 쓰지 마시오.


까막님의 제보로 http://code.google.com/p/google-sparsehash/에 있는 dense_hash_map을 테스트 해봤습니다. sparse_hash_map은 시간보다 메모리에 더 신경을 쓴 녀석이고 dense는 시간 최적화입니다. 시간 측정 테스트 코드에 포팅한 ATLMFC 해쉬를 넣어서 같이 돌려봤습니다. 성능은 큰 차이는 없어 보이나 그래도 삽입과 탐색은 ATL 버전이 빠르군요.

Average over 10000000 iterations
Current time (GMT): Sun Jul 20 23:04:44 2008

*** WARNING ***: sys/resources.h was not found, so all times
reported are wall-clock time, not user time

SPARSE_HASH_MAP:
map_grow 1179.4 ns
map_predict/grow 702.0 ns
map_replace 333.9 ns
map_fetch 363.5 ns
map_fetch_empty 74.9 ns
map_remove 394.7 ns

DENSE_HASH_MAP:
map_grow 226.2 ns
map_predict/grow 170.1 ns
map_replace 85.8 ns
map_fetch 79.6 ns
map_fetch_empty 1.6 ns
map_remove 85.8 ns

STANDARD HASH_MAP:
map_grow 669.3 ns
map_predict/grow 705.1 ns
map_replace 156.0 ns
map_fetch 148.2 ns
map_fetch_empty 15.6 ns
map_remove 307.3 ns

STANDARD MAP:
map_grow 326.0 ns
map_predict/grow 313.6 ns
map_replace 131.0 ns
map_fetch 112.3 ns
map_fetch_empty 4.7 ns
map_remove 279.3 ns

mySTL HASH_MAP:
map_grow 223.0 ns
map_predict/grow 99.9 ns
map_replace 132.6 ns
map_fetch 65.5 ns
map_fetch_empty 23.4 ns
map_remove 165.4 ns

핑백

  • art.oriented : 스택오버플로우: 새로운 개발자 커뮤니티의 대안 2009-12-03 21:35:05 #

    ... 와 cout을 비교하면 그 차이는 현저하게 준다. 어떤 사람은 cout이 더 빠르다고 주장하기도 했다. cout, printf의 구현은 전적으로 해당 라이브러리에 의존적이다. STL도 마찬가지다. 구현에 따라 성능 차이가 매우 심하게 날 수 있다. cout과 printf 문제에서 cout이 느린 이유는 그냥 MSVC의 cout 구현은 멍청해서다. 혹시 저 글로 ... more

  • art.oriented : VC++ STL의 멍청한(?) string 2010-02-27 16:46:28 #

    ... 신가요? 그리고 다른 STL 구현의 string은 어떻게 행동하는지 알려주시면 대단히 고맙겠습니다. 안 그래도 VC++의 C++ cout은 무지하게 느리고 hash_map 구현도 매우 멍청한데 string 까지 나를 실망 시킬 것인가… 보너스 비슷한 이야기로 위 그림에서 ca, cb는 같은 내용의 스트링을 가리킨다. 그렇다면 얘들은 프로그램 내에서 동일 ... more

  • 미친병아리가 삐약삐약 : 2008년 07월 21일.. 2010-04-21 11:44:20 #

    ... 까 문제다. 10년 동안 한 우물만 파 보라. 할 게 없으면 길거리에 널부러진 병뚜껑이라도 10년을 주워 보라. 세상이 당신을 달리 보게 될 것이다"고 했는데.. VC++ hash_table의 엄청난 느린 속도 마이크로소프트 같은 회사에서도 내부 의사소통 및 소스교환은 인원이 많다보니 엄청나게 힘든가보다.. 어느 팀에서 만든 코드중 어떤 것은 훌륭하지만, 어떤 것 ... more

덧글

  • Lyn 2008/07/19 21:13 # 삭제 답글

    STL 보단 MFC 에 무게를 두려는 MS의 작전일지도
  • object 2008/07/20 05:34 #

    MFC는 예전에 버림을 받았습니다만.. 요즘 다시 키워주려고 하는 것 같긴한데 자기들도 쓰지 않은 MFC 라이브러리이긴 하죠. C# 아래에선 STL이나 MFC나 버림 받은 자식일 뿐.
  • Lyn 2008/07/19 21:45 # 삭제 답글

    그런데 Hash 가 Vactor 가 List 를 내부에 가지고 있다는건...

    .net Framework 에서의 구조와 거의 비슷하군요
  • 킬러앱스 2008/07/20 01:12 # 답글

    Stlport 를 쓰시는건 어떤지?
  • object 2008/07/20 05:33 #

    STL port도 있었군요. 일단 해쉬 테이블은 ATLMFC 버전이 제일 빨라 일단 이 녀석을 이용 중입니다.
  • tan 2008/07/20 21:13 # 삭제 답글

    해시테이블!! 얼마전에 자바책에서 나온거!! 와 드디어 아는 거 나왔다...
  • 까막 2008/07/21 01:12 # 삭제 답글

    http://code.google.com/p/google-sparsehash/ 에 있는 densh/sparse 구현을 써보시는 것도 괜찮을 듯 싶네요.

    제가 테스트했던 바로는 괜찮은 성능을 가지고 있었습니다. (그 기능 자체가 폐지되어서 쓰진 않지만요.)
  • object 2008/07/21 09:07 #

    감사합니다. 실험 결과 첨부했습니다.
  • noname 2008/07/27 06:54 # 삭제 답글

    해시 테이블이 이렇게 느린지 몰랐군요.

    블로그 스킨이 가로로 넓어져서 상당히 보기 시원합니다. ^^

    >공사중: 이글루스 스킨의 !DOCTYPE 문제로 현재 파이어폭스에서만 의도대로 제대로 나옵니다.
    이글루스를 사용 안 한지 오래되서 확실치는 않지만, 기존에 쓰던 스킨을 편집하면 doctype이 제대로 안 나오던 문제가 있었던 걸로 기억합니다. 메뉴에서 스킨을 새로 처음부터 작성하면 x/html을 준수하는 스킨을 작성할 수 있었던 것 같은데 혹시 그걸로 해결될지도 모르겠습니다. (확실치는 않습니다. ^^;)
  • 까미유 2008/10/08 14:34 # 삭제 답글

    혹시 release 모드로 컴파일하셨나요?
  • object 2008/10/08 14:45 #

    본문 중에.. "컴파일러는 인텔 컴파일러로 윈도우 리눅스 비슷하게 최적화를 줬다"
  • kalstein 2009/02/12 12:46 # 삭제 답글

    오래된 글에 코멘트를 다는군요 ^^;;

    vc++의 hash_map의 경우 int타입 (본문의 코드에서는 어떤 타입으로 map을 생성했는지 나와있지않지만 그냥 코드로 추측입니다)의 경우에도 hash function을 수행합니다.
    반면, gcc측의 hash_map의 경우에 int일 경우 hash function을 수행치않고, int 값 자체를 이용합니다.

    그래서 큰 차이를 보이는것으로 알고있네요...^^
  • anonymous 2009/03/20 16:53 # 삭제 답글

    오래된 글에 또 코멘트를 다는군요.

    내부적으로 vector/list를 쓰는 것은 사실 큰 문제는 아닙니다.
    list를 "하나만" 쓰고 버킷을 vector<list::iterator>로 구현한 것이 삽이죠. -_-

    대신 vc++에서 얻은 것은 next / prev 연산이 O(1)이라는 점입니다.
    다만 이 기능은 쓸 일이 별로 없다는 점과 hash table이 충분히 차면 왠만한 경우에도 next / prev 연산은 그다지 비싸지 않다는 점이 있겠네요.

    hash_map용 iterator를 구현하기 귀찮았나? 느낌도 좀 드네요.
댓글 입력 영역