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:
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 thanint
pair<int, int>
is on a par withint
- if you have to have both
int
andstring
, put theint
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.