STL map, SLT hash_map, CAtlMap, TR1 unordered_map 성능 테스트
Moderator: 류광
-
- Posts: 1035
- Joined: 2002-01-09 09:00
STL map, SLT hash_map, CAtlMap, TR1 unordered_map 성능 테스트
예전에 누군가를 통해서 VC++의 hash_map이 느리다라는 말을 들은 적이 있었지만 그 당시에는 FreeBSD에서 개발하고 있어서 ‘설마?’라는 생각만 하고 끝냈습니다.
시간이 지난 후 VC++의 hash_map이 느리다라는 말을 잊고 있었는데 근래 GPGStudy에서 다시 느리다라는 말이 언급 되었고, ‘온라인 서버제작자 모임’ 커뮤니티에서 ‘풍이’님이 손수 테스트한 결과를 코드와 같이 올려주셨고( http://cafe.naver.com/ongameserver/3619 ), 왜 VC의 hash_map이 느린가에 대해 주말에 웹 서핑을 통해서 관련 글을 보았습니다( http://minjang.egloos.com/1983788
, http://junyoung.tistory.com/1 ).
오늘 출근 후 바로 직접 테스트 해 보았습니다. 또 VS 2008 SP1에서 추가된 TR1의 unordered_map도 추가했습니다.
테스트 환경은 Windows 2008 Server 64bit, Visual Studio 2008 Pro SP1 입니다.
결과는 CAtlMap이 가장 빠르고, STL hash_map은 생각보다 느리고, 특히 TR1의 unordered_map은 너무 느렸습니다.
VC의 hash_map이 gcc의 hash_map 보다 느리다고 하니 VC++의 TR1 보다도 boost의 unordered_map이 더 빠르지 않을까 라는 생각을 합니다. 혹시 이거 테스트 가능한 분들은 테스트 부탁합니다.
백 마디의 말보다 하나의 코드가 더 좋습니다. ^^
테스트한 코드도 올리니 틀린 부분이 있으면 말로만 이야기 하지 마시고 직접 코딩을 하여 결과를 보여 주시면 고맙겠습니다.
그림과 파일을 올리는 기능이 없어서 제 블로그 주소를 링크합니다.
http://blog.naver.com/jacking75/140062720030
시간이 지난 후 VC++의 hash_map이 느리다라는 말을 잊고 있었는데 근래 GPGStudy에서 다시 느리다라는 말이 언급 되었고, ‘온라인 서버제작자 모임’ 커뮤니티에서 ‘풍이’님이 손수 테스트한 결과를 코드와 같이 올려주셨고( http://cafe.naver.com/ongameserver/3619 ), 왜 VC의 hash_map이 느린가에 대해 주말에 웹 서핑을 통해서 관련 글을 보았습니다( http://minjang.egloos.com/1983788
, http://junyoung.tistory.com/1 ).
오늘 출근 후 바로 직접 테스트 해 보았습니다. 또 VS 2008 SP1에서 추가된 TR1의 unordered_map도 추가했습니다.
테스트 환경은 Windows 2008 Server 64bit, Visual Studio 2008 Pro SP1 입니다.
결과는 CAtlMap이 가장 빠르고, STL hash_map은 생각보다 느리고, 특히 TR1의 unordered_map은 너무 느렸습니다.
VC의 hash_map이 gcc의 hash_map 보다 느리다고 하니 VC++의 TR1 보다도 boost의 unordered_map이 더 빠르지 않을까 라는 생각을 합니다. 혹시 이거 테스트 가능한 분들은 테스트 부탁합니다.
백 마디의 말보다 하나의 코드가 더 좋습니다. ^^
테스트한 코드도 올리니 틀린 부분이 있으면 말로만 이야기 하지 마시고 직접 코딩을 하여 결과를 보여 주시면 고맙겠습니다.
그림과 파일을 올리는 기능이 없어서 제 블로그 주소를 링크합니다.
http://blog.naver.com/jacking75/140062720030
MS MVP( VC++ )
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
-
- Posts: 398
- Joined: 2004-02-14 20:11
- Location: N거시기
- Contact:
-
- Posts: 149
- Joined: 2004-05-28 02:11
- Location: N모사
조금 다른 테스트입니다.
결과는 다음과 같습니다.
사양은 AMD 브리즈번 4800+, RAM 4G, vista x64입니다.
환경은 vc++ 2008 expresss sp1, win32입니다. 그래서 당연히! ATL은 테스트해보지 못했습니다.
누가 추가 좀 해 주셨으면 좋겠군요.
블로그를 닫았기 때문에, 코드를 여기 올립니다.
사양은 AMD 브리즈번 4800+, RAM 4G, vista x64입니다.
환경은 vc++ 2008 expresss sp1, win32입니다. 그래서 당연히! ATL은 테스트해보지 못했습니다.
누가 추가 좀 해 주셨으면 좋겠군요.
Code: Select all
D:\Backup\hashperfomancetest-jacking75\Release>HashPerfomanceTest.exe
insert - map: 5081, hash_map: 2712, unordered_map: 2976
loop - map: 430, hash_map: 473, unordered_map: 475
search - map: 306, hash_map: 81, unordered_map: 87
erase - map: 358, hash_map: 80, unordered_map: 90
result - map: -1495112807, hash_map: -1495112807, unordered_map: -1495112807
D:\Backup\hashperfomancetest-jacking75\Release>HashPerfomanceTest.exe
insert - map: 5162, hash_map: 2696, unordered_map: 2991
loop - map: 426, hash_map: 482, unordered_map: 474
search - map: 300, hash_map: 78, unordered_map: 91
erase - map: 363, hash_map: 82, unordered_map: 91
result - map: 288425469, hash_map: 288425469, unordered_map: 288425469
D:\Backup\hashperfomancetest-jacking75\Release>HashPerfomanceTest.exe
insert - map: 5114, hash_map: 2700, unordered_map: 2992
loop - map: 430, hash_map: 477, unordered_map: 474
search - map: 300, hash_map: 78, unordered_map: 89
erase - map: 361, hash_map: 81, unordered_map: 91
result - map: 574438481, hash_map: 574438481, unordered_map: 574438481
Code: Select all
#define _SECURE_SCL 0
#define _HAS_ITERATOR_DEBUGGING 0
#define _CRT_RAND_S
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <list>
#include <hash_map>
#include <bitset>
#include <algorithm>
#include <unordered_map>
#include <wtypes.h>
#include <mmsystem.h>
//#include <atlcoll.h>
#pragma warning(disable:4786)
#pragma comment (lib, "winmm.lib")
using namespace std;
using namespace stdext;
template<typename Cont>
void insert(Cont &cont, vector<DWORD> &val)
{
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
cont.insert(make_pair(*pos, *pos));
}
}
template<typename Cont>
DWORD loop(Cont &cont, int loop)
{
DWORD result = 0;
for (int i = 0; i < loop; ++i)
{
Cont::iterator pos = cont.begin(), end = cont.end();
for (; pos != end; ++pos)
{
result += pos->second;
}
}
return result;
}
template<typename Cont>
DWORD search(Cont &cont, vector<DWORD> &val)
{
DWORD result = 0;
vector<DWORD>::iterator pos = val.begin(), end = val.end();
Cont::iterator found, cend = cont.end();
for (; pos != end; ++pos)
{
found = cont.find(*pos);
if (cend != found)
{
result += found->second;
}
}
return result;
}
template<typename Cont>
void erase(Cont &cont, vector<DWORD> &val)
{
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
cont.erase(*pos);
}
}
struct gen_rand
{
DWORD operator () () const
{
unsigned int val;
rand_s(&val);
return static_cast<DWORD>(val);
}
};
void gen_by_val(vector<DWORD> &cont, vector<DWORD> &val, float hit_rate)
{
if (1.0f < hit_rate) { hit_rate = 1.0f; }
vector<DWORD>::iterator
dpos = cont.begin(),
dend = dpos + static_cast<int>(cont.size() * hit_rate);
unsigned int r;
for (; dpos != dend; ++dpos)
{
rand_s(&r);
*dpos = val[r & val.size()];
}
dend = cont.end();
for (; dpos != dend; ++dpos)
{
rand_s(&r);
*dpos = r;
}
}
int main(void)
{
const int MAX_LOOP = 10;
const int MAX_CONT = 3, MAX_TEST = 4, LL = 1;
std::vector<DWORD> v, s, e;
v.resize(500000, 0);
s.resize(50000, 0);
e.resize(50000, 0);
DWORD ticks[MAX_CONT][MAX_TEST], start, result[MAX_CONT];
memset(ticks, 0, sizeof(ticks));
memset(result, 0, sizeof(result));
for (int i = 0; i < MAX_LOOP; ++i)
{
map<DWORD, DWORD> map;
hash_map<DWORD, DWORD> hash;
std::tr1::unordered_map<DWORD, DWORD> unordered;
generate(v.begin(), v.end(), gen_rand());
gen_by_val(s, v, 0.5); // half hit, half miss
gen_by_val(e, v, 0.5); // half hit, half miss
start = timeGetTime(); insert(map, v); ticks[0][0] += timeGetTime() - start;
start = timeGetTime(); result[0] += loop(map, LL); ticks[0][1] += timeGetTime() - start;
start = timeGetTime(); result[0] += search(map, s); ticks[0][2] += timeGetTime() - start;
start = timeGetTime(); erase(map, e); ticks[0][3] += timeGetTime() - start;
start = timeGetTime(); insert(hash, v); ticks[1][0] += timeGetTime() - start;
start = timeGetTime(); result[1] += loop(hash, LL); ticks[1][1] += timeGetTime() - start;
start = timeGetTime(); result[1] += search(hash, s); ticks[1][2] += timeGetTime() - start;
start = timeGetTime(); erase(hash, e); ticks[1][3] += timeGetTime() - start;
start = timeGetTime(); insert(unordered, v); ticks[2][0] += timeGetTime() - start;
start = timeGetTime(); result[2] += loop(unordered, LL); ticks[2][1] += timeGetTime() - start;
start = timeGetTime(); result[2] += search(unordered, s); ticks[2][2] += timeGetTime() - start;
start = timeGetTime(); erase(unordered, e); ticks[2][3] += timeGetTime() - start;
}
/*
for (int i = 0; i < MAX_CONT; ++i)
{
for (int j = 0; j < MAX_TEST; ++j)
{
ticks[i][j] /= MAX_LOOP;
}
}
//*/
printf("insert - map:%12d, hash_map:%12d, unordered_map:%12d\n", ticks[0][0], ticks[1][0], ticks[2][0]);
printf("loop - map:%12d, hash_map:%12d, unordered_map:%12d\n", ticks[0][1], ticks[1][1], ticks[2][1]);
printf("search - map:%12d, hash_map:%12d, unordered_map:%12d\n", ticks[0][2], ticks[1][2], ticks[2][2]);
printf("erase - map:%12d, hash_map:%12d, unordered_map:%12d\n", ticks[0][3], ticks[1][3], ticks[2][3]);
printf("result - map:%12d, hash_map:%12d, unordered_map:%12d\n", result[0], result[1], result[2]);
return 0;
}
-
- Posts: 1035
- Joined: 2002-01-09 09:00
페쇄적인 카페입니다. -_-;;;;Xine wrote:폐쇄적으로 운영되는 카페가 아니시라면 카페 가입없이도 글을 읽을 수 있었으면 좋겠습니다 ^^
현업 서버 프로그래머만 가입 할 수 있습니다.
카페에 올라온 지식 중 좋은 것들은 다른 경로로 외부에 공개하려고 노력 중입니다.
MS MVP( VC++ )
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
-
- Posts: 1035
- Joined: 2002-01-09 09:00
참고로 오규태님이 32비트에서 boost의 tr1::unordered_map을 테스트 했는데 성능이 VC++보다 훨씬 더 좋았습니다.
지금까지 봐서는 MS에서 제공하는 표준 라이브러리는 성능이 좋지 못하고 어떤 의미로 다른 플랫폼에서 컴파일 할 수 있도록 하려고 만든 것 같습니다. -_-;
수요일에 MS에 모임이 있어서 가서 왜 이렇게 만들었는지 물어보려고 하는데 혹시 답변을 얻게 되면 공유 하겠습니다.
오규태님이 테스트한 결과입니다. 소스는 제 것에서 32비트 프로젝트에 unordered_map은 boost 것을 사용했습니다.
hash insert : 494
hash loop : 94
hash search : 78
hash erase : 118
unordered_map insert : 256
unordered_map loop : 7
unordered_map search : 40
unordered_map erase : 39
list insert : 222
list loop : 8
map insert : 512
map loop : 19
map search : 265
map erase : 355
atl insert : 59
atl loop : 9
atl search : 20
atl erase : 46
지금까지 봐서는 MS에서 제공하는 표준 라이브러리는 성능이 좋지 못하고 어떤 의미로 다른 플랫폼에서 컴파일 할 수 있도록 하려고 만든 것 같습니다. -_-;
수요일에 MS에 모임이 있어서 가서 왜 이렇게 만들었는지 물어보려고 하는데 혹시 답변을 얻게 되면 공유 하겠습니다.
오규태님이 테스트한 결과입니다. 소스는 제 것에서 32비트 프로젝트에 unordered_map은 boost 것을 사용했습니다.
hash insert : 494
hash loop : 94
hash search : 78
hash erase : 118
unordered_map insert : 256
unordered_map loop : 7
unordered_map search : 40
unordered_map erase : 39
list insert : 222
list loop : 8
map insert : 512
map loop : 19
map search : 265
map erase : 355
atl insert : 59
atl loop : 9
atl search : 20
atl erase : 46
MS MVP( VC++ )
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
sphawk님의 테스트코드에 CAtlMap을 추가한 결과입니다.
테스트 환경은 펜티엄4 3.0G, RAM 1G, Win XP, VS 2008 SP1 입니다.
테스트 환경은 펜티엄4 3.0G, RAM 1G, Win XP, VS 2008 SP1 입니다.
Code: Select all
c:\work\projects\hashperfomancetest\Release>hashperfomancetest.exe
insert - map: 11016, hash_map: 6063, unordered_map: 6578, atl: 3748
loop - map: 546, hash_map: 483, unordered_map: 500, atl: 783
search - map: 576, hash_map: 156, unordered_map: 188, atl: 48
erase - map: 830, hash_map: 296, unordered_map: 265, atl: 124
result - map: 1689559733, hash_map: 1689559733, unordered_map: 1689559733, atl: 1689559733
c:\work\projects\hashperfomancetest\Release>hashperfomancetest.exe
insert - map: 10971, hash_map: 5984, unordered_map: 6577, atl: 3796
loop - map: 546, hash_map: 532, unordered_map: 515, atl: 751
search - map: 592, hash_map: 171, unordered_map: 173, atl: 61
erase - map: 782, hash_map: 283, unordered_map: 266, atl: 142
result - map: -842961530, hash_map: -842961530, unordered_map: -842961530, atl: -842961530
sphawk님의 테스트코드를 약간 수정하고 CAtlMap을 추가한 결과입니다.
테스트 환경은 펜티엄4 3.0G, RAM 1G, Win XP, VS 2008 SP1 입니다.
할당자를 Loki 0.1.7의 LokiAllocator로 변경한 결과입니다.
테스트에 사용한 소스코드입니다.
테스트 환경은 펜티엄4 3.0G, RAM 1G, Win XP, VS 2008 SP1 입니다.
Code: Select all
c:\work\projects\hashperfomancetest\Release>hashperfomancetest.exe
insert - map: 11016, hash_map: 6063, unordered_map: 6578, atl: 3748
loop - map: 546, hash_map: 483, unordered_map: 500, atl: 783
search - map: 576, hash_map: 156, unordered_map: 188, atl: 48
erase - map: 830, hash_map: 296, unordered_map: 265, atl: 124
result - map: 1689559733, hash_map: 1689559733, unordered_map: 1689559733, atl: 1689559733
c:\work\projects\hashperfomancetest\Release>hashperfomancetest.exe
insert - map: 10971, hash_map: 5984, unordered_map: 6577, atl: 3796
loop - map: 546, hash_map: 532, unordered_map: 515, atl: 751
search - map: 592, hash_map: 171, unordered_map: 173, atl: 61
erase - map: 782, hash_map: 283, unordered_map: 266, atl: 142
result - map: -842961530, hash_map: -842961530, unordered_map: -842961530, atl: -842961530
Code: Select all
c:\work\projects\hashperfomancetest\Release>hashperfomancetest.exe
insert - map: 6078, hash_map: 2735, unordered_map: 2984, atl: 2547
loop - map: 546, hash_map: 545, unordered_map: 530, atl: 764
search - map: 376, hash_map: 111, unordered_map: 110, atl: 79
erase - map: 469, hash_map: 80, unordered_map: 140, atl: 32
result - map: -1658514180, hash_map: -1658514180, unordered_map: -1658514180, atl: -1658514180
c:\work\projects\hashperfomancetest\Release>hashperfomancetest.exe
insert - map: 5892, hash_map: 2689, unordered_map: 2906, atl: 2579
loop - map: 515, hash_map: 547, unordered_map: 580, atl: 751
search - map: 359, hash_map: 78, unordered_map: 77, atl: 31
erase - map: 499, hash_map: 110, unordered_map: 125, atl: 93
result - map: 632774745, hash_map: 632774745, unordered_map: 632774745, atl: 632774745
Code: Select all
#define _SECURE_SCL 0
#define _HAS_ITERATOR_DEBUGGING 0
#define _CRT_RAND_S
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <list>
#include <hash_map>
#include <bitset>
#include <algorithm>
#include <unordered_map>
#include <wtypes.h>
#include <mmsystem.h>
#include <atlcoll.h>
#include <Loki/Allocator.h>
#pragma warning(disable:4786)
#pragma comment (lib, "winmm.lib")
using namespace std;
using namespace stdext;
template<typename Cont>
void insert(Cont &cont, vector<DWORD> &val)
{
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
cont.insert(make_pair(*pos, *pos));
}
}
void insert(CAtlMap<DWORD, DWORD>& cont, vector<DWORD>& val)
{
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
cont.SetAt(*pos, *pos);
}
}
template<typename Cont>
DWORD loop(Cont &cont, int loop)
{
DWORD result = 0;
for (int i = 0; i < loop; ++i)
{
Cont::iterator pos = cont.begin(), end = cont.end();
for (; pos != end; ++pos)
{
result += pos->second;
}
}
return result;
}
DWORD loop(CAtlMap<DWORD, DWORD>& cont, int loop)
{
DWORD result = 0;
for (int i = 0; i < loop; ++i)
{
CAtlMap<DWORD, DWORD>::CPair* pair = NULL;
POSITION pos = cont.GetStartPosition();
while (pos)
{
pair = cont.GetNext(pos);
result += pair->m_value;
}
}
return result;
}
template<typename Cont>
DWORD search(Cont &cont, vector<DWORD> &val)
{
DWORD result = 0;
vector<DWORD>::iterator pos = val.begin(), end = val.end();
Cont::iterator found, cend = cont.end();
for (; pos != end; ++pos)
{
found = cont.find(*pos);
if (cend != found)
{
result += found->second;
}
}
return result;
}
DWORD search(CAtlMap<DWORD, DWORD>& cont, vector<DWORD>& val)
{
DWORD result = 0;
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
CAtlMap<DWORD, DWORD>::CPair* pair = cont.Lookup(*pos);
if (pair != NULL)
{
result += pair->m_value;
}
}
return result;
}
template<typename Cont>
void erase(Cont &cont, vector<DWORD> &val)
{
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
cont.erase(*pos);
}
}
void erase(CAtlMap<DWORD, DWORD>& cont, vector<DWORD>& val)
{
vector<DWORD>::iterator pos = val.begin(), end = val.end();
for (; pos != end; ++pos)
{
cont.RemoveKey(*pos);
}
}
struct gen_rand
{
DWORD operator () () const
{
unsigned int val;
rand_s(&val);
return static_cast<DWORD>(val);
}
};
void gen_by_val(vector<DWORD> &cont, vector<DWORD> &val, float hit_rate)
{
if (1.0f < hit_rate) { hit_rate = 1.0f; }
vector<DWORD>::iterator
dpos = cont.begin(),
dend = dpos + static_cast<int>(cont.size() * hit_rate);
unsigned int r;
for (; dpos != dend; ++dpos)
{
rand_s(&r);
*dpos = val[r % val.size()];
}
dend = cont.end();
for (; dpos != dend; ++dpos)
{
rand_s(&r);
*dpos = r;
}
}
int main(void)
{
const int MAX_LOOP = 10;
const int MAX_CONT = 4, MAX_TEST = 4, LL = 1;
std::vector<DWORD> v, s, e;
v.resize(500000, 0);
s.resize(50000, 0);
e.resize(50000, 0);
DWORD ticks[MAX_CONT][MAX_TEST], start, result[MAX_CONT];
memset(ticks, 0, sizeof(ticks));
memset(result, 0, sizeof(result));
for (int i = 0; i < MAX_LOOP; ++i)
{
// typedef std::allocator<pair<const DWORD, DWORD> > Alloc;
typedef Loki::LokiAllocator<pair<const DWORD, DWORD> > Alloc;
generate(v.begin(), v.end(), gen_rand());
gen_by_val(s, v, 0.5); // half hit, half miss
gen_by_val(e, v, 0.5); // half hit, half miss
{
map<DWORD, DWORD, less<DWORD>, Alloc> map;
start = timeGetTime(); insert(map, v); ticks[0][0] += timeGetTime() - start;
start = timeGetTime(); result[0] += loop(map, LL); ticks[0][1] += timeGetTime() - start;
start = timeGetTime(); result[0] += search(map, s); ticks[0][2] += timeGetTime() - start;
start = timeGetTime(); erase(map, e); ticks[0][3] += timeGetTime() - start;
}
{
hash_map<DWORD, DWORD, hash_compare<DWORD, less<DWORD> >, Alloc> hash;
start = timeGetTime(); insert(hash, v); ticks[1][0] += timeGetTime() - start;
start = timeGetTime(); result[1] += loop(hash, LL); ticks[1][1] += timeGetTime() - start;
start = timeGetTime(); result[1] += search(hash, s); ticks[1][2] += timeGetTime() - start;
start = timeGetTime(); erase(hash, e); ticks[1][3] += timeGetTime() - start;
}
{
std::tr1::unordered_map<DWORD, DWORD, std::tr1::hash<DWORD>, std::equal_to<DWORD>, Alloc> unordered;
start = timeGetTime(); insert(unordered, v); ticks[2][0] += timeGetTime() - start;
start = timeGetTime(); result[2] += loop(unordered, LL); ticks[2][1] += timeGetTime() - start;
start = timeGetTime(); result[2] += search(unordered, s); ticks[2][2] += timeGetTime() - start;
start = timeGetTime(); erase(unordered, e); ticks[2][3] += timeGetTime() - start;
}
{
CAtlMap<DWORD, DWORD> atl;
start = timeGetTime(); insert(atl, v); ticks[3][0] += timeGetTime() - start;
start = timeGetTime(); result[3] += loop(atl, LL); ticks[3][1] += timeGetTime() - start;
start = timeGetTime(); result[3] += search(atl, s); ticks[3][2] += timeGetTime() - start;
start = timeGetTime(); erase(atl, e); ticks[3][3] += timeGetTime() - start;
}
}
printf("insert - map:%12d, hash_map:%12d, unordered_map:%12d, atl:%12d \n", ticks[0][0], ticks[1][0], ticks[2][0], ticks[3][0]);
printf("loop - map:%12d, hash_map:%12d, unordered_map:%12d, atl:%12d \n", ticks[0][1], ticks[1][1], ticks[2][1], ticks[3][1]);
printf("search - map:%12d, hash_map:%12d, unordered_map:%12d, atl:%12d \n", ticks[0][2], ticks[1][2], ticks[2][2], ticks[3][2]);
printf("erase - map:%12d, hash_map:%12d, unordered_map:%12d, atl:%12d \n", ticks[0][3], ticks[1][3], ticks[2][3], ticks[3][3]);
printf("result - map:%12d, hash_map:%12d, unordered_map:%12d, atl:%12d \n", result[0], result[1], result[2], result[3]);
return 0;
}
-
- Posts: 149
- Joined: 2004-05-28 02:11
- Location: N모사
테스트 올려주셔서 감사합니다. ^^;
내일 회사 가면 짬 내서 ATL에도 할당자를 적용해 볼까;; 했었는데
http://msdn.microsoft.com/en-us/library ... S.80).aspx
을 보니 할당자를 따로 적용할 수는 없는 듯 하군요.
자체적으로 뭔가 할당 소멸 관련하여 최적화 하는 것은 없는지 한번 살펴봐야겠군요.
(자체적으로 메모리 풀을 둔다던가...)
내일 회사 가면 짬 내서 ATL에도 할당자를 적용해 볼까;; 했었는데
http://msdn.microsoft.com/en-us/library ... S.80).aspx
을 보니 할당자를 따로 적용할 수는 없는 듯 하군요.
자체적으로 뭔가 할당 소멸 관련하여 최적화 하는 것은 없는지 한번 살펴봐야겠군요.
(자체적으로 메모리 풀을 둔다던가...)
-
- Posts: 149
- Joined: 2004-05-28 02:11
- Location: N모사
윗분 말씀대로, 자체적으로 할당 최적화를 하는군요.
템플릿 멤버만 보고 없다고 오해했군요.
http://msdn.microsoft.com/en-us/library ... S.80).aspx
nBlockSize가 그 역할을 하는 듯 합니다.
템플릿 멤버만 보고 없다고 오해했군요.
http://msdn.microsoft.com/en-us/library ... S.80).aspx
nBlockSize가 그 역할을 하는 듯 합니다.
-
- Posts: 1314
- Joined: 2003-03-04 10:21
- Contact:
Code: Select all
class HashCompare
{
public:
enum
{
bucket_size = 4,
min_buckets = 1024,
};
size_t operator()(const int _Key) const
{
return (size_t)_Key;
}
bool operator()(const int _Key1, const int _Key2) const
{
return _Key1 < _Key2;
}
};
hash_map<DWORD, DWORD, HashCompare> hash;
search 랑 erase 속도는 빨라지네요
문제는 네이밍-_-;
레퍼런스:
http://junyoung.tistory.com/1
ps.
bucket_size 의 사용용도는 이해불가-_-
빗자루네 http://www.myevan.net >_<b
-
- Posts: 1314
- Joined: 2003-03-04 10:21
- Contact:
Code: Select all
class HashCompare
{
public:
enum
{
bucket_size = 4,
min_buckets = 1024,
};
size_t operator()(const int _Key) const
{
return (size_t)_Key;
}
bool operator()(const int _Key1, const int _Key2) const
{
return _Key1 < _Key2;
}
};
#include <boost/pool/pool_alloc.hpp>
typedef boost::fast_pool_allocator<int, boost::default_user_allocator_new_delete, boost::details::pool::null_mutex> Allocactor;
hash_map<DWORD, DWORD, PackHashCompare, Allocactor> hash;
Code: Select all
insert - map: 5050, hash_map: 7092, unordered_map: 0
loop - map: 389, hash_map: 429, unordered_map: 0
search - map: 273, hash_map: 79, unordered_map: 0
erase - map: 339, hash_map: 76, unordered_map: 0
result - map: -1764325575, hash_map: -1764325575, unordered_map: 0
Code: Select all
insert - map: 5596, hash_map: 2106, unordered_map: 0
loop - map: 390, hash_map: 334, unordered_map: 0
search - map: 258, hash_map: 43, unordered_map: 0
erase - map: 321, hash_map: 49, unordered_map: 0
result - map: 715496236, hash_map: 715496236, unordered_map: 0
빗자루네 http://www.myevan.net >_<b
-
- Posts: 34
- Joined: 2006-11-29 02:11
비교를 하기 전에 해쉬함수와 채우기 비율이 동일하게 통제되어야 하지 않나요?
위가 CAtlMap의 해쉬 함수고 밑에가 VC 9.0 hash_map 의 해쉬 functor입니다.
버킷 인덱스를 구할 때는 CAtlMfc는 하드코딩된 소수로 나머지 연산을 한번 수행하고 hash_map도 별반 다르지는 않던데요..
key값이 랜덤하게 구해졌기는 하지만 특정 범위 내에서 고른 분포를 가지는 DWORD값이라 생각할 수 있기 때문에 mfc는 단순하지만 질적으로 괜찮은 해쉬 함수를 사용한 셈이 아닐까요?
채우기 비율은 mfc의 경우 insert 기본으로 2.25를 사용하지만 hash_map은 4를 쓰고 있기 때문에 상한이 정해진 경우 mfc가 유리할테구요..
하지만 위분들이 올려주신 결과에서도 나타났지만 가장 큰 병목은 메모리 할당같습니다.
hash_map의 경우 vector와 list 두 개의 컨테이너를 사용하기 땜에 rehash가 일어날 때 상당히 치명적일 듯 하네요.
stl의 구현은 얼핏 봐서는 상당히 비효율적일 것만 같단 말이죠..
그럼에도 불구하고 얼로케이터만 바꿔도 꽤 선전한다는 점, 표준 인터페이스를 가진다는 점에서 전 stl쪽에 한표~
Code: Select all
template<typename>
class CDefaultHashTraits
{
public:
static ULONG Hash( const T& element ) throw()
{
return( ULONG( ULONG_PTR( element ) ) );
}
};
Code: Select all
size_t operator()(const _Kty& _Keyval) const
{ // hash _Keyval to size_t value by pseudorandomizing transform
long _Quot = (long)(hash_value(_Keyval) & LONG_MAX);
ldiv_t _Qrem = ldiv(_Quot, 127773);
_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
if (_Qrem.rem < 0)
_Qrem.rem += LONG_MAX;
return ((size_t)_Qrem.rem);
}
버킷 인덱스를 구할 때는 CAtlMfc는 하드코딩된 소수로 나머지 연산을 한번 수행하고 hash_map도 별반 다르지는 않던데요..
key값이 랜덤하게 구해졌기는 하지만 특정 범위 내에서 고른 분포를 가지는 DWORD값이라 생각할 수 있기 때문에 mfc는 단순하지만 질적으로 괜찮은 해쉬 함수를 사용한 셈이 아닐까요?
채우기 비율은 mfc의 경우 insert 기본으로 2.25를 사용하지만 hash_map은 4를 쓰고 있기 때문에 상한이 정해진 경우 mfc가 유리할테구요..
하지만 위분들이 올려주신 결과에서도 나타났지만 가장 큰 병목은 메모리 할당같습니다.
hash_map의 경우 vector와 list 두 개의 컨테이너를 사용하기 땜에 rehash가 일어날 때 상당히 치명적일 듯 하네요.
stl의 구현은 얼핏 봐서는 상당히 비효율적일 것만 같단 말이죠..
그럼에도 불구하고 얼로케이터만 바꿔도 꽤 선전한다는 점, 표준 인터페이스를 가진다는 점에서 전 stl쪽에 한표~
-
- Posts: 307
- Joined: 2005-12-13 11:50
얼마나 빨라야 빠르고 얼마나 느려야 너무 느린걸까요? 위의 테스트 결과는 (최초에 jacking님이 테스트하신 것) 백만번 연속 작업의 결과입니다. 맵(해시 포함)을 사용하기로 결정했다는건 삽입/삭제보다는 검색이 주가 된다는 얘기겠죠(그래서 일단 삽입을 예외로 치면...)cycle277 wrote:STL 관련 이슈가 될때마다 늘 궁금했던 사항인데요,
현업에서 MS stl 그대로 쓰시는 분들이 많은가요?
전 관련해서는 stlport가 ms보다 눈에 보일만큼 차이나게 빠르다고 해서 ms stl의 경우는 전혀 사용하지 않고 있는데요,
실무자분들 의견이 좀 듣고 싶네요;
위의 테스트 경우도 그렇고 ㅎㅎ
성능 비율로 보면 ATL 구현에 비해 3~4배의 차이가 나지만 시간으로 보면 해시 검색의 경우 100ms의 차이도 나지 않습니다. 100만번에 100ms요. 물론 도메인에 따라 이 100ms의 차이가 엄청난 결과를 만들 수도 있습니다. 그러나 게임에서는 무시할만하다고 봅니다.
뭘 쓰던 대세에는 영향을 미치지않는다에 한표던집니다. 물론 프로그래머로서 더 나은 성능을 갈구해야는 건 맞지만 MS 구현(dinkumware의 구현이겠죠)을 멀리할정도는 아닙니다. 느린건 대단히 상대적이거든요.
Last edited by 조성경 on 2009-02-12 10:47, edited 1 time in total.
더 이상 이 곳에 오지 않습니다.