13 ms·

Effortless Performance Improvements in C++: std:unordered_map

• ofalkaed 4y ago
  Under what situation (if any) does the ordered map win over the unordered? I find it difficult to believe it is always an improvement, what's the niche uses?
  • teraflop 4y ago
    Any time you actually need to use the ordering property. For instance, if you have an ordered map with string keys, you can very efficiently find all the keys with a given prefix. With an unordered_map, you'd have to iterate through the entire data structure.
    • ofalkaed 4y ago
      Thanks for explaining the obvious, my self taught programming skills are unordered and my biggest obstacle is generally my not seeing what is right in front of me.
      • sicp-enjoyer 4y ago
        All of <algorithm> uses ordering operators as well. If you have a "regular" type with proper comparison and assignment operators, it works for everything, container keys, sorting, etc, etc.
    • nly 4y ago
      Doing a string prefix search in an ordered map is actually not maximally efficient since you end up comparing the shared prefix over and over again during the binary search. You'd definitely don't want to be doing this with long prefixes.
  • s9w 4y ago
    [dead]
  • OnionBlender 4y ago
    If you want to store an object that implements operator< but doesn't have a hash function. While working on a leetcode problem I stored vector<int> in a set<vector<int>> instead of unordered_set<vector<int>> in order to eliminate duplicates.
    • sicp-enjoyer 4y ago
      Do you know about std::unique? Generally sets are a poor tool for removing duplicates.
      • pixelesque 4y ago
        Doesn't std::unique only generally work on consecutive items, and effectively requires the items to already be in a container (or at the very least have access to iterators to the items)? If so, that sounds fairly limiting to me (i.e. potential extra storage - of duplicates, sorting required, etc).
        • sicp-enjoyer 4y ago
          This person is already putting sets inside vectors, so I don't think they are worried about storage. But yes, you either need to stop occasionally and remove the duplicates or use a set, if the storage is prohibitive. Otherwise in terms of performance, sorting and unique is much faster than inserting one element at a time in a set.
  • dataflow 4y ago
    Some stuff I can think of: - Hashing can be slower than comparison (or vice-versa), depending on the input. (e.g., imagine if your keys are multi-gigabyte files - hashing them would require reading all of their contents, whereas comparing might only need to read the first few bytes.) - Ordered maps guarantee good worst-case performance. Unordered maps only guarantee average case. Usually you don't need to care, but with adversarial input you might. - Ordered maps can guarantee low latency (well, to the extent your allocator can). Unordered maps can't - they suddenly block your program until the whole table is rehashed. Again, usually you don't need to care, but in some situations you might. - Ordered maps have stable iterators; unordered maps "only" have stable pointers. - Ordered maps have a guaranteed iteration order that depends solely on their contents; unordered maps don't. - Any time the ordering itself is useful (see sibling comment)
    • ofalkaed 4y ago
      That was very helpful, my initial mistake was I forgot about the data and only looked at what was being done too it, but I also neglected how we access that data. My background in analog electronics has made this one of the more difficult things in programming for me, I am used to my data as a stream not as something stored.
  • pixelesque 4y ago
    There may be contrived situations where std::map<T> is actually faster due to the operator < work being possibly cheaper than doing the full hash of the key, but that will only work if the key type is very well distributed early on in the key (i.e. for very long strings, with the first few characters in long strings all being different among items in the std::map, providing the ability to short-circuit quickly) and the number of items in the map is less than what's needed to meet the short-circuit threshold that makes it technically more efficient. But that's very unlikely, and in such a contrived scenario it's likely doing a linear std::find() over an array of keys would be as fast or faster anyway, due to better caching/pre-fetching/branch-prediction.
• saagarjha 4y ago
  To preempt the inevitable comment: in some cases (make sure to check!) you can use a third-party hash table such as the one Abseil provides, which may be faster for your usecase if you can use it. Of course, profile first before switching and make sure that std::unordered_map is your bottleneck, understand why it is slow, then determine whether it would be possible to switch.
  • lrem 4y ago
    Are there any cases where the abseil maps are slower? And: how often does this even matter? I'd guess very rarely.
    • tialaramex 4y ago
      The Abseil maps assume you are using a good quality hash for your hash map. If you are using one that's particularly bad, e.g. your standard library typically provides hashes which are a complete joke, Google's Swiss Tables have catastrophically bad performance. In contrast your typical std::unordered_map has indifferent performance with a good hash versus a terrible hash, anything vaguely resembling a working hash will perform similarly (not very well). Remember "all the defaults are wrong" in C++. That's not literally true, but more often than not, if there's a clownishly obvious mistake possible, C++ made it and you will need to explicitly work around it in your C++ program. In this case, there's no avalanche behaviour in most out-of-box hashes for C++. So the hash for 1, 2, 3 and 4 are extremely similar, and indeed in many cases they turn out to be 1, 2, 3 and 4 respectively. Not a good hash.
      • themulticaster 4y ago
        I was genuinely surprised when I stumbled upon this Stack Overflow question [1] where someone asked why std::hash is the identity function for int, and some commenters argue that it is a perfectly sensible choice for a hash function. [1] https://stackoverflow.com/questions/38304877/why-stdhashint-seems-to-be-identity-function https://stackoverflow.com/questions/38304877/why-stdhashint-...
