CMap vs std::map

C++의 자료 구조 중에 map이라는 것이 있다.

key와 value를 한 쌍으로 저장하며, key의 중복을 허용하지 않고 정렬하여 저장하는 자료구조이다.

아는 사람은 다 아는 내용이니 map에 대한 설명은 여기까지만 하고...

 

MFC에서는 이러한 경우를 처리하기 위해 CMap이라는 클래스를 만들어두었다.

또한 STL에서는 map과 unordered_map을 구현하여 유사한 기능을 수행하게 해두었다.

 

여기서 Windows 환경에서 어느 쪽의 구현이 더 빠른가 하는 점이 궁금해졌다.

그런데, 구글링을 해보니 이미 거의 답이 나와있었다.

Does MFC CMap have a good performance compared to std::unordered_map or std::map

 

MFC의 CMap 쪽이 근소하게 더 빠른 삽입과 검색 시간을 보여주고 있었다.

해당 글에서 천만개의 데이터를 삽입하고 검색하는데 소요되는 시간은 아래와 같았다.

 

 

그런데, 코드를 읽어보면 뭔가 좀 아쉬운 부분이 있다.

map의 삽입시에 key를 순차적으로 증가시키는데, 무작위로 삽입할 필요가 있다.

또한 CMap은 생성 후 해시 테이블 크기를 미리 잡아주어 성능을 최적화하는데, 이건 공정한 비교가 될 수 없다.

STL의 map/unordered_map에는 이런 기능 자체가 없기 때문이다.

그리고, 좀 더 순수한(?) 성능만을 비교하기 위해 value 값으로 CString 대신 int를 저장하는 것으로 수정했다.

 

이렇게 수정한 결과는 뭔가 묘하다.

일단, CMap의 초기 해시 테이블 크기를 10,000으로 설정한 결과는 아래와 같다.

CMap의 성능이 처참하게 느리다.

 

 

CMap의 초기 해시 테이블 크기를 100,000으로 설정한 결과는 아래와 같다.

많이 따라잡았지만, 여전히 성능이 훨씬 떨어진다.

전체 데이터의 개수가 10,000,000개라는 점을 참고할 것.

 

 

초기 해시 테이블의 크기를 1,000,000으로 설정하니 비로소 CMap 쪽이 더 빨라지기 시작한다.

원문에서는 아예 초기 해시 테이블 크기를 10,000,000으로 설정해두었었다.

 

 

map 구조에 저장할 데이터의 크기를 어느 정도 알고 적용한다면 CMap이 더 빠르다.

하지만, 그런 사전 정보 없이 사용한다면 std::map이 더 나은 성능을 보여준다.

 

덧. value의 형을 int 대신 원문과 동일하게 CString으로 적용한 결과도 대동소이함.

해시 테이블 초기 크기를 충분히 잡지 않는다면 삽입은 map이 더 빠르고, 탐색은 unordered_map이 더 빠름.