Slowville: std::map
October 4, 2010 1 Comment
Many people don’t realise how slow the map that comes with the standard template library is.
Reciently, did some performance comparisons of std::map versus boost::unordered_map.
These are the benchmarks that I tested:
fmap<int, int> mapTest; fmap<int, int>::iterator iter; int time1 = GetMilliSeconds(); int n; int randNum, rand2; rand2 = 0; for (n = 0; n < 100000; n++) { randNum = rand()%1000; iter = mapTest.find(randNum); if (iter != mapTest.end()) { rand2 = iter->second; } else { mapTest[randNum] = rand2; rand2 = n; } } int time2 = GetMilliSeconds(); int timeElapsed = abs(time2-time1); cout << "map test1 time:" << timeElapsed << "ms" << endl; time1 = time2; fmap<int, int> mapTest2; fmap<int, int>::iterator iterLowest; int f; for (n = 0; n < 10000; n++) { for (f = 0; f < 10; f++) { randNum = rand()%1000; iter = mapTest2.find(randNum); if (iter != mapTest2.end()) { rand2 = iter->second+1; } else { mapTest2[randNum] = rand2; rand2 = n; } } // find lowest iterLowest = mapTest2.begin(); for (iter = mapTest2.begin(); iter != mapTest2.end(); iter++) { if (iter->second > iterLowest->second) iterLowest = iter; } mapTest2.erase(iterLowest); } time2 = GetMilliSeconds(); timeElapsed = abs(time2-time1); cout << "map test2 time:" << timeElapsed << "ms" << endl;
(Unfortunately, this looks awful because stupid word press strips out my code indentation 😦 )
And these are the results running on 1st gen iPod touch:
boost::unordered_map
map test1 time:115ms
map test2 time:2251ms
std::map
map test1 time:200ms
map test2 time:3940ms
As you can see it’s nearly twice as slow.
std::map is an ordered map. In other words, when iterating the values are ordered according to the key. Normally, you don’t need this functionality, so using a hash map like boost::unordered_map is a no-brainer.
hi!This was a really marvelous subject!
I come from milan, I was luck to search your Topics in bing
Also I obtain much in your website really thanks very much i will come again