diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -203,15 +203,19 @@ def findcommonheads(ui, local, remote,
         if full:
             ui.note(_("sampling from both directions\n"))
             sample = _takefullsample(dag, undecided, size=fullsamplesize)
+            targetsize = fullsamplesize
         elif common:
             # use cheapish initial sample
             ui.debug("taking initial sample\n")
             sample = _takefullsample(dag, undecided, size=fullsamplesize)
+            targetsize = fullsamplesize
         else:
             # use even cheaper initial sample
             ui.debug("taking quick initial sample\n")
             sample = _takequicksample(dag, undecided, size=initialsamplesize,
                                       initial=True)
+            targetsize = initialsamplesize
+        sample = _limitsample(sample, targetsize)
 
         roundtrips += 1
         ui.progress(_('searching'), roundtrips, unit=_('queries'))
diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -311,17 +311,23 @@ One with >200 heads, which used to use u
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 1240, sample size is: 260
+  query 2; still undecided: 1240, sample size is: 100
   sampling from both directions
   searching: 3 queries
-  query 3; still undecided: 980, sample size is: 260
+  query 3; still undecided: 1140, sample size is: 200
   sampling from both directions
   searching: 4 queries
-  query 4; still undecided: 720, sample size is: 260
+  query 4; still undecided: 940, sample size is: 200
   sampling from both directions
   searching: 5 queries
-  query 5; still undecided: 460, sample size is: 200
-  5 total queries
+  query 5; still undecided: 740, sample size is: 200
+  sampling from both directions
+  searching: 6 queries
+  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
+  7 total queries
   common heads: 3ee37d65064a
 
 Test actual protocol when pulling one new head in addition to common heads