# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 2015-01-08 01:28:51
# Node ID 932f814bf01635c327570cf61c0ac3cae4718db4
# Parent  db58186dd8e3ad35fb451916c262a43a6e7d524e

setdiscovery: always add exponential sample to the heads

As explained in a previous changeset, prioritizing heads too much behaves
pathologically when there are more heads than the sample size. To counter this,
we always inject exponential samples before reducing to the sample size limit.

This already show some benefit in the test themselves, but on a real-world example
this moves my discovery for push to pathologically headed repo from 45 rounds to
17 of them.

We should maybe ensure that at least 25% of the result sample is heads, but I
think the random sampling will be fine in practice.

diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -105,10 +105,7 @@ def _takequicksample(dag, nodes, size):
     return sample
 
 def _takefullsample(dag, nodes, size):
-    always = dag.headsetofconnecteds(nodes)
-    if size <= len(always):
-        return always
-    sample = always
+    sample = always = dag.headsetofconnecteds(nodes)
     # update from heads
     _updatesample(dag, nodes, sample, always)
     # update from roots
diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -317,17 +317,14 @@ One with >200 heads, which used to use u
   query 3; still undecided: 1140, sample size is: 200
   sampling from both directions
   searching: 4 queries
-  query 4; still undecided: 940, sample size is: 200
+  query 4; still undecided: 592, sample size is: 200
   sampling from both directions
   searching: 5 queries
-  query 5; still undecided: 740, sample size is: 200
+  query 5; still undecided: 292, 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: 46, sample size is: 46
-  7 total queries
+  query 6; still undecided: 51, sample size is: 51
+  6 total queries
   common heads: 3ee37d65064a
 
 Test actual protocol when pulling one new head in addition to common heads