Re: [PATCH 4/7] Class-fy partial_die_info

[Pedro Alves <palves at redhat dot com>]

On 01/31/2018 03:46 AM, Simon Marchi wrote:
> On 2018-01-30 06:39, Pedro Alves wrote:
>> On 01/29/2018 01:15 AM, Simon Marchi wrote:
>>
>>> From what I understand, the only reason to have that private constructor is
>>> to construct a temporary partial_die_info object used to search in the htab,
>>> is that right?  If so, converting that htab_t to an std::unordered_map would
>>> remove the need for all this, since you don't need to construct an object
>>> to search it.  See the diff below that applies on top of this patch.
>>>
>>> It's not thoroughly tested and I am not sure of the validity of the
>>> per_cu->cu->partial_dies.empty () call in find_partial_die, but I think it
>>> should work.  Plus, it adds some type-safety, which I am a big fan of.
>>>
>>> But otherwise, the patch is fine with me.
>>
>> Careful here.  This could do with some benchmarking.  The DWARF reading code
>> is performance (both timing and memory) sensitive.  This is trading an open
>> addressing hash table (htab_t), for a node-based closed addressing hash table.
>> The keys/elements in the map are small so I'd expect this to make
>> a difference.  Also, this is trading a in-principle cache-friendly
>> obstack allocation scheme for the standard new allocator.
> 
> Ah, indeed.  I thought that unordered_map would be implemented the same way as htab_t, but I see it's not the case.  Doing some quick tests on a big binary, it increases the time reading the symbols from an average of 37 seconds to an average of 42 seconds.
> 
> I understand the different hash table implementation having an impact, but I don't really understand how the allocation scheme can have a meaningful impact.  The partial_die_info objects are still allocated on the obstack, aren't they?  So it's just the space for the table itself that isn't on the objstack, but I don't see why that would make a difference.

Well, that's the thing.  unordered_map is going to reach to the heap to
allocate the buckets and nodes.  And the heap is slow.  And there's a
memory size cost for each element too, along with that reducing
cache locality.

unordered_map is really inefficient for this use case.  We have a hash map
of small objects that is filled in once, and after initial fill, we don't
do random insert/remove of elements from this map.  I think.

> 
> If we want to have a data structure with the same kind of performance as htab_t but with type-safety in the future, is your vision that we'll have to implement it ourselves?  Should we make a wrapper around htab_t?

Well, my vision is to investigate alternatives.  :-)  There are many options
out there.  If you google around for hash table benchmarks you'll find several.
E.g.: <https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html>.

So there are good alternatives out there that we could import and use.
AFAIK, libiberty's htab_t is actually quite good, and GCC has a C++-ified
version of that.  See gcc/hash-table.h, gcc/hash-map.h, gcc/hash-set.h:

 /* This file implements a typed hash table.
    The implementation borrows from libiberty's htab_t in hashtab.h.

So sharing that code with GCC may make sense, as it's already in
"the family".

One thing I dislike about GCC's hash containers above is that
their API isn't modeled on the standard's, which can lead to
confusion if you're used to the standard containers, or if you're
experimenting/benchmarking different containers for some
use case.  You have things like:

  /* This function clears all entries in this hash table.  */
   void empty () { if (elements ()) empty_slow (); }

while in the std containers, empty() is a predicate...

It may be that GCC's hash/map/set could do with C++11-fication too.
Really I haven't investigated much.  I'm just aware of their
existence.

(A while ago I found reading this discussion quite educational:
  <https://bugs.ruby-lang.org/issues/12142>)

Thanks,
Pedro Alves