On Tue, 30 Aug 2022 at 21:08, Marek Polacek via Gcc <gcc@gcc.gnu.org> wrote: > > On Tue, Aug 30, 2022 at 09:57:45PM +0200, Tim Lange wrote: > > Hello, > > > > I was preparing a patch for GCC and used the unordered_map from the C++ > > stdlib in my patch. Later on, I noticed that it is used nowhere else inside > > GCC except for some files in the go frontend. > > > > I wondered, now that building GCC requires a C++11 host compiler, whether > > there is a consensus on which data structure implementation is preferred. > > Should I rather use a hash_map instead of an unordered_map or is it on my > > side to decide which one I choose? > > I think you're probably better off using a hash_map; std::unordered_map > has efficiency issues as described in > https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2028r0.pdf
I assume you mean the comments on page 6. Does GCC's hash_map actually use open addressing and probing to deal with collisions? Do we want to be able to change the hash function or use per-compilation salts? (Would that break PCH?) If not, I don't see why it would be any better when considering the metrics that paper is referring to. It might be better based on other properties that benefit GCC, but the case against std::unordered_map is often overstated. If the question was whether to prefer std::unordered_map or absl::node_hash_map then I would agree that std::unordered_map is a bad choice. But that's not the question.
