Re: Usage of the C++ stdlib unordered_map in GCC

[Jonathan Wakely <jwakely.gcc@gmail.com>]

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.