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

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

덧글

[Lyn]

STL 보단 MFC 에 무게를 두려는 MS의 작전일지도

[object]

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

[Lyn]

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

.net Framework 에서의 구조와 거의 비슷하군요

[킬러앱스]

Stlport 를 쓰시는건 어떤지?

[object]

STL port도 있었군요. 일단 해쉬 테이블은 ATLMFC 버전이 제일 빨라 일단 이 녀석을 이용 중입니다.

[tan]

해시테이블!! 얼마전에 자바책에서 나온거!! 와 드디어 아는 거 나왔다...

[까막]

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

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

[object]

감사합니다. 실험 결과 첨부했습니다.

[noname]

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

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

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

[까미유]

혹시 release 모드로 컴파일하셨나요?

[object]

본문 중에.. "컴파일러는 인텔 컴파일러로 윈도우 리눅스 비슷하게 최적화를 줬다"

[kalstein]

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

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

그래서 큰 차이를 보이는것으로 알고있네요...^^

[anonymous]

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

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

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

hash_map용 iterator를 구현하기 귀찮았나? 느낌도 좀 드네요.