Trying to get some of the algorithm ideas going on the mjw/dwarf_output
branch. Although I started out trying to change te way the copier marked
entries final and put them into the collector I ended up not immediately
needing that. Because when the entries are marked final both their
children and reference attributes are resolved already.
So what the code does at the moment is add a local_hash function to both
dwarf_output::debug_info_die and copier::pending_entry. These hash
functions should be in sync because a not fully resolved attribute
reference could be pointing to a pending_entry. Both calculate the local
hash based on the local hash of the attributes_type and the
children_type. Then the hash of a value_reference is the local hash of
the debug_info_die hash it is pointing at.
For now the really tricky case inside the local hash function of the
attribute_types containing a reference attribute is side stepped by just
using the tag of the reference attribute. This is enough to get the
small testcases in dwarf_edit_output working that failed before. Because
this makes the hashes of similar structures always the same (before they
would have hash slightly differently based on where a attribute
reference cycle was detected).
So what is missing is "chaining" the reference attribute local hashes
(if we don't chain them, we end up with very "flat" hashes where lots
dies get the same hash just because they have a reference attribute).
Ideally this would just be ref_attr.reference()->local_hash (), but
since we calculate the hash of the attributes_type just before it is
inserted into the collector this doesn't work (the way this aborts is
somewhat obscure though - it ends up in in the dwarf_data::variant
constructor that throws a "can't happen!"). I am a little confused atm
about how the instantiation of the attributes_type gets triggered
precisely. It is probably necessary to do this in two phases by lifting
parts of pending_entry::final () method out in a second initialization
Please do poke holes in the code or the whole story.
about two weeks ago I let dwarfcmp spin on one of the difficult cases.
After a week or so it answered that the files are equal. Another case
ended up after about a day. So I suppose the algorithms are sound, it's
just that it takes ages to get through it all.
OProfile shows that one major time sink is dwarf_path_finder::step ctor.
That is called from a bunch of places, but the interesting cases come
from dwarf_comparator::reference_match where it calls
dwarf_ref_tracker::left_context and dwarf_ref_tracker::right_context.
This gets called when the comparator hits forward reference. The
algorithm then starts from where in the tree we are (since it's
guaranteed to not need any of the already-seen dies, these are cached),
and traverses it in a linear fashion, looking for the referenced die.
I added counters to see how long these walks were. Average over our
build tree (excluding the cases that would take ages, where "ages" for
my purposes was anything above 20 seconds) is 18 steps, but many C++
modules make easily 100+ steps on average. Average over dwarflint
objects is 90 steps. Clearly C++ produces forward references that lead
further ahead on average (or there's more detailed and deeper structure
between here and there).
So the problem is we simply end up doing walks over those same dies
again and again and again, as we look for some far-ahead die. I don't
know if there are other time sinks, but getting rid of this traversing
should help a great deal.
The obvious solution is to do an initial pass over all dies, noting
forward references, and when we hit the die that is forward-referred to,
remembering the path for later. That way we would avoid all the
repetitve walking that context extraction entails. I suspect that
should help a great deal with the overall performance.
Another one of these c++ constructs that make me go ehe? questions...
Just wondering why there are these try-catch-throw constructs in
dwarf_edit and dwarf_output. They do some cleanups, but there isn't any
"recatcher" for the failures, so effectively all they do is hide the
root cause when something goes wrong. But I might be missing something.
To help my own debugging I have removed them on my branch.