# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@octobus.net>
# Date 1647185041 -3600
# Node ID 5a24bb7f4ed742c6d84cf6c694b73c97b14e2d50
# Parent  186223795e4ae1b00121c48230c51d6e0a7b7105
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

diff -r 186223795e4a -r 5a24bb7f4ed7 contrib/perf-utils/subsetmaker.py
--- 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)