Re: [PATCH 00/19] Add hash table to gdbsupport

[Simon Marchi <simark@simark.ca>]

On 2024-01-11 13:07, Tom Tromey wrote:
>>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
> 
> [ new hash table ]
> 
> Tom> I'd like to move forward with this.
> 
> Tom> I think most of the patches here are straightforward.  The real question
> Tom> is whether we want it.  I've laid out my rationale in patch #1, with
> Tom> some additions (explaining why this is better than unordered_map /
> Tom> unordered_set) in a follow-up email.
> 
> I tried converting a few more libiberty hash tables to this one.
> 
> For a lot of things this is fine, big improvement, etc.
> 
> However, this hash table doesn't really admit the possibility that an
> element might not have a natural sentinel value.  This particularly
> comes up with hash maps, where if you want a std::string->whatever map,
> you have to introduce some kind of explicit sentinel (in my case I chose
> empty string) and also then have to write a trait class.
> 
> So, this is one area where unordered_map has the advantage.  Now, it
> would be possible to handle this in some way.  The hash table could
> store a sentinel flag, for instance.  Or, we could just accept this
> drawback and use unordered_map when convenience is important.
> 
> Anyway, I tend to think it's not an enormous issue, but I figured I'd
> point it out.
> 
> Tom

I spent a bit of time reading the interface of your hash table, and that
was a point I found unfortunate.  The type V must have a default
constructor and an "empty" state (I guess that's what you mean by
sentinel), even if it doesn't make sense for the rest of the program.

How do other implementations (of open addessing hash tables) typically
deal with this?  From what I recally, other implementations I have used
in the past didn't have this requirement.

And that makes me think that a question I did not see answered is: I
don't want to undermine your work, but what is the rationale for
implementing it ourselves?  Efficient C++ hash maps is a topic that
comes up all the time on various programming news sites (I found this
recent blog post after a quick google search [1]), surely that's a
solved problem.  Is there not a popular hash map library we can use
as-is?

Simon

[1] https://martin.ankerl.com/2022/08/27/hashmap-bench-01/