marmoute created this revision. Herald added a reviewer: hg-reviewers. Herald added a subscriber: mercurial-patches.
REVISION SUMMARY Before this, antichain computation can run for 10s of hours without completion in sight. We use a more direct approach in the computation to keep the computation in complexity in check. With good result. We can now have a full antichain computation on mozilla-try in about one minute. Which is usable. REPOSITORY rHG Mercurial BRANCH default REVISION DETAIL https://phab.mercurial-scm.org/D12396 AFFECTED FILES contrib/perf-utils/subsetmaker.py CHANGE DETAILS diff --git a/contrib/perf-utils/subsetmaker.py b/contrib/perf-utils/subsetmaker.py --- a/contrib/perf-utils/subsetmaker.py +++ b/contrib/perf-utils/subsetmaker.py @@ -159,16 +159,44 @@ else: assert False - selected = set() + cl = repo.changelog - baseset = revset.getset(repo, smartset.fullreposet(repo), x) - undecided = baseset + # We already have cheap access to the parent mapping. + # However, we need to build a mapping of the children mapping + parents = repo.changelog._uncheckedparentrevs + children_map = collections.defaultdict(list) + for r in cl: + p1, p2 = parents(r) + if p1 >= 0: + children_map[p1].append(r) + if p2 >= 0: + children_map[p2].append(r) + children = children_map.__getitem__ + + selected = set() + undecided = SortedSet(cl) while undecided: - pick = rand.choice(list(undecided)) + # while there is "undecided content", we pick a random changeset X + # and we remove anything in `::X + X::` from undecided content + pick = rand.choice(undecided) selected.add(pick) - undecided = repo.revs( - '%ld and not (::%ld or %ld::head())', baseset, selected, selected - ) + undecided.remove(pick) + + ancestors = set(p for p in parents(pick) if p in undecided) + descendants = set(c for c in children(pick) if c in undecided) + + while ancestors: + current = ancestors.pop() + undecided.remove(current) + for p in parents(current): + if p in undecided: + ancestors.add(p) + while descendants: + current = descendants.pop() + undecided.remove(current) + for p in children(current): + if p in undecided: + ancestors.add(p) return smartset.baseset(selected) & subset To: marmoute, #hg-reviewers Cc: mercurial-patches, mercurial-devel _______________________________________________ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
