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.)

Thanks, Roland