stl map performance?

Question

I am using map<MyStruct, I*> map1;. Apparently 9% of my total app time is spent in there. Specifically on one line of one of my major functions. The map isn't very big (<1k almost always, <20 is common).

Is there an alternative implementation i may want to use? I think i shouldn't write my own but i could if i thought it was a good idea.

Additional info: I always check before adding an element. If a key exist I need to report a problem. Than after a point i will be using map heavily for lookups and will not add any more elements.

Solution 1

First you need to understand what a map is and what the operations that you are doing represent. A std::map is a balanced binary tree, lookup will take O( log N ) operations, each of which is a comparison of the keys plus some extra that you can ignore in most cases (pointer management). Insertion takes roughly the same time to locate the point of insertion, plus allocation of the new node, the actual insertion into the tree and rebalancing. The complexity is again O( log N ) although the hidden constants are higher.

When you try to determine whether an key is in the map prior to insertion you are incurring the cost of the lookup and if it does not succeed, the same cost to locate the point of insertion. You can avoid the extra cost by using std::map::insert that return a pair with an iterator and a bool telling you whether the insertion actually happened or the element was already there.

Beyond that, you need to understand how costly it is to compare your keys, which falls out of what the question shows (MyStruct could hold just one int or a thousand of them), which is something you need to take into account.

Finally, it might be the case that a map is not the most efficient data structure for your needs, and you might want to consider using either an std::unordered_map (hash table) that has expected constant time insertions (if the hash function is not horrible) or for small data sets even a plain ordered array (or std::vector) on which you can use binary search to locate the elements (this will reduce the number of allocations, at the cost of more expensive insertions, but if the held types are small enough it might be worth it)

As always with performance, measure and then try to understand where the time is being spent. Also note that a 10% of the time spent in a particular function or data structure might be a lot or almost nothing at all, depending on what your application is. For example, if your application is just performing lookups and insertions into a data set, and that takes only a 10% of the CPU you have a lot to optimize everywhere else!

Solution 2

Probably it will be quicker to just do an insert and check if the pair.second is false if key already exists:

like this

if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
  // report error
}
else
  // inserted new value

... rather than doing a find call every time.

Solution 3

Instead of map you could try unordered_map which uses hash keys, instead of a tree, to find elements. This answer gives some hints when to prefer unordered_map over map.

Solution 4

It might be a long shot, but for small collections, sometimes the most critical factor is the cache performance.

Since std::map implements a Red-Black Tree, which is [AFAIK] not very cache-efficient - maybe implementing the map as a std::vector<pair<MyStruct,I*>> would be a good idea, and use binary search there [instead of map look-ups], at the very least it should be efficient once you start only looking up [stop inserting elements], since the std::vector is more likely to fit in cache than the map.

This factor [cpu-cache] is usually neglected and hidden as constant in the big O notation, but for large collections it might have major effect.

Solution 5

The way you are using the map, you're doing lookups on the basis of a MyStruct instance and depending on your particular implementation, the required comparison may or may not be costly.

View more solutions

Comments

[Alexandre C.]

Without source code, we can't really tell. Also look at the version of insert which returns a pair (this will answer your second question)

[amit]

Could you share information on your compare function on MyStruct that the map uses as well?

[Sebastian Dressler]

Can you provide a little more information about what are you doing within the mentioned function? Since the lookup complexity of map is O(log n), I'm not sure where an improvement shall come from.

[Peter Wood]

Are you profiling with optimisations on?

[amit]

For small collections, hash-maps are usually slower then red-black-trees, so I expect its usage in this case to only have a negative affect.

[Admin]

Excellent idea. Although adding memebers is not the line with the performance problem. I'll add that in and take a look at the performance

[Admin]

I'd probably have a class that uses two vectors internally rather than a pair and make it look similar to a map.

[EdChum]

If you defer the find to whether you actually have a clash you probably eliminate a shedload of lookups that are not necessary unless you are doing something rather odd and generating more duplicate values than unique ones. The insert method I have detailed returns a pair with first being an iterator to the new value or duplicate value, the second is a boolean with true meaning success and false meaning duplicate entry.

[amit]

@acidzombie24: The pair is only a suggestion. Regarding two vectors: I agree, it will probably be indeed even better then a vector of pairs [less fields -> less memory usage -> more likely that the entire map will fit in cache]. The answer aimed to only to emphasize the important of cache on small collections, and to remind it is usually much more important then big O notation for these, since the constants should not be neglected.

[Admin]

hmm, i don't think i need it in a specific order. I realize most of the code was checking if the two variables are null and i dount think it ever is. Just removing that check made it fast enough to disappear from the profiler(i'm surprised). If it shows up again i'll play with the compare function more. +1 and possibly accept.

[Admin]

Problem: Lookup. Proper Struct: Maybe. I need to find a struct by key (which needs to compare with other struct) and the interface object associated with it. I dont think order is a problem since it typically tiny. Copy/Assign: Well, i assign by copying a ptr. Its immutable so i dont have to worry about it being deleted.

[Admin]

I was checking if both structs are null in my cmp func. Removing it made it fast enough to not show up anymore. +1 for overall answer.

[Admin]

MyStruct is actually T* where T is a template ;). See my first comment to Johann Gerell answer

[Admin]

Excellent answer. One suggestion was unordered (hash) may be bad since the size of the table is small. I'll definitely use insert in my other location. You hit on all the important points

[bitmask]

Well, in that case you don't have to bother with this redirection.

[Admin]

I feel a bit silly not doing inserts this way. I must have been in a rush or thought it was throwaway code.

[Admin]

yep. so +1 for the suggestion anyways :)

[Kerrek SB]

Alternatively to a blind insert you could use lower_bound, check the key, and then use hinted insertion (if you want to avoid a potentially expensive object construction).

[Dai Doan]

We have seen big improvements in our code in certain cases when switching from map to vector. We suspect the caching performance is much greater with vector.

[Christian Ammer]

@amit: Even for a small collection with 20 elements, this simple comparison -- under the restriction of a simple key type -- gives me a better performance for the unordered_set. A real comparison would include MyStruct and a hash function for it.

[Admin]

The struct is actually a quick wrapper template i wrote which holds T*. The point is so ops like < and == will do *ptr OP *other so it doesn't compare by ptr address. It makes my life immensely easier when using containers. Thats another good hint. +1 @KerrekSB

[Admin]

I looked at unordered_map. After reading the error message (its big...) i realize i need to implement a hashing function. I have no idea how to do that. How do i hash a char*? One that can be 1 to 20chars long (or more)

[Christian Ammer]

@acidzombie24: The Standard Library provides the template std::hash which you can use as hash function for std::string. Maybe you don't need to explicitly specify it as template argument to unordered_map, if you switch from char* to std::string. There is also this stackoverflow question asking for a string-hashing-function.