Usage of the C++ stdlib unordered_map in GCC

Usage of the C++ stdlib unordered_map in GCC

[Tim Lange]

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?

- Tim

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

[Marek Polacek]

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

Marek

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

[Jonathan Wakely]

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.

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

[Jason Merrill]

On Wed, Aug 31, 2022 at 5:38 AM Jonathan Wakely via Gcc <gcc@gcc.gnu.org>
wrote:

> 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.
>

Generally we want to use the GCC hash_map because it works with GCC garbage
collection (and PCH).  Is that not relevant to your patch?

Jason

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

[Jason Merrill]

[-- Attachment #1: Type: text/plain, Size: 1749 bytes --]

On Wed, Aug 31, 2022 at 5:38 AM Jonathan Wakely via Gcc <gcc@gcc.gnu.org>
wrote:

> 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.
>

Generally we want to use the GCC hash_map because it works with GCC garbage
collection (and PCH).  Is that not relevant to your patch?

Jason

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

[Tim Lange]

On Mi, Aug 31 2022 at 10:35:08 -0400, Jason Merrill via Gcc 
<gcc@gcc.gnu.org> wrote:
> Generally we want to use the GCC hash_map because it works with GCC 
> garbage
> collection (and PCH).  Is that not relevant to your patch?
> 
> Jason

The map is only part a short-lived visitor object inside the analyzer 
and is used to map svalues to other svalues (in most cases <15 kv 
pairs). I'm new to GCC, so I started of using what I knew. Only later, 
I have noticed that the unordered_map is used little to nowhere. It is 
not much effort to change it but I just wondered whether the usage is 
so low because GCC only lately switched to C++11 or other reasons. The 
responses answered my question, thanks.

- Tim