How can I increase the performance in a map lookup with key type std::string?

Question

I'm using a std::map (VC++ implementation) and it's a little slow for lookups via the map's find method.

The key type is std::string.

Can I increase the performance of this std::map lookup via a custom key compare override for the map? For example, maybe std::string < compare doesn't take into consideration a simple string::size() compare before comparing its data?

Any other ideas to speed up the compare?

In my situation the map will always contain < 15 elements, but it is being queried non stop and performance is critical. Maybe there is a better data structure that I can use that would be faster?

Update: The map contains file paths.

Update2: The map's elements are changing often.

Instantly

Answer 1

First, turn off all the profiling and DEBUG switches. These can slow down STL immensely.

If that's not it, part of the problem may be that your strings are identical for the first 80-90% of the string. This isn't bad for map, necessarily, but it is for string comparisons. If this is the case, your search can take much longer.

For example, in this code find() will likely result in a couple of string compares, but each will return after comparing the first character until "david", and then the first three characters will be checked. So at most, 5 characters will be checked per call.

map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map<string,int>::iterator iter = names.find("daniel");

On the other hand, in the following code, find() will likely check 135+ characters:

map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;

map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");

That's because the string comparisons have to search deeper to find a match since the beginning of each string is the same.

Using size() in your comparison for equality won't help you much here since your data set is so small. A std::map is kept sorted so its elements can be searched with a binary search. Each call to find should result in less than 5 string comparisons for a miss, and an average of 2 comparisons for a hit. But it does depend on your data. If most of your path strings are of different lengths, then a size check like Motti describes could help a lot.

Something to consider when thinking of alternative algorithms is how many many "hits" you get. Are most of your find() calls returning end() or a hit? If most of your find()s return end() (misses) then you are searching the entire map every time (2logn string compares).

Hash_map is a good idea; it should cut your search time in about half for hits; more for misses.

A custom algorithm may be called for because of the nature of path strings, especially if your data set has common ancestry like in the above code.

Another thing to consider is how you get your search strings. If you are reusing them, it may help to encode them into something that is easier to compare. If you use them once and discard them, then this encoding step is probably too expensive.

I used something like a Huffman coding tree once (a long time ago) to optimize string searches. A binary string search tree like that may be more efficient in some cases, but its pretty expensive for small sets like yours.

Finally, look into alternative std::map implementations. I've heard bad things about some of VC's stl code performance. The DEBUG library in particular is bad about checking you on every call. StlPort used to be a good alternative, but I haven't tried it in a few years. I've always loved Boost too.

Epitasis

Thanks for the debug part, never thought that debug checks can eat so much time (50 ms per operator[] in my map<int,...>). – Brawl

Answer 2

As Even said the operator used in a set is < not ==.

If you don't care about the order of the strings in your set you can pass the set a custom comparator that performs better than the regular less-than.

For example if a lot of your strings have similar prefixes (but they vary in length) you can sort by string length (since string.length is constant speed).

If you do so beware a common mistake:

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() < rhs.length())
            return true;
        return lhs < rhs;
    }
};

This operator does not maintain a strict weak ordering, as it can treat two strings as each less than the other.

string a = "z";
string b = "aa";

Follow the logic and you'll see that comp(a, b) == true and comp(b, a) == true.

The correct implementation is:

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() != rhs.length())
            return lhs.length() < rhs.length();
        return lhs < rhs;
    }
};

Detrude

not a bad idea (though I would rewrite it with temps so that the length() calls happen once not twice. But I suspect that these extra compares have the potential to mitigate any gains given the small number of elements in the map. – Bidentate

I like the idea to define a non-lexicographic ordering that is faster to evaluate. – Bagel

They're just integer compares, you never know till you measure. As for temps for length, sure I would do that too, just wanted to keep the example clear. – Detrude

Answer 3

The first thing is to try using a hash_map if that's possible - you are right that the standard string compare doesn't first check for size (since it compares lexicographically), but writing your own map code is something you'd be better off avoiding. From your question it sounds like you do not need to iterate over ranges; in that case map doesn't have anything hash_map doesn't.

It also depends on what sort of keys you have in your map. Are they typically very long? Also what does "a little slow" mean? If you have not profiled the code it's quite possible that it's a different part taking time.

Update: Hmm, the bottleneck in your program is a map::find, but the map always has less than 15 elements. This makes me suspect that the profile was somehow misleading, because a find on a map this small should not be slow, at all. In fact, a map::find should be so fast, just the overhead of profiling could be more than the find call itself. I have to ask again, are you sure this is really the bottleneck in your program? You say the strings are paths, but you're not doing any sort of OS calls, file system access, disk access in this loop? Any of those should be orders of magnitude slower than a map::find on a small map. Really any way of getting a string should be slower than the map::find.

Cloudy

I have profiled the code, it is the map find that's causing the slowdown I want to improve. I'm comparing file paths in the map. – Instantly

Thanks I'll give hash_map a try. The file paths stored in the map are also usually files in the same directory (so most of the path match). I was considering doing my own compare function and comparing from right to left instead. But I think hash_map might give me even better performance. – Instantly

If your compiler implements TR1, you'll have access to unordered_map, unordered_set, etc. Otherwise, you'll be using a vendor extension (like the GNU hash_map). – Thyrsus

ya I'm sure it is that line of code for the find. It is not slow, it is just that I want the best performance because there is constant lookups in this map. – Instantly

Answer 4

You can try to use a sorted vector (here's one sample), this may turn out to be faster (you'll have to profile it to make sure of-course).

Reasons to think it'll be faster:

1. Less memory allocations and deallocations (the vector will expand to the maximal size used and then reuse freed memory).
2. Binary find with random access should be faster than tree traversal (espacially due to data locality).

Reasons to think it'll be slower:

1. Deleations and additions will mean moving strings around in memory, since string's swap is efficiant and the size of the data set is small this may not be an issue.

Detrude

note that when the map is frequently updated (as Brian said it would), a sorted vector loses its appeal (you would have to sort it again very often). I'd agree to those that suggested a hash_map – Secern

Answer 5

std::map's comparator isn't std::equal_to it's std::less, I'm not sure what the best way to short circuit a < compare so that it would be faster than the built in one.

If there are always < 15 elems, perhaps you could use a key besides std::string?

Bidentate

All 15 elements are always changing. But at any 1 time there are only around at most 15 elements. – Instantly

Answer 6

Motti has a good solution. However, I'm pretty sure that for your < 15 elements a map isn't the right way because its overhead will always be greater than that of a simple lookup table with an appropriate hashing scheme. In your case, it might even be enough to hash by length alone, and if that still produces collisions, use a linear search through all entries of the same length.

To establish if I'm right, a benchmark is of course required but I'm quite sure of its outcome.

Assuming

The app is very multi-threaded and the 15 elements are always changing. – Instantly

So maybe a hash_map with hash function that hashes the length, ok. – Instantly

"Very multi-threaded". I know everyone has already asked this, and you've said you're sure, so this is a statement not a question: the bottleneck is definitely the call to find(), not the locking. How good is your profiler at accounting for the overhead of context switches? – Jenks

Answer 7

You might consider pre-computing a hash for a string, and saving that in your map. Doing so gives the advantage of hash compares instead of string compares during the search through the std::map tree.

class HashedString
{
  unsigned m_hash;
  std::string m_string;

public:
  HashedString(const std::string& str)
    : m_hash(HashString(str))
    , m_string(str)
  {};
  // ... copy constructor and etc...

  unsigned GetHash() const {return m_hash;}
  const std::string& GetString() const {return m_string;}
};

This has the benefits of computing a hash of the string once, on construction. After this, you could implement a comparison function:

struct comp
{
  bool operator()(const HashedString& lhs, const HashedString& rhs)
  {
    if(lhs.GetHash() < rhs.GetHash()) return true;
    if(lhs.GetHash() > rhs.GetHash()) return false;
    return lhs.GetString() < rhs.GetString();
  }
};

Since hashes are now computed on HashedString construction, they are stored that way in the std::map, and so the compare can happen very quickly (an integer compare) in an astronomically high percentage of the time, falling back on standard string compares when the hashes are equal.

Deiform

Answer 8

Maybe you could reverse the strings prior to using them as keys in the map? That could help if the first few letters of each string are identical.

Dose

Or using a comparison operator that does reverse comparisons. – Pumpernickel

Answer 9

Here are some things you can consider:

0) Are you sure this is where the performance bottleneck is? Like the results from Quantify, Cachegrind, gprof or something like that? Because lookups on such a smap map should be fairly fast...

1) You can override the functor used to compare the keys in std::map<>, there is a second template parameter to do that. I doubt you can do much better than operator<, however.

2) Are the contents of the map changing a lot? If not, and given the very small size of your map, maybe using a sorted vector and binary search could yield better results (for example because you can exploit memory locality better.

3) Are the elements known at compile time? You could use a perfect hash function to improve lookup times if that is the case. Search for gperf on the web.

4) Do you have a lot of lookups that fail to find anything? If so, maybe comparing with the first and last elements in the collection may eliminate many mismatches quicker than a full search every time.

These have been suggested already, but in more detail:

5) Since you have so few strings, maybe you could use a different key. For example, are your keys all the same size? Can you use a class containing a fixed-length array of characters? Can you convert your strings to numbers or some data structure with only numbers?

Swiercz

Are you sure this is where the performance bottleneck is? -- Yes, they are fairly fast but I need faster. – Instantly

Are the contents of the map changing a lot? -- Yes – Instantly

Are the elements known at compile time? -- No Do you have a lot of lookups that fail to find anything? - Never Re 5: They are all file paths – Instantly

@Brian: I would look into hash maps then. – Swiercz

Answer 10

Depending on the usage cases, there are some other techniques you can use. For example we had an application that needed to keep up with over a million different file paths. The problem with that there were thousands of objects that needed to keep small maps of these file paths.

Since adding new file paths to the data set was an infrequent operation, when path was added to the system, a master map was searched. If the path was not found, then it was added and a new sequenced integer (starting at 1) was returned. If the path already existed, then the previously assigned integer was returned. Then each map maintained by each object was converted from a string based map to an integer map. Not only did this greatly improve performance, it reduced memory usage by not having so many duplicate copies of the strings.

Sure, this is a very specific optimization. But when it comes to performance improvements, you often find yourself having to make tailored solutions to specific problems.

And I hate strings :) Not are they slow to compare, but they can really trash your CPU caches on high performance software.

Mayce

Answer 11

Try std::tr1::unordered_map (found in the header <tr1/unordered_map>). This is a hash map, and, while it doesn't maintain a sorted order of elements, will likely be far faster than a regular map.

If your compiler doesn't support TR1, get a newer version. MSVC and gcc both support TR1, and I believe the newest versions of most other compilers also have support. Unfortunately, a lot of the library reference sites haven't been updated, so TR1 remains a largely-unknown piece of technology.

I hope C++0x isn't the same way.

EDIT: Note that the default hashing method for tr1::unordered_map is tr1::hash, which needs to be specialized to work on a UDT, probably.

Voluble

Answer 12

Where you have long common substrings, a trie might be a better data structure than a map or a hash_map. I said "might", though - a hash_map already only traverses the key once per lookup, so should be fairly fast. I won't discuss it further since others already have.

You could also consider a splay tree if some keys are more frequently looked up than others, but of course this makes the worst-case lookup worse than a balanced tree, and lookups are mutating operations, which may matter to you if you're using e.g. a reader-writer lock.

If you care about the performance of lookups more than modifications, you might do better with an AVL tree than a red-black, which I think is what STL implementations generally use for map. An AVL tree is typically better balanced and so will on average require fewer comparisons per lookup, but the difference is marginal.

Finding an implementation of these that you're happy with might be an issue. A search on the Boost main page suggests they have a splay and AVL tree but not a trie.

You mentioned in a comment that you never have a lookup that fails to find anything. So you could in theory skip the final comparison, which in a tree of 15 < 2^4 elements could give you something like a 20-25% speedup without doing anything else. In fact, maybe more than that, since equal strings are the slowest to compare. Whether it's worth writing your own container just for this optimisation is another question.

You might also consider locality of reference - I don't know whether you could avoid the occasional page miss by allocating the keys and the nodes out of a small heap. If you only need about 15 entries at a time, then assuming a file name limit below 256 bytes you could ensure that everything accessed during a lookup fits into a single 4k page (apart from the key being looked up, of course). It may be that comparing the strings is insignificant compared with a couple of page loads. However, if this is your bottleneck there must be an enormous number of lookups going on, so I'd guess that everything is reasonably close to the CPU. Worth checking, maybe.

Another thought: if you are using pessimistic locking on a structure where there's a lot of contention (you said in a comment the program is massively multi-threaded) then regardless of what the profiler tells you (what code the CPU cycles are spent in), it might be costing you more than you think by effectively limiting you to 1 core. Try a reader-writer lock?

Jenks

Answer 13

hash_map is not standard, try using unordered_map available in tr1 (which is available in boost if your tool chain doesn't already have it).

For small numbers of strings you might be better using vector, as map is typically implemented as a tree.

Heavy

hash_map for vc++ has is available stdext::hash_map #include <hash_map> – Instantly

Answer 14

Why don't you use a hashtable instead? boost::unordered_map could do. Or you can roll out your own solution, and store the crc of a string instead of the string itself. Or better yet, put #defines for the strings, and use those for lookup, e.g.,

#define "STRING_1" STRING_1

Monotype