STL map, SLT hash_map, CAtlMap, TR1 unordered_map 성능 테스트

프로그래밍 일반에 관한 포럼입니다.

Moderator: 류광

Locked
jacking
Posts: 1035
Joined: 2002-01-09 09:00

STL map, SLT hash_map, CAtlMap, TR1 unordered_map 성능 테스트

Post by jacking »

예전에 누군가를 통해서 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
MS MVP( VC++ )
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:

Post by 해키스트 »

우옹 이런 모임이 있었군요. 가입 해야겠군용
Quitters no win, winners no quit.
Xine
Posts: 253
Joined: 2002-08-12 00:37

Post by Xine »

폐쇄적으로 운영되는 카페가 아니시라면 카페 가입없이도 글을 읽을 수 있었으면 좋겠습니다 ^^
이덕희
sphawk
Posts: 149
Joined: 2004-05-28 02:11
Location: N모사

조금 다른 테스트입니다.

Post by sphawk »

결과는 다음과 같습니다.
사양은 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;
}

jacking
Posts: 1035
Joined: 2002-01-09 09:00

Post by jacking »

Xine wrote:폐쇄적으로 운영되는 카페가 아니시라면 카페 가입없이도 글을 읽을 수 있었으면 좋겠습니다 ^^
페쇄적인 카페입니다. -_-;;;;
현업 서버 프로그래머만 가입 할 수 있습니다.

카페에 올라온 지식 중 좋은 것들은 다른 경로로 외부에 공개하려고 노력 중입니다.
MS MVP( VC++ )
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
jacking
Posts: 1035
Joined: 2002-01-09 09:00

Post by jacking »

참고로 오규태님이 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 MVP( VC++ )
Twitter : jacking75
블로그 1: http://jacking.tistory.com
블로그 2: http://blog.naver.com/jacking75
스프링노트 : http://jacking.springnote.com
비회원

Post by 비회원 »

sphawk님의 테스트코드에 CAtlMap을 추가한 결과입니다.
테스트 환경은 펜티엄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
Posts: 149
Joined: 2004-05-28 02:11
Location: N모사

Post by sphawk »

가능하면 소스도 올려 주셨으면 좋겠습니다. CAtlMap부분만 올려주셔도 좋습니다.
비회원

Post by 비회원 »

sphawk님의 테스트코드를 약간 수정하고 CAtlMap을 추가한 결과입니다.
테스트 환경은 펜티엄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
할당자를 Loki 0.1.7의 LokiAllocator로 변경한 결과입니다.

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;
}
sphawk
Posts: 149
Joined: 2004-05-28 02:11
Location: N모사

Post by sphawk »

테스트 올려주셔서 감사합니다. ^^;

내일 회사 가면 짬 내서 ATL에도 할당자를 적용해 볼까;; 했었는데
http://msdn.microsoft.com/en-us/library ... S.80).aspx
을 보니 할당자를 따로 적용할 수는 없는 듯 하군요.

자체적으로 뭔가 할당 소멸 관련하여 최적화 하는 것은 없는지 한번 살펴봐야겠군요.
(자체적으로 메모리 풀을 둔다던가...)
비회원

Post by 비회원 »

ATL의 컨테이너들은 보통 생성자에서 할당하는 메모리 블럭의 크기를 조절할 수 있습니다.
sphawk
Posts: 149
Joined: 2004-05-28 02:11
Location: N모사

Post by sphawk »

윗분 말씀대로, 자체적으로 할당 최적화를 하는군요.
템플릿 멤버만 보고 없다고 오해했군요.

http://msdn.microsoft.com/en-us/library ... S.80).aspx
nBlockSize가 그 역할을 하는 듯 합니다.
youngdie
Posts: 4
Joined: 2007-02-20 16:17

Post by youngdie »

CAtlMap에서는 InitHashTable이란 함수를 이용해서 미리 메모리를 잡아두고 분포도를 늘리는 것도 성능향상에 좋은 방법 중에 하나죠
- 신영욱
myevan
Posts: 1314
Joined: 2003-03-04 10:21
Contact:

Post by myevan »

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; 
min_bucket 이 해쉬 테이블 크기 늘리는 방식인데...
search 랑 erase 속도는 빨라지네요

문제는 네이밍-_-;

레퍼런스:
http://junyoung.tistory.com/1



ps.
bucket_size 의 사용용도는 이해불가-_-
빗자루네 http://www.myevan.net >_<b
myevan
Posts: 1314
Joined: 2003-03-04 10:21
Contact:

Post by myevan »

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
namenu
Posts: 34
Joined: 2006-11-29 02:11

Post by namenu »

비교를 하기 전에 해쉬함수와 채우기 비율이 동일하게 통제되어야 하지 않나요?

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);
		}
위가 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쪽에 한표~
cycle277
Posts: 4
Joined: 2007-06-19 18:47
Location: 비밀

Post by cycle277 »

STL 관련 이슈가 될때마다 늘 궁금했던 사항인데요,

현업에서 MS stl 그대로 쓰시는 분들이 많은가요?

전 관련해서는 stlport가 ms보다 눈에 보일만큼 차이나게 빠르다고 해서 ms stl의 경우는 전혀 사용하지 않고 있는데요,

실무자분들 의견이 좀 듣고 싶네요;

위의 테스트 경우도 그렇고 ㅎㅎ
조성경
Posts: 307
Joined: 2005-12-13 11:50

Post by 조성경 »

cycle277 wrote:STL 관련 이슈가 될때마다 늘 궁금했던 사항인데요,

현업에서 MS stl 그대로 쓰시는 분들이 많은가요?

전 관련해서는 stlport가 ms보다 눈에 보일만큼 차이나게 빠르다고 해서 ms stl의 경우는 전혀 사용하지 않고 있는데요,

실무자분들 의견이 좀 듣고 싶네요;

위의 테스트 경우도 그렇고 ㅎㅎ
얼마나 빨라야 빠르고 얼마나 느려야 너무 느린걸까요? 위의 테스트 결과는 (최초에 jacking님이 테스트하신 것) 백만번 연속 작업의 결과입니다. 맵(해시 포함)을 사용하기로 결정했다는건 삽입/삭제보다는 검색이 주가 된다는 얘기겠죠(그래서 일단 삽입을 예외로 치면...)

성능 비율로 보면 ATL 구현에 비해 3~4배의 차이가 나지만 시간으로 보면 해시 검색의 경우 100ms의 차이도 나지 않습니다. 100만번에 100ms요. 물론 도메인에 따라 이 100ms의 차이가 엄청난 결과를 만들 수도 있습니다. 그러나 게임에서는 무시할만하다고 봅니다.

뭘 쓰던 대세에는 영향을 미치지않는다에 한표던집니다. 물론 프로그래머로서 더 나은 성능을 갈구해야는 건 맞지만 MS 구현(dinkumware의 구현이겠죠)을 멀리할정도는 아닙니다. 느린건 대단히 상대적이거든요.
Last edited by 조성경 on 2009-02-12 10:47, edited 1 time in total.
더 이상 이 곳에 오지 않습니다.
xster
Posts: 214
Joined: 2006-10-30 10:56

Post by xster »

현업이라하시면 출시에 준하는 대 인원을 받는 서버를 말씀하시는 건가요?
저희같은 경우는 아직 개발 중인데 ms stl 을 그대로 사용하고 있습니다.
vs2008 에 들어가 있는 stl 사용 중입니다.

실제 대규모 인원을 받는 단계에 가기 전에 프로파일링해서 속도에 문제가 되는
부분을 해결하고 갈 예정입니다만 그때도 stl 에서 문제가 안 된다면 그냥 갈 생각입니다.
비회원

Post by 비회원 »

컨테이너 선언 할 때 Allocator 지정하면
성능 아주 좋아 집니다.
Locked