Tweet  Follow @esstory

 

지난 몇 주간 유지보수중인 프로그램의 성능 문제 때문에 Visual Studio 2005/2008 의 Profiler 덕을 많이 봤습니다.

Visual Studio 2005의 Profiler 로 성능에 문제가 있는 함수를 하나씩 파고 들면서 거기서 가장 많은 시간을 소비하거나, 쓸데 없이 많이 호출되는 함수들을 개선해 나가는 식으로 진행했는데요.

 

작업을 하다 보니 STL 의 map 을 이용해서 insert 하고, find 하는 코드들이 시간 소비가 많다는 것을 확인했습니다.

 

워낙 많이 호출되다 보니 그렇겠거니 하고 일단 쉽게 수정 가능한 다른 부분들을 먼저 수정해서 큰 고비는 넘겼습니다.

 

그래도 마음 속으로는 계속 map 에 대한 성능부분이 마음에 걸려 Visual Studio 에서 제공하는 다른 map 들과 간단하게 성능을 비교해 봤습니다.

성능 비교에 쓰인 3가지 클래스입니다.

 

std:map  - C++ 표준에서 제공하는 일반적인 map, 바이너리 트리 검색

CAtlMap – ATL 에서 제공하는 map, 해시 검색

CRBMap – ATL 에서 제공하는 map, 바이너리 트리 검색

 

구조적으로 STL 의 map 과 ATL 의 CRBMap 는 비슷한 방식으로 가지고 있어 성능도 비슷할 것으로 보였지만, 실제 결과는 상당한 성능 차이가 있었습니다.
 

일단 대상으로 삼은 <Key, Value> 조합은 <LPCTSTR, TEST_DATA> 입니다.

문자열을 키로 삼아 원하는 구조체를 찾는 일반적인 방식을 사용했습니다.

참고로 TEST_DATA 구조체는

struct TEST_DATA

{

           long lData;

           wstring sData;

};

와 같이 임의로 정의했습니다.

 

테스트를 위해 사용할 오늘의 컨테이너들을 소개합니다.

 

map<LPCTSTR, TEST_DATA> m_mapData;

CAtlMap <LPCTSTR, TEST_DATA> m_atlmapData;

CRBMap <LPCTSTR, TEST_DATA> m_RBmapData;

Insert할 데이터의 공정성(?)을 위해 키가 되는 문자열은 일방향적인 삽입이 일어나지 않도록 하기 위해서 rand() 함수를 통해 문자열로 변환했습니다. 아래는 map 에 insert 를 위해서 vector 에 랜덤한 문자열을 만들어 저장하는 코드입니다. vector<> 에 저장된 데이터들은 순서대로 map 에 추가하는 방식을 사용했습니다.

 

for (int i = 0; i < MAX_ELEMENT; i++)

{

             data.lData = rand();

             _stprintf_s  (szFormat, _countof(szFormat), _T("%010d%i\n"), data.lData,i);

             data.sData = szFormat;   

            

             m_vtKey.push_back( make_pair(data.sData,data) );

}

 

1.     Insert 비교

10,000 개  ~ 100,000 개의 TEST_DATA 를 Insert 하는 시험을 했습니다. 3가지 모두 동일한 조건으로 추가했고 추가를 위해 사용한 코드는 아래와 같습니다.

 

// STL MAP INSERT

DWORD dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           m_mapData.insert(make_pair(itV->first.c_str(), itV->second) );

}

TRACE("%d,", timeGetTime() - dwStart);

 

// ATL MAP INSERT

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           m_atlmapData.SetAt(itV->first.c_str(), itV->second);

}

TRACE("%d,", timeGetTime() - dwStart);

 

// RBMAP INSERT

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           m_RBmapData.SetAt(itV->first.c_str(), itV->second);

}

TRACE("%d,", timeGetTime() - dwStart);

 

위와 같은 코드로 데이터를 10,000 ~ 100,0000 개까지 map 에 Insert 하는 동안 걸린 시간은 아래 차트와 같았습니다.

 

 

 

X 축은 Insert 횟수를, Y 축은 X 축의 횟수 만큼 Insert를 했을 때 걸린 시간을 의미합니다.

그림을 대충 봐도 알 수 있듯이 STL map 과 CAtlMap 의 Insert 시간은 상당한 차이를 보입니다. 게다가 비슷한 방식의 CRBMap 과도 상당한 차이가 나는 것을 볼 수 있습니다. 이러한 차이는 데이터가 늘어날 수록 극명해 짐을 알 수 있었습니다.

 

2.     Find 비교

Insert 와 같은 방식으로 이번에는 각각의 map에 들어 있는 모든 항목을 하나씩 찾는데 걸린 시간을 비교했습니다.

