October 14, 2010, at 02:37 PM

STL Map Lookup Times

So I’m writing some code that needs to cache things in a map. The key in the map corresponds to a unique sender. I want my senders to be able to get guaranteed-unique IDs without any server, peer-to-peer or static config; what they have is a string and an int that in combination, is guaranteed unique.

But I think that’s going to suck as a map key. Strings need memory accesses and lots of them. Ints can live in a register and compare in a single cycle.

I tried really hard to come up with a way of making them both merge into an int, without any luck. Mr. Boss Man suggested I should try actually measuring the difference between different types as map keys.

Here’s the core of the test code I wrote:

template<typename T>
double testMap(unsigned int itemCount, unsigned int lookupCount, T (*getKey)())
{
        Stopwatch sw;

        printf("Testing %s...\n", typeid(T).name());
        printf("Generating %d keys...", itemCount);
        sw.start();

        std::vector<T> keys(itemCount);

        for (unsigned int i = 0; i < itemCount; ++i)
        {
                keys.push_back(getKey());
        }

        sw.stop();
        printf("done; took %gms\n", sw.getElapsed());

        printf("Putting them into a map...", itemCount);
        sw.reset();
        sw.start();
        std::map<T, int> m;

        for (std::vector<T>::const_iterator it = keys.begin(); it != keys.end(); ++it)
        {
                m.insert(std::make_pair(*it, 0));
        }

        sw.stop();
        printf("done; took %gms\n", sw.getElapsed());

        printf("Looking up %d items...", lookupCount);
        sw.reset();
        sw.start();

        for (unsigned int i = 0; i < lookupCount; ++i)
        {
                const T& key = keys[i % keys.size()];
                m.find(key);
        }

        sw.stop();
        double time = sw.getElapsed() / lookupCount * 1000000;
        printf("done; took %gns each\n\n", time);

        return time;
}

You call this with a number of map items, number of lookups, and a pointer to a function that gets you a randomly generated key. (Random number generator collisions are probably an issue here but I chose to not bother with that.) It then fills up a vector with random keys, stuffs them into a map, and then looks them up. The times for filling the two collections are just data porn, the last one is what matters.

I then ran it with five different key types:

  • int
  • std::string
  • std::pair<int, int>
  • std::pair<int, std::string>
  • std::pair<std::string, int>

Here’s the results in Excel-o-vision, for varying map sizes and averaged across 10,000,000 lookups:

They’re roughly linear in log(n) as you might expect. Here they are as relative slowness compared to int:

So, for small maps (as I’m expecting in my case):

  • string is about 6x worse than int
  • pair<int, int> is on a par with int
  • if you have to have both int and string, put the int first (as it allows early exit from the comparison operator)
    • because the other way round is really awful
  • but overall, it’s still really fast. 120ns is not very long (well... maybe) compared to 20ns.

Update: These tests will of course have benefited hugely from the CPU caches. In real life, that doesn’t always happen. So I added some code to nuke the CPU cache (just a large memcpy() and being careful to exclude it from the timings) and got these:

A bit uglier, obviously a lot slower... the “cost” is less extreme, but it still produces similar conclusions, I think. Lookup is going to be on the microsecond level with strings and half with ints.