subsetmaker: use SortedSet for the scratch variant
This provides a massive speedup on wide repository with many heads. For example
on mozilla-try, this move from un-usable slow to fairly instant.
Differential Revision: https://phab.mercurial-scm.org/D12395
--- a/contrib/perf-utils/subsetmaker.py Sun Mar 13 15:53:29 2022 +0100
+++ b/contrib/perf-utils/subsetmaker.py Sun Mar 13 16:24:01 2022 +0100
@@ -15,6 +15,10 @@
smartset,
)
+import sortedcontainers
+
+SortedSet = sortedcontainers.SortedSet
+
revsetpredicate = registrar.revsetpredicate()
@@ -78,7 +82,7 @@
n = revsetlang.getinteger(n, _(b"scratch expects a number"))
selected = set()
- heads = set()
+ heads = SortedSet()
children_count = collections.defaultdict(lambda: 0)
parents = repo.changelog._uncheckedparentrevs
@@ -102,9 +106,7 @@
for x in range(n):
if not heads:
break
- pickable = list(heads)
- pickable.sort()
- pick = rand.choice(pickable)
+ pick = rand.choice(heads)
heads.remove(pick)
assert pick not in selected
selected.add(pick)