비교에 사용된 코드입니다.

 

// STL MAP FIND

dwStart = timeGetTime();

// find 성능분석

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           it = m_mapData.find(itV->first.c_str());

           if (it == m_mapData.end())

                     TRACE(_T("%s\n"), itV->first.c_str());

}

TRACE("%d,", timeGetTime() - dwStart);

 

// ATL MAP FIND

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           pPair1 = m_atlmapData.Lookup(itV->first.c_str());

           if (pPair1 == NULL)

                     TRACE(_T("%s\n"), itV->first.c_str());

}

TRACE("%d,", timeGetTime() - dwStart);

 

// RBMAP FIND

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           pPair2 = m_RBmapData.Lookup(itV->first.c_str());

           if (pPair2 == NULL)

                     TRACE(_T("%s\n"), itV->first.c_str());

}

TRACE("%d,", timeGetTime() - dwStart);

 

비교 차트입니다. 바이너리 검색보다 역시 해시 검색에서 확실히 더 나은 성능을 보여주는 것을 알 수 있습니다.  그리고 조금 놀란 부분은 같은 바이너리 검색으로 알고 있는 STL 의 map 과 CRBMap 이 상당한 성능 차이를 보인다는 점이었습니다.  사실 1회성인 insert 에서 보다, 그 빈도 수가 훨씬 많은 편인 find 함수에서 이 정도의 격차가 난다는것만으로도 STL::map 구현에서 성능적인 문제들이 많이 간과되었다고 밖에 생각할 수가 없었습니다. (물론 Visual Studio 2008 의 구현에 국한 된 테스트라 다른 컴파일러에 대한 얘기로 확대 해석 할 수는 없습니다)

 

3.     Find & Erase 비교

일반적으로 Find 이후에 Erase 를 하는 경우가 많을 거라 생각되어서 Find 와 Erase 를 함께 사용하여 수행 시간을 측정했습니다.

// STL MAP ERASE

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           it = m_mapData.find(itV->first.c_str());

           if (it != m_mapData.end())

                     m_mapData.erase(it);

}

TRACE("%d,", timeGetTime() - dwStart);

 

// ATL MAP ERASE

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           m_atlmapData.RemoveKey(itV->first.c_str());

}

TRACE("%d,", timeGetTime() - dwStart);

 

// RBMAP ERASE

dwStart = timeGetTime();

for (itV = m_vtKey.begin(); itV != m_vtKey.end(); ++itV)

{

           m_RBmapData.RemoveKey(itV->first.c_str());

}

TRACE("%d", timeGetTime() - dwStart);

 

 

Erase 부분도 역시 CAtlMap 의 압승입니다. CRBMap 과 STL map 은 어느 정도 비슷한 시간을 보였습니다.

 

혹시나 키가 문자열이 아닌 숫자라면 어떨까요.
이번에는 키를 숫자로 설정해서 <long, TEST_DATA> 로 컨테이너를 만들어 비교해 봤습니다.

사용된 컨테이너들입니다.

 

map<long, TEST_DATA> m_mapData2;

CAtlMap <long, TEST_DATA> m_atlmapData2;

CRBMap <long, TEST_DATA> m_RBmapData2;

 

코드는 거의 중복이기 때문에 생략하겠습니다.

1.     Insert

 

2.     Find

 

3.     Find & Erase

 

 

위 두 가지 예는 데이터가 너무 많은 감이 있어 데이터를 1,000 ~ 10,000 개 정도로 줄여서 비교해 봤습니다. <LPCTSTR, TEST_DATA> 를 사용했습니다.

 

1.     insert

2.     Find

 

3.     Find & Erase

 

데이터가 적은 경우에도 STL 의 map 이 Insert 와 Find 에 가장 많은 시간이 소요됐고, Erase 부분에서는 오히려 RBMap 이 가장 많은 시간이 걸린 것으로 조사됐습니다.

 

그리 어렵지 않은 테스트로 얻은 교훈은

 

- Visual Studio의 STL 의 map 구현이 뭔가 최적화 되지 않은 느낌입니다.

- 일반적인 경우에는 상관없겠으나 성능이 중요한 이슈인 프로그램에서는 CAtlMap 이나 다른 대안이 될만한 Map 을 찾거나, 가장 최적화된 Map 을 직접 만들어야 합니다.

 

그 동안 좀 무분별하게 STL MAP 을 선호하는 편이었는데 최근의 프로파일링 결과도 그렇고, 테스트 결과도 그렇고 좀 더 성능에 신경 써야겠다는 생각이 들었습니다.

조금 다른 얘기이긴 하지만 STL 자료구조의 성능 관련 아래 글도 읽어 볼만 합니다.

STL 자료구조 성능테스트: 포인터? 객체?