subsetmaker: rework the antichain generation to be usable
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.
Differential Revision: https://phab.mercurial-scm.org/D12396
--- a/contrib/perf-utils/subsetmaker.py Sun Mar 13 16:24:01 2022 +0100
+++ b/contrib/perf-utils/subsetmaker.py Mon Mar 21 20:06:51 2022 +0100
@@ -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