Page MenuHomePhabricator

Replace custom written DFS walk with depth first iterator

Authored by dberlin on Apr 9 2015, 11:06 AM.



GenericDomTreeConstruction had its own written DFS walk.
It is basically identical to the DFS walk df_* is doing in the iterators.
the one difference is that df_iterator uses an internal visited set.
The GenericDomTreeConstruction one reused a field in an existing densemap lookup.

Time-wise, this way is actually more cache-friendly (the previous way has a random store
into a successor's info, the new way does that store at the same time and in the same place
as other stores to the same info)

It costs some very small amount of memory to do this, and one we pay in some other part of
dom tree construction *anyway*, so we aren't really increasing dom tree constructions's
peak memory usage.

It could still be changed to use the old field with a little work on df_ext_* if we care
(and if someone find performance regressions)

Diff Detail


Event Timeline

dberlin retitled this revision from to Replace custom written DFS walk with depth first iterator.
dberlin updated this object.
dberlin edited the test plan for this revision. (Show Details)
dberlin added a reviewer: chandlerc.
dberlin added a subscriber: Unknown Object (MLST).
chandlerc accepted this revision.Apr 14 2015, 8:02 AM
chandlerc edited edge metadata.

LGTM. Yay deleting code.

This revision is now accepted and ready to land.Apr 14 2015, 8:02 AM

Looks like patch was not committed.

dberlin updated this revision to Diff 73336.Oct 3 2016, 1:45 PM
dberlin edited edge metadata.

Update to fix parent bug

dberlin reclaimed this revision.Feb 7 2017, 9:09 AM

I'm going to reopen this. The postdom bug in 24415 is much easier to fix if we go with this.
As that bug says, i'm going to make the visited set external, to remove the small slowdown this patch has, and then properly add roots during DFS finding.

This revision is now accepted and ready to land.Feb 7 2017, 9:09 AM
davide added a subscriber: davide.Feb 7 2017, 9:27 AM
  • Update to use external storage, removing performance difference vs current code.

As a followup, i will fix 24415 and i believe that will re-merge these two DFS functions.

This revision was automatically updated to reflect the committed changes.