• thethirdone 4y ago
  If you look at part 1 [0], it is pretty clear that std::map is not THE major bottle neck. The whole program is pretty slow. The issues I see are: a lot of string copying instead of string views, splitting strings into vectors rather than splitting on demand, replacing on the same string repeatedly and collecting into a string before adding it to another string. It seems like their benchmark data has a lot of small lines with set and value commands, which would not be majorly hurt by those issues. The performance of ~20MB/s is REALLY SLOW for string processing in cpp. A fast but not super optimized c++ program should be getting in the ballpark of 500MB/s. [0]: https://julien.jorge.st/posts/en/effortless-performance-improvements-in-cpp/ https://julien.jorge.st/posts/en/effortless-performance-impr...
  • benreesman 4y ago
    Clearly a veteran of C++ in particular or the “zero-cost abstraction” cluster of languages in general is not going to miss a bunch of needless allocations etc. in a setting where performance matters a lot and I basically agree about the high notes of where you’d start to tune this up. But the author is clearly a highly-motivated intermediate C++ user who is taking time to share some key lessons and anyone who keeps that up for long won’t be intermediate for long! So it’s still a cool blog IMHO :)
    • raverbashing 4y ago
      Well I'm always surprised how the actual implementation of the stl primitives looks like "C++ cool tricks 101" turned to eleven and I wouldn't be surprised if the ability of compilers to optimize that was not great
      • benreesman 4y ago
        Eh, the folks writing the standard library definitely work adjacent to the folks doing the compiler in C++ for sure and I think Rust and stuff too. Both gcc and clang for example ship with co-designed standard libraries. It’s backwards compatibility that kills them on performance which is why the 900-IQ C++ shops like Google etc. just go their own way on the hash table because it’s worth it to them to do the extra work.
• colonwqbang 4y ago
  I find it so strange and unintuitive that a table lookup in STL can actually amend the table to include the key. I don't know of another library that works like that. std::map<std::string, std::string> m; (void) m["nonexistent"]; m.size(); // => 1 Is there a historic reason for this strange specification? Or is it just a concession make the "operator=" sugar work better?
  • cmovq 4y ago
    If you try to implement your own map you’ll naturally end up with this quirk. operator[] returns a reference to a slot in the map which can be read from or assigned to. Since the reference must be valid, you better have allocated a slot in the map that can be written to if the value didn’t exist.
    • madars 4y ago
      I don't think it's _that_ unnatural to just return a reference to a dummy value (i.e. have a member T map<T>::dummy and always return that if the key does not exist). Users writing to it/reading from it are on their own; you could even reinitialize it on every such operator[] call.
      • cmovq 4y ago
        operator[] is not only used for lookups though, it’s also used for insertions: m["nonexistent"] = 1; This would not work if you return a dummy value.
        • madars 4y ago
          That's true; thanks! It's 3am and time for bed :-)
        • 8n4vidtmkvmk 4y ago
          This is why I gave up on [] and just use .at now.
• panic 4y ago
  std::unordered_map is forced to be slow and make lots of allocations due to iterator invalidation requirements. It's usually a good choice to avoid it (and use a different hash table implementation) if you care about performance.
• samsaga2 4y ago
  I always listened that unordered_map is more cache friendlier than map. My intuition tells me unordered_map is better to iterate, and map is better to random access.
  • powersnail 4y ago
    Unordered map is a hash map. Map is a binary search tree. There’s no random access for hash map, in the sense of “give me the fifth element”. If you mean a lookup, like map[key], hash map has an O(1) amortized look up, where as a binary tree has an O(log n) look up, so hash map will generally be faster in this regard.
    • tialaramex 4y ago
      By "iterate" I expect they mean to just look at all the key/value pairs in the map. Since it says "Unordered" right in the name they don't care what order they see the elements, just that they see them all. This is easy to do in all sane hash map designs, and is very fast in a linear design like Abseil's Swiss Tables. Also sadly C++ std::unordered_map is guaranteed to be not just a hash table but an open hash table, using buckets to keep all the stuff which collided together. This is probably not what you wanted, but too bad that's what was standardized.
      • sicp-enjoyer 4y ago
        This is quite unfortunate. The way to get a really good hash table is by enforcing a bunch of simplifying assumptions (power of 2 sizes, sentinel values, etc). But the C++ committee has to make the "one true table" for everyone. std::map actually seems to fit this role better. It works reasonable well for many workloads and types without tuning a bunch of parameters.
      • masklinn 4y ago
        > is very fast in a linear design like Abseil's Swiss Tables. It's not that fast, because branching is completely unpredictable when iterating the sparse array (though a very high load factor helps). That's why a few modern hash tables trade an additional indirection on lookup by storing entries in a dense array and making the sparse array an array of indices into that. It makes iterating the map as efficient as iterating an array (or zipping two depending on data layout), it also saves some memory (especially if the indices array is adaptive), and has the neat side-effect of making the map conserve insertion order (though deletion is a bit of a concern, tradeoffs may have to be made with the other advantages).
• einpoklum 4y ago
  Both std::map and std::unordered_map are slow, ,actually. See this discussion on StackOverflow: https://stackoverflow.com/q/42588264/1593077 https://stackoverflow.com/q/42588264/1593077
• benreesman 4y ago
  In spite of some technically incorrect statements this is a generally very useful observation and not just in C++: it’s easy to pay for traversal properties you don’t need in an associative data structure. Hash tables and red black trees shine in different applications :) Still pretty low-effort but slightly higher cost and benefit is to switch to more modern data structures that have to break a little backwards compatibility to get big wins. Things like Folly’s F14 and Abseil’s collections (Abseil has both faster hash tables and faster tree-style maps). I think languages like Rust with a little less backwards compatibility burden are shipping with cache-aware and SIMD-exploiting data structures “out of the box” these days, but but my knowledge of e.g. Rust stops short of “read the standard library a bunch of times” so check with someone who has :)
  • tialaramex 4y ago
    Rust promises its language and standard library have full backward compatibility however that promise only refers to the actual documented API behaviour and this is intentionally narrow in places where it matters for performance. Thus for example, the HashMap in Rust 1.0 is different from the HashMap shipped in any recent Rust, but they both implement the API described in the documentation, the new one is just much faster because it's actually HashBrown, a re-implementation in Rust of Google's Swiss Tables C++ hash map. Hyrum's Law means that to some extent even though the defined API is narrow, people will write Rust code, by mistake or on purpose which depends on internals that were never guaranteed. For example, sort_unstable_by() is, as its name says, an unstable sort, you should not assume that it leaves ['a', 'A', 'B', 'b'] in the same order when you provide a case-insensitive comparison operator - you should have used sort_by() if you could not accept instability in your sort results. Rust gets to measure the impact of Hyrum's Law and re-consider potential changes which have large real impact because it does Crater Runs, which compile and test large volumes of Rust software from the crates.io package site and GitHub, with to-be-released Rust versions. If you made a change that you thought was basically a typographical fix, and it's technically not a breaking change by Rust's rules but it blew up 15000 widely used crates, you need to think harder about whether that's OK and most likely revert your change. C++ has no analogue of the Crater Run as of yet, and it offers a lot of needlessly broad APIs which lock it into choices that are terrible because it promised something that in hindsight nobody cares about, but now you daren't change that. The ABI promises in real world C++ implementations make this even worse. Rust's Mutex<Option<CompactString>> [[CompactString is a 3rd party library type]] is significantly smaller than a std::mutex on most popular C++ platforms, and yet std::mutex is literally just a mutex, whereas Mutex<Option<CompactString>> is a mutex protecting an optional Small String Optimized string containing up to 24 bytes of UTF-8 encoded string all in line in your smaller data type.
• jb1991 4y ago
  The thing is, it’s not actually effortless in many situations to switch from one map to the other. In C++, if you switch to an unordered map, you now have to contend with the annoying boilerplate of implementing a hash function for many key types. Using an ordered map may sometimes give you a slight hit in performance, but it offers significant benefits in developer convenience, and for small maps, the binary tree could actually be faster anyway.
  • benreesman 4y ago
    In fairness the tree still needs operator<() which sometimes less but not always easier to figure out than std::hash<>. I’d make a polite observation that in practice the GNU std::map is a red-black tree and that terminology mixup (which the author makes) might confuse folks.
    • jb1991 4y ago
      It’s not unusual for the operator to be automatically available while the hashing function is not, however.
      • benreesman 4y ago
        Yeah that’s fair and not a bad point.
      • MauranKilom 4y ago
        Also, for some reason the C++ standard library does not provide a simple hash_combine or similar that would allow composing hashes of sub-objects of your custom type in a straightforward manner.
        • sicp-enjoyer 4y ago
          Can many hashes be combined quickly in a uniform way? This is another benefit of `<`, it composes.
• avarsheny 4y ago
  Why not just use iterator that will avoid multiple lookups.
  • julien-j 4y ago
    This is a solution presented in the post :)
• TonyTrapp 4y ago
  I rarely need to use maps, but everytime I had to, std::unordered_map was measurably slower than std::map. In particular in debug mode, it was really slow, and if you choose an unfortunate hashing function (I think older MSVC versions had a really bad one), it can easily become a bottleneck. In particular with small data or data that has trivial comparison functions, std::map might often be better and should be the go-to choice.
• deleted 4y ago
  [deleted]
• Night_Thastus 4y ago
  For anyone in a situation where an unordered_set or unordered_map is in a hot part of the code, I'd also highly recommend Robin Hood: https://github.com/martinus/robin-hood-hashing https://github.com/martinus/robin-hood-hashing It made a huge difference in one of the programs I was running. EDIT: I could have sworn they used to also support the ordered versions, but maybe not.
  • jll29 4y ago
    Thanks!
• ziml77 4y ago
  If you're really looking to optimize hash map performance, you should try Abseil's flat_hash_map. It's able to do some things that the standard library's maps cannot because it doesn't have to stick to the standard library's guarantees of pointer stability.