public inbox for gcc@gcc.gnu.org
 help / color / mirror / Atom feed
* Usage of the C++ stdlib unordered_map in GCC
@ 2022-08-30 19:57 Tim Lange
  2022-08-30 20:07 ` Marek Polacek
  0 siblings, 1 reply; 6+ messages in thread
From: Tim Lange @ 2022-08-30 19:57 UTC (permalink / raw)
  To: GCC Mailing List

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



^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: Usage of the C++ stdlib unordered_map in GCC
  2022-08-30 19:57 Usage of the C++ stdlib unordered_map in GCC Tim Lange
@ 2022-08-30 20:07 ` Marek Polacek
  2022-08-31  9:37   ` Jonathan Wakely
  0 siblings, 1 reply; 6+ messages in thread
From: Marek Polacek @ 2022-08-30 20:07 UTC (permalink / raw)
  To: Tim Lange; +Cc: GCC Mailing List

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


^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: Usage of the C++ stdlib unordered_map in GCC
  2022-08-30 20:07 ` Marek Polacek
@ 2022-08-31  9:37   ` Jonathan Wakely
  2022-08-31 14:35     ` Jason Merrill
  0 siblings, 1 reply; 6+ messages in thread
From: Jonathan Wakely @ 2022-08-31  9:37 UTC (permalink / raw)
  To: Marek Polacek; +Cc: Tim Lange, GCC Mailing List

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.

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: Usage of the C++ stdlib unordered_map in GCC
  2022-08-31  9:37   ` Jonathan Wakely
@ 2022-08-31 14:35     ` Jason Merrill
  2022-08-31 14:35       ` Jason Merrill
  2022-08-31 15:22       ` Tim Lange
  0 siblings, 2 replies; 6+ messages in thread
From: Jason Merrill @ 2022-08-31 14:35 UTC (permalink / raw)
  To: Jonathan Wakely; +Cc: Marek Polacek, GCC Mailing List

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

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: Usage of the C++ stdlib unordered_map in GCC
  2022-08-31 14:35     ` Jason Merrill
@ 2022-08-31 14:35       ` Jason Merrill
  2022-08-31 15:22       ` Tim Lange
  1 sibling, 0 replies; 6+ messages in thread
From: Jason Merrill @ 2022-08-31 14:35 UTC (permalink / raw)
  To: Jonathan Wakely; +Cc: Marek Polacek, GCC Mailing List

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

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: Usage of the C++ stdlib unordered_map in GCC
  2022-08-31 14:35     ` Jason Merrill
  2022-08-31 14:35       ` Jason Merrill
@ 2022-08-31 15:22       ` Tim Lange
  1 sibling, 0 replies; 6+ messages in thread
From: Tim Lange @ 2022-08-31 15:22 UTC (permalink / raw)
  To: Jason Merrill; +Cc: GCC Mailing List

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



^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2022-08-31 15:22 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-30 19:57 Usage of the C++ stdlib unordered_map in GCC Tim Lange
2022-08-30 20:07 ` Marek Polacek
2022-08-31  9:37   ` Jonathan Wakely
2022-08-31 14:35     ` Jason Merrill
2022-08-31 14:35       ` Jason Merrill
2022-08-31 15:22       ` Tim Lange

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).