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

contrib/perf-utils/subsetmaker.py

@@ -159,16 +159,44 b' def antichain(repo, subset, x):'
     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