D12396: subsetmaker: rework the antichain generation to be usable

[marmoute (Pierre-Yves David)]

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