The cache in question being dwarf_path_finder::_m_seen that's
filled in
dwarf_path_finder::step::step?
Right.
Then I guess we see the case that referents are further and further
ahead, so each of our caching walks ends just before hitting them.
I think I see what you mean. But that should still result in at most two
steps hitting each node, a forward reference causing a tracker::path_to
call and then the main walk in dwarf_comparator::match_child.
On one of the bigger C++ objects, I would normally see one DIE being
walked over 90+ times (since that's for dwarfcmp X X case, that actually
means 45+ times for each of the files).
> With a little more instrumentation, you can investigate whether there are
> really redundant walks being kicked off from {left,right}_context calls.
Yeah, I believe that actually is the case. I added some logging so that
step::step tells me where it's constructed from. That can be either
dwarf_path_finder::walk_to or dwarf_ref_tracker::step::step. The latter
case is rather rare (on my arbitrary test case, which is
libdw/edit-values.o, it's about 10% of all step constructions). The
former case is always inside {left,right}_context calls.
Right, walk_to is only used from path_to for the forward-reference cases.
After reading further and annotating some more, I see that some of
these
*_context calls are actually caused by the sub-comparator. But they are
still due to *_context.
Ok. This indicates something is not as it's supposed to be in that caching.
FWIW the caching seems to work, eventually. The last
{left,right}_context calls that end up doing more than 0 steps are in 8%
of my log file. There are big chasms of 0-step *_context calls even
before that point. The problem is that before we get to that point, we
do more steps that there is dies.
Ok.
Actually it seems to me like we always start walking from
"here" when we
look for referents, instead of walking from last referent on (since up
to that point, everything is cached). Could it be something as simple
as that?
It's been a long time since I really looked at this code, so I can't be
quite sure of anything. But anyway, I don't think I'm following exactly
what you are saying here. Each dwarf_path_finder object has a current
place in the walk. A path_to call that gets a cache miss always spins the
walk forward from that current location.
When a subcomparator is created in reference_match, it gets a subtracker.
The subtracker has a new dwarf_path_finder for each of the left and right
sides. That new dwarf_path_finder is built with the third constructor
variant, which shares the _m_seen map of the dwarf_path_finder of the main
tracker, but sets its initial _m_path (position in the walk) to the path
just returned by {left,right}_context.
I'm not clear on what "here" and "last referent" mean in what you
said.
So you may well be right, but I've become unclear on what it all means. :-)
Oh, I'm actually using roland/dwarf-hacking, so I don't have
this
commented out. Even the week-long spinning that I talked about before
was with that.
Ok, that's something unexpected.
Thanks,
Roland