Re: mjw/dwarf_output branch

[Roland McGrath <roland at redhat dot com>]

> I guess I was somewhat misled by picking dynamic_equality_set as example
> since that isn't really a standard STL container, but something where we
> use the hash value explicitly and create and search the buckets directly
> instead of letting the STL container magic do all that for us.

Yes.  We only have dynamic_equality_set because a normal unordered_set
doesn't work for our case.  In an unordered_set (and all STL containers),
the equality predicate is a template parameter of the container type.  Here
we have a single container that can be used with many different equality
predicates.  That's because there is only one container in the collector,
but the things going into it are candidates partially-instantiated by the
various different copier<input> variants.  That's all because the actual
element comparison has to be done via copier<input>::attrs_match, which
uses the copier<input>::entry when it comes to an attr_value that is a
reference.  If we were using dynamic binding rather than template-based
compile-time binding, we would just use an unordered_set here.

> > The children_type and attributes_type objects are somewhat larger.  And
> > those are not the granularities of sharing in the file format.  So the only
> > benefit we are getting from independent sharing at those granularities is
> > memory savings.
> 
> You mean, we mostly do it for the side effect that comes with using a
> hashing function to put them into a container, so we don't have to
> compare lots of them?

I am not entirely sure what you mean, but I think that is close to what I
mean but not quite it.  ;-)

We have an independent hash table _m_broods, rather than just _m_unique.
This gets us more sharing of our in-memory data structures, because a
children_type that is by itself identical (e.g. the empty vector) will be a
single unique object with just one copy that is an element of _m_broods.
To do that, children_type has its own hash function, that drives the
_m_broods hash table.

If we didn't do this, then instead children_type would have no hash
function of its own and instead just debug_info_entry would have a hash
function that involves using hash_combine on each element of its children()
vector.  This would not increase the number of comparisons on children
vectors that we do.  It would just mean that the only comparisons would be
of a whole debug_info_entry with existing ones in _m_unique, where those
comparisons entail comparing the children when the debug_info_entry hash
value collides.  Today we are doing those same comparisons, but on the
children_type vector alone.  

In fact, we would do slightly fewer comparisons without the separate
_m_broods table, because we would never be comparing e.g. the empty
children_type vector on its own to an existing _m_broods element that might
be the identical empty vector (i.e. when its hash value is the same as that
of the empty children vectoor).  Instead, we would only compare a whole
childless debug_info_entry to existing _m_unique elements whose hash value
is the same as the whole debug_info_entry's hash value, which differs
between two different childless debug_info_entry objects that have a
different tag or different attributes.

Repeat all that for attributes_type and _m_attr_sets, in parallel to
children_type and _m_broods.

> >   For example, there is just one empty children_type object
> > in the collector and all debug_info_entry objects share the pointer to
> > that.  Likewise for less trivial ones, like an attributes_type of just
> > {name="x", type="#ref_to_int"} and a whole children_type for a parameter
> > list of (int, int, int) appearing in numerous prototypes' subprogram dies,
> > etc.  But it could well be that the memory savings there is not worth the
> > computation time to do the two separate hash tables.
> 
> I am not clear on what these two separate hash tables are.

I should have said "two more separate hash tables".  That is, there are
three separate hash tables: _m_unique, _m_broods, and _m_attr_sets.

> > I guess what I mean is that we would not have separate hash tables for
> > attributes_type and children_type objects in the collector (as I just
> > mentioned above).  Instead, only the whole debug_info_entry would have its
> > hashes collected from the contents of its two constituent containers.
> 
> And, so by extension I don't understand this either.
> Sorry for being dense.

There would be only _m_unique, and no _m_broods or _m_attr_sets.
The debug_info_entry hash function would be something like:

	size_t hash = tag ();
	for (auto i = attributes ().begin (); i != attributes ().end (); ++i)
	  subr::hash_combine (hash, *i);
	for (auto i = children ().begin (); i != children ().end (); ++i)
	  subr::hash_combine (hash, *i);

The single hash table would theoretically use more memory in the collector
because identical children_type vectors (independent of tag or attributes)
would not be shared, and identical attribute_type maps (independent of tag
or children) would not be shared.  In compensation, <tag1 attr=123/> and
<tag2 attr=123/> have different hash values and so no comparison of
{attr=123} or {empty children vector} would be done.  Today, those two
debug_info_entry objects still have different hash values (just because of
the differing tags) and don't get compared at the debug_info_entry level.
But {attr=123} is identical and thus is a single element in _m_attr_sets
with the same hash value and thus the need to compare a duplicate
attributes_type in its bucket, and likewise {emtpy children vector} is a
single element in _m_broods with the same hash value and thus the need to
compare a duplicate children_type in its bucket.  So we are trading compute
time for memory use.


Thanks,
Roland