I think I see now why dwarfcmp is so slow. But I don't fully understand
the intent/design of the comparison caching. But it seems we are not
using the results of the dwarf_comparator tracker caching as often (at
all?) as we could.
For future reference, there are a couple of similar, but different
comparing operators/functions constructs used. An important difference
to look for is whether dwarf_comparator comparisons are made through
equals () or match (). In the case of equals () the tracker can "short
circuit" a successful comparison if it has cached the result.
- subr::container_equal calls begin() on the arguments to get iterators
and compares each element through a predicate function given.
- class dwarf_comparator extends std::binary_function and defines an
bool operator (). This is implemented by calling match (a, b).
- a dwarf_comparator has a template function for equals (a, b) which
consults the tracker set and the match (a, b) function through
return _m_tracker.identical (a, b) || match (a, b);
- the private dwarf_comparator match (a, b) functions are specialized:
- dwarfs (calls match on compile_units),
- compile_units (uses subr::container_equal with match () as
predicate, while tracker.mismatch),
- debug_info_entries (creates a tracker::visitor calls == on tags,
equals () on attributes and children),
- die attributes (uses subr::container_equal, with match_rhs () as
predicate, which uses the comparator equals ()
method on the values of attributes, while
tracker.mismatch, then tries ordered attribute
lists comparing keys with == and values with equals)
- die children (uses subr::container_equal with match as predicate,
- attribute (calls == on value and equals () on values),
- attribute values (depending on the value space almost all
comparisons are done through ==, except for
reference which are compared through
calling reference_match ())
- child iterator (calls reference_match ())
- reference_match works on two die iterators. If the comparator ignores
refs then it always returns true. Otherwise a die identity comparison
is done first, then the tags are compared and whether both have
children. Then the tracker is queried. First the tracker
reference_matched () and cannot_match () are tried. Then a subtracker
and a subcomparator are created (with a reference to the original
tracker). Then the subcomparator equals () is called on the
attributes, the original tracker context_match () and the
subcomparator equals () in the children. Finally the original tracker
notice_match () is called with the actual result so it can possibly
log and/or cache that.
- dwarfcmp extends dwarf_comparator and overrides the () operator to
call equals (a, b) in quiet mode or in the noisy variant it calls
equals (a, b) && tracker.result.
- A dwarf_ref_tracker notice_match is ignored in both the base_tracker
and the dwarf_ref_tracker. dwarfcmp overrides it, but stores the
result in the base tracker, so it seems that is lost too.
identical (a, b) is defined as false in the base tracker (which means
the dwarf_comparator equals short circuit doesn't work).
So what is happening in even a small example is:
main (int argc, char **argv)
compiled with gcc -g this gives: tests/dwarf-print main
<subprogram external=1 name="main" ... type="#ref1" ...>
<formal_parameter name="argc" ... type="#ref1" .../>
<formal_parameter name="argv" ... type="#ref2" .../>
<base_type ref="ref1" byte_size=0x4 encoding=signed
<pointer_type ref="ref2" byte_size=0x8 type="#ref3"/>
<pointer_type ref="ref3" byte_size=0x8 type="#ref4"/>
<base_type ref="ref4" byte_size=0x1 encoding=signed_char
Note that the subprogram has #refs to types that are declared later in
the compile unit.
If we compare two of the above compile_units, even though the
ref_tracker keeps a cache of the context path, the "down path" isn't
cached. So the argv #ref2 is followed down to #ref3 and finally compared
down to ref4. But then when we encounter ref2 itself, the #ref3 type
reference is fully compared down to ref4. And again for the #ref4 in
I am not really sure where we the compare caching should really go and
be fixed because he precise idea behind the equal/match and
identical/notice_match are not completely clear to me. Is the
entanglement of the context path caching and the identical tracking on