I've revamped the dwarf_path_finder code a bit (f8af969). I think the new
way it works is what Petr was suggesting earlier, when I wasn't following
what he was saying.
Now all searches on any derived object go to the "master" object. If
walk-ahead is required to find a DIE not yet seen, then it uses a single
walkahead object that spins ahead until it steps over the target DIE.
That walkahead object stays alive until the master object catches up to its
position in the walk, at which point it's deleted.
This should have the effect of only ever doing at most two complete walks
(not including proper side-walks in subcomparators, of course).
There's a simple optimization I didn't do, for a case that the old code
tried to optimize. That's for a case where a forward reference is to the
immediate next sibling. This is fairly common, e.g. <pointer_type type=/>
with the referent type being the immediate next sibling DIE in the CU. As
things now stand, this will create the walkahead clone that takes only one
step to win, then delete it on the next step of the main walk. When that
case comes up a lot, it could be a lot of churn on new/construct and
destroy/delete work for that clone. We could short-circuit that if the
new/delete overhead there seems significant.
I tested this on run-dwarfcmp-self and saw no regressions in the C cases.
I didn't wait for the C++ cases to finish, since it will still take a week.
I didn't actually measure the performance at all, though algorithmically it
should be better than before. (And the new code is actually a bit simpler
than the old, too.)
Petr, I'd appreciate it if you could do that performance comparison and
also re-do your instrumentation checks to ensure that the redundant walks
for searches really are bounded the way I think they should be now.
Whenever you do some instrumentation, please post (directly or via private
git branches) the code hacks you write, as well as describing completely
the test data and test scenarios you do, so that other people can repeat
the experiments easily. (If cases and results get hairy, it may be
worthwhile to put up actual binaries you used as test data, in case
everybody's build doesn't come out the same.)