This is the mail archive of the elfutils-devel@sourceware.org mailing list for the elfutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

dwarfcmp comparison caching


Hi,

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,
                  while tracker.mismatch)
  - 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:

int
main (int argc, char **argv)
{
  return 0;
}

compiled with gcc -g this gives: tests/dwarf-print main

main:
<compile_unit ...>
  <subprogram external=1 name="main" ... type="#ref1" ...>
   <formal_parameter name="argc" ... type="#ref1" .../>
   <formal_parameter name="argv" ... type="#ref2" .../>
  </subprogram>
  <base_type ref="ref1" byte_size=0x4 encoding=signed name="int"/>
  <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 name="char"/>
</compile_unit>

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
ref3 itself.

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
purpose?

Cheers,

Mark


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]