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

Question

Does MFC CMap have a good performance compared to std::unordered_map or std::map, I ask this question because I'm going to start a project in my company, and to accelerate the development I'm going a start with an existing "similar" project but in this last, there is MFC CMap (hash table maps) ans I thought that using std::unordered_map can maybe increase performances. I didn't find any benchmarks or good articles related to CMap on the internet. Otherwise, with std::unordered_map do I have to fix a size for the hash table too like in CMap to avoid collisions and performances issues ?

***I didn't find any benchmarks or good articles related to CMap on the interne*** Why don't you benchmark both yourself with a dataset similar to what you will use in production on the hardware that you will use in production? — drescherjm, Dec 13 '15 at 16:00
CMap doesn't have a move support (you have to always pass it as an output parameter because of this if you want to return one from a function) and doesn't display anything useful in a watch window in a debugger. You also have to write code like `CMap map;` instead of `std::unordered_map map;`. If I were you I wouldn't even consider using of it - but it is up to you. — Marian Spanik, Dec 13 '15 at 16:01
drescgerjm, I have done in the past (std::map vs CMap) but I'm not convinced... but If I don't get answers here, I ll do another benchmark (CMaps vs unordered_map). — Aminos, Dec 13 '15 at 16:03
CMap is an outdated, non-portable horror show. Do us all a favour: use the standard containers and help bury MFC forever. — Richard Hodges, Dec 13 '15 at 16:08
I've just down-voted this because the first thing to do when trying to answering questions like this is to have a look at the documentation. — Martin Bonner supports Monica, Dec 13 '15 at 16:14
Haha OK Richard, those ugly stuff (CStrings, LPCSTR, CMaps, POINTERS ARITHMETICS to parse char strings :( ...) are still used in big companies... and If we use good stuff like smart pointers/STL, the produced code is usually (but no always) not accepted ! — Aminos, Dec 13 '15 at 16:14
Pick between either `std::map` or `std::unordered_map` for new MFC projects. I would stay away from all MFC containers except `CString` --- See also [`std::map` versus `std::unordered_map`](http://stackoverflow.com/questions/3902644/choosing-between-stdmap-and-stdunordered-map) — Barmak Shemirani, Dec 13 '15 at 17:13
@Aminos I understand the problem but idiot software managers need to be educated, otherwise the discipline of software development will be held back by MFC for another 20 years... — Richard Hodges, Dec 13 '15 at 21:46
@MarianSpanik: Like any other native object, display in a watch window is controlled through [Natvis visualizers](https://msdn.microsoft.com/en-us/library/jj620914.aspx). A `std::unordered_map` doesn't display any more useful information than a `CMap` would, out of the box. The debugger can be instructed to display useful information and structure for either type. — IInspectable, Dec 14 '15 at 01:27
@Aminos: Since you got all worked up about the ugliness of `CString`, keep in mind, that `CString` is **the only** true drop-in replacement for `const char*`/`const wchar_t*`. It can be used **anywhere** a `const char*`/`const wchar_t*` is expected, including variable argument lists. — IInspectable, Dec 14 '15 at 01:33

Andrew Komiagin · Accepted Answer · 2015-12-14T09:52:44.107

8

I've made pretty simple performance comparison test:

int nElements = 1000000;
CMap<int, int, CString, LPCTSTR> MfcHashTable;
MfcHashTable.InitHashTable(nElements);

// CMap insert
DWORD dwStart = ::GetTickCount();
for(int i=0; i<nElements; i++)
{
    CString sBase;
    sBase.AppendFormat(_T("Test String %d"), i);
    MfcHashTable[i] = sBase;
}

DWORD dwMfcMapInsert = ::GetTickCount() - dwStart;

// CMap lookup
CString sValue;

dwStart = ::GetTickCount();
for(int i=0; i<nElements; i++)
{
    MfcHashTable.Lookup(i, sValue);
}
DWORD dwMfcMapLookup = ::GetTickCount() - dwStart;

// std::map insert
std::map<int, CString> StdMap;
dwStart = ::GetTickCount();
for(int i=0; i<nElements; i++)
{
    CString sBase;
    sBase.AppendFormat(_T("Test String %d"), i);
    StdMap[i] = sBase;
}
DWORD dwStdMapInsert = ::GetTickCount() - dwStart;

//std::map lookup
dwStart = ::GetTickCount();
std::map<int, CString>::iterator it;
for(int i=0; i<nElements; i++)
{
    it = StdMap.find(i);
    CString sBase = it->second;
}
DWORD dwStdMapLookup = ::GetTickCount() - dwStart;

// std::unordered_map insert (hash table)
std::unordered_map<int, CString> StdUnordMap;
dwStart = ::GetTickCount();
for(int i=0; i<nElements; i++)
{
    CString sBase;
    sBase.AppendFormat(_T("Test String %d"), i);
    StdUnordMap[i] = sBase;
}
DWORD dwStdUnordMapInsert = ::GetTickCount() - dwStart;

//std::map lookup
dwStart = ::GetTickCount();
std::unordered_map<int, CString>::iterator it1;
for(int i=0; i<nElements; i++)
{
    it1 = StdUnordMap.find(i);
    CString sBase = it1->second;
}
DWORD dwStdUnordMapLookup = ::GetTickCount() - dwStart;

cout << dwMfcMapInsert << endl;
cout << dwMfcMapLookup << endl;

cout << dwStdMapInsert << endl;
cout << dwStdMapLookup << endl;

cout << dwStdUnordMapInsert << endl;
cout << dwStdUnordMapLookup << endl;

Here are the results for 1000000 elements on Intel Core i5 2.5Ghz 8GB RAM (Lenovo ThinkPad X230):

MFC CMap insert: 1125
MFC CMap lookup: 125
std::map insert: 1406
std::map lookup: 172
std::unordered_map insert: 1578
std::unordered_map lookup: 140

So surprisingly the CMap is the winner here. It turns out the ugly legacy CMap is not that bad after all!

edited Dec 14 '15 at 09:52

answered Dec 14 '15 at 09:40

Andrew Komiagin

6,446
1
13
23

3

And if you include the destruction. The CMap is even much faster, because it use memory blocks comparable with a pool allocator. If you look into the construction of the code it seams clear that the MFC Map is "better". ;) Even if it outdated. – xMRi Dec 14 '15 at 11:25
interesting, I've done a benchmark too, I used words from a big txt dictionary file and High performance coutner to measure time, but I did a mistake, for std::unordered_map I used std::string type for the values or keys whereas for CMaps, I used CStrings, so in that case unordered_map beat CMaps (by tens of milliseconds), I ll rewrite my benchmark and I ll took CString for everybody (because I couldn't put a std::string as a value in CMap, I didn't remember why it didn't work) – Aminos Dec 14 '15 at 12:03
2

I think the test is in `CMap`'s favor because the size is known (`InitHashTable`), it would be much slower if size is large and unknown. Meanwhile `unordered_map` is not taking advantage of `reserve`. Only lookup is faster for `CMap`. – Barmak Shemirani Dec 14 '15 at 19:49
2

You're right. The reason I did not use it is because `reserve()` was not implemented in VS2010 for `unordered_map`. Anyways I've implemented reserve as follows: `StdUnordMap.rehash(std::ceil(nElements / StdUnordMap.max_load_factor()));` The results are the following: 1312 for insert, 140 for lookup. A little bit better but still not the best. – Andrew Komiagin Dec 14 '15 at 20:12
if you rehash the unordered_map with a correct size and use std::string instead of CMaps in the STL container, well you will see that unordered map beats CMap. Mixed marriage between the two different libraries ain't good ! Otherwise, you use sorted keys, so if you put random int values as keys, well first of all, std::map will be the slowest and then the battle will be between unordered_map and the old CMap, and with my benchmark I found that unordred_map using std::string keys is faster than CMaps using CString keys by 20 - 40 ms for inserting and 3 - 8 ms for look ups. – Aminos Dec 14 '15 at 21:32
But then for the convenience, unordered_map is the best ! – Aminos Dec 14 '15 at 21:33
2

As long as you don't use a pool allocator, the MFC map will beat the unordered_map specially when you have a lot of entries. And when the hash map is just created for a temporary action the destruction phase in deleting all items is not a "short" action. – xMRi Dec 16 '15 at 09:14

score 0 · Answer 2 · answered Dec 13 '15 at 16:12

0

Well 20 seconds searching for "MFC CMap" found

Lookup uses a hashing algorithm to quickly find the map element with a key that exactly matches the given key.

So the big-O efficiency will be like unordered_map.

answered Dec 13 '15 at 16:12

Martin Bonner supports Monica

28,528
3
51
88

1

Could down-voters please explain? The question asked whether CMap had similar performance to `map` or `unordered_map`. I answered that it will be similar to `unordered_map`. Why is that a bad answer? – Martin Bonner supports Monica Dec 14 '15 at 13:00

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

2 Answers2