C++ map<std::string> vs map<char *> performance (I know, "again?")

Question

I was using a map with a std::string key and while everything was working fine I wasn't getting the performance I expected. I searched for places to optimize and improved things only a little and that's when a colleague said, "that string key is going to be slow."

I read dozens of questions and they consistently say:

"don't use a char * as a key"
"std::string keys are never your bottleneck"
"the performance difference between a char * and a std::string is a myth."

I reluctantly tried a char * key and there was a difference, a big difference.

I boiled the problem down to a simple example:

#include <stdio.h>
#include <stdlib.h>
#include <map>

#ifdef USE_STRING

#include <string>
typedef std::map<std::string, int> Map;

#else

#include <string.h>
struct char_cmp { 
    bool operator () (const char *a,const char *b) const 
    {
        return strcmp(a,b)<0;
    } 
};
typedef std::map<const char *, int, char_cmp> Map;

#endif

Map m;

bool test(const char *s)
{
    Map::iterator it = m.find(s);
    return it != m.end();
}

int main(int argc, char *argv[])
{
    m.insert( Map::value_type("hello", 42) );

    const int lcount = atoi(argv[1]);
    for (int i=0 ; i<lcount ; i++) test("hello");
}

First the std::string version:

$ g++ -O3 -o test test.cpp -DUSE_STRING
$ time ./test 20000000
real    0m1.893s

Next the 'char *' version:

g++ -O3 -o test test.cpp             
$ time ./test 20000000
real    0m0.465s

That's a pretty big performance difference and about the same difference I see in my larger program.

Using a char * key is a pain to handle freeing the key and just doesn't feel right. C++ experts what am I missing? Any thoughts or suggestions?

Answer 1

You are using a const char * as a lookup key for find(). For the map containing const char* this is the correct type that find expects and the lookup can be done directly.

The map containing std::string expects the parameter of find() to be a std::string, so in this case the const char* first has to be converted to a std::string. This is probably the difference you are seeing.