use unordered_map where possible (e.g. mapRelay) #4237

I suggest to use unordered_map instead of map because it reduces the complexity. The standard map is ordered (often realized as binary search tree) and hence has a logarithmic complexity. In contrast the unordered_map has a constant complexity on average.

In most cases the ordered property is not necessary. For example in case of mapRelay I believe the map can be substituted by the unordered_map without loss of functionality. I am not sure about the magnitude of inserted inv messages but I can imagine if the network and/or the number of transactions grows this might have an impact on performance.

This seems like a pretty obvious optimization, however, you'd have to figure out where an unordered map can be used safely. For example, find out which maps are never iterated over at all.

In general if you want to improve performance I recommend to first profile before going on a wild goose chase. If we don't have concrete statistics that map lookups/insertions are a bottleneck anywhere, it may be wasted time to go over everything. In my profiles using valgrind here-and-there I don't remember seeing map functions anywhere near the top.

Also unordered_map is new in C++11. We don't use C++11 yet. Boost also has an unordered_map which should be interface-compatible with the C++11 one (TR1), which can be used in the meantime.

The one place where this would matter significantly is in CCoinsViewCache.

I've been thinking about using boost::multi_index for that, to have it implement a cache that is both O(1) to lookup, but also maintains an LRU list across entries. If the cache were split up in a dirty and a pure-cache part, it could even automatically discard non-dirty entries, until a given % of the cache is dirty, at which you flush. (instead of the current behaviour of flushing everything when the cache gets too large, and then dropping everything).

While hash table has a constant complexity on average it has linear complexity in the worst case. This potentialy can be used for DoS attack.

This was done. Closing.

• Use boost::unordered_map for mapBlockIndex #4838
• Use unordered_map for CCoinsViewCache with salted hash #4494