diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -113,11 +113,11 @@ def _takefullsample(dag, nodes, size):
     # update from roots
     _updatesample(dag.inverse(), nodes, sample, always)
     assert sample
-    sample = _limitsample(sample, desiredlen)
-    if len(sample) < desiredlen:
-        more = desiredlen - len(sample)
-        sample.update(random.sample(list(nodes - sample - always), more))
     sample.update(always)
+    sample = _limitsample(sample, size)
+    if len(sample) < size:
+        more = size - len(sample)
+        sample.update(random.sample(list(nodes - sample), more))
     return sample
 
 def _limitsample(sample, desiredlen):
diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -326,7 +326,7 @@ One with >200 heads, which used to use u
   query 6; still undecided: 540, sample size is: 200
   sampling from both directions
   searching: 7 queries
-  query 7; still undecided: 44, sample size is: 44
+  query 7; still undecided: 37, sample size is: 37
   7 total queries
   common heads: 3ee37d65064a