Slowville: std::map

Many people don’t realise how slow the map that comes with the standard template library is.

Recently, I 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 1^st 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.