diff --git a/mercurial/configitems.py b/mercurial/configitems.py
--- a/mercurial/configitems.py
+++ b/mercurial/configitems.py
@@ -412,6 +412,9 @@
 coreconfigitem('devel', 'debug.peer-request',
     default=False,
 )
+coreconfigitem('devel', 'discovery.randomize',
+    default=True,
+)
 _registerdiffopts(section='diff')
 coreconfigitem('email', 'bcc',
     default=None,
diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -386,7 +386,9 @@
 
     # full blown discovery
 
-    disco = partialdiscovery(local, ownheads)
+    randomize = ui.configbool('devel', 'discovery.randomize')
+    disco = partialdiscovery(local, ownheads, randomize=randomize)
+
     # treat remote heads (and maybe own heads) as a first implicit sample
     # response
     disco.addcommons(knownsrvheads)
diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -968,7 +968,7 @@
   updating to branch b
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
 
-  $ hg -R a debugdiscovery b --debug --verbose --config progress.debug=true
+  $ hg -R a debugdiscovery b --debug --verbose --config progress.debug=true --config devel.discovery.randomize=false
   comparing with b
   query 1; heads
   searching for changes
@@ -983,8 +983,11 @@
   query 4; still undecided: \d+, sample size is: 200 (re)
   sampling from both directions
   searching: 5 queries
-  query 5; still undecided: 195, sample size is: 195
-  5 total queries in *.????s (glob)
+  query 5; still undecided: 297, sample size is: 200
+  sampling from both directions
+  searching: 6 queries
+  query 6; still undecided: 96, sample size is: 96
+  6 total queries in *.????s (glob)
   elapsed time:  * seconds (glob)
   heads summary:
     total common heads:          1
@@ -1093,16 +1096,9 @@
 give 'all remote heads known locally' without checking the remaining heads -
 fixed in 86c35b7ae300:
 
-  $ cat >> $TESTTMP/unrandomsample.py << EOF
-  > import random
-  > def sample(population, k):
-  >     return sorted(population)[:k]
-  > random.sample = sample
-  > EOF
-
   $ cat >> r1/.hg/hgrc << EOF
-  > [extensions]
-  > unrandomsample = $TESTTMP/unrandomsample.py
+  > [devel]
+  > discovery.randomize = False
   > EOF
 
   $ hg -R r1 outgoing r2 -T'{rev} ' --config extensions.blackbox= \