> 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
_______________________________________________
elfutils-devel mailing list
[email protected]
https://fedorahosted.org/mailman/listinfo/elfutils-devel
