setdiscovery: batch heads and known(ownheads)
This means that we now discover both subset conditions (local<remote and
remote<local) in a single roundtrip without ever constructing an actual
sample (which takes a bit of client CPU).
--- a/mercurial/setdiscovery.py Tue Jun 14 22:56:20 2011 +0200
+++ b/mercurial/setdiscovery.py Tue Jun 14 22:58:00 2011 +0200
@@ -91,15 +91,27 @@
roundtrips = 0
cl = local.changelog
dag = dagutil.revlogdag(cl)
- nodes = dag.nodeset()
- # early exit if we know all the specified server heads already
+ # early exit if we know all the specified remote heads already
ui.debug("query 1; heads\n")
roundtrips += 1
- srvheadhashes = remote.heads()
-
- ## TODO We might want to request an additional random sample of the server's
- ## nodes batched with the heads query here.
+ ownheads = dag.heads()
+ sample = ownheads
+ if remote.local():
+ # stopgap until we have a proper localpeer that supports batch()
+ srvheadhashes = remote.heads()
+ yesno = remote.known(dag.externalizeall(sample))
+ elif remote.capable('batch'):
+ batch = remote.batch()
+ srvheadhashesref = batch.heads()
+ yesnoref = batch.known(dag.externalizeall(sample))
+ batch.submit()
+ srvheadhashes = srvheadhashesref.value
+ yesno = yesnoref.value
+ else:
+ # compatibitity with pre-batch, but post-known remotes during 1.9 devel
+ srvheadhashes = remote.heads()
+ sample = []
if cl.tip() == nullid:
if srvheadhashes != [nullid]:
@@ -115,46 +127,48 @@
ui.note("all remote heads known locally\n")
return (srvheadhashes, False, srvheadhashes,)
+ if sample and util.all(yesno):
+ ui.note("all local heads known remotely\n")
+ ownheadhashes = dag.externalizeall(ownheads)
+ return (ownheadhashes, True, srvheadhashes,)
+
# full blown discovery
- undecided = nodes # own nodes where I don't know if the server knows them
+ undecided = dag.nodeset() # own nodes where I don't know if remote knows them
common = set() # own nodes I know we both know
- missing = set() # own nodes I know the server lacks
+ missing = set() # own nodes I know remote lacks
- # treat remote heads as a first implicit sample response
+ # treat remote heads (and maybe own heads) as a first implicit sample response
common.update(dag.ancestorset(srvheads))
undecided.difference_update(common)
- # use cheapish initial sample
- if common:
- ui.debug("taking initial sample\n")
- sample = _takefullsample(dag, undecided, size=fullsamplesize)
- else:
- ui.debug("taking quick initial sample\n")
- sample = _takequicksample(dag, nodes, size=initialsamplesize,
- initial=True)
+
+ full = False
+ while undecided:
- roundtrips += 1
- ui.progress(_('searching'), roundtrips, unit=_('queries'))
- ui.debug("query %i; still undecided: %i, sample size is: %i\n"
- % (roundtrips, len(undecided), len(sample)))
- # indices between sample and externalized version must match
- sample = list(sample)
- yesno = remote.known(dag.externalizeall(sample))
+ if sample:
+ commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
+ common.update(dag.ancestorset(commoninsample, common))
- while undecided:
- commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
- common.update(dag.ancestorset(commoninsample, common))
+ missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
+ missing.update(dag.descendantset(missinginsample, missing))
- missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
- missing.update(dag.descendantset(missinginsample, missing))
-
- undecided.difference_update(missing)
- undecided.difference_update(common)
+ undecided.difference_update(missing)
+ undecided.difference_update(common)
if not undecided:
break
- ui.note("sampling from both directions\n")
- sample = _takefullsample(dag, undecided, size=fullsamplesize)
+ if full:
+ ui.note("sampling from both directions\n")
+ sample = _takefullsample(dag, undecided, size=fullsamplesize)
+ elif common:
+ # use cheapish initial sample
+ ui.debug("taking initial sample\n")
+ sample = _takefullsample(dag, undecided, size=fullsamplesize)
+ else:
+ # use even cheaper initial sample
+ ui.debug("taking quick initial sample\n")
+ sample = _takequicksample(dag, undecided, size=initialsamplesize,
+ initial=True)
roundtrips += 1
ui.progress(_('searching'), roundtrips, unit=_('queries'))
@@ -163,6 +177,7 @@
# indices between sample and externalized version must match
sample = list(sample)
yesno = remote.known(dag.externalizeall(sample))
+ full = True
result = dag.headsetofconnecteds(common)
ui.progress(_('searching'), None)
--- a/tests/test-http-proxy.t Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-http-proxy.t Tue Jun 14 22:58:00 2011 +0200
@@ -102,19 +102,19 @@
* - - [*] "GET http://localhost:$HGPORT/?cmd=stream_out HTTP/1.1" - - (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
- * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+ * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
- * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+ * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
- * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+ * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
- * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+ * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
* - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
--- a/tests/test-push-warn.t Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-push-warn.t Tue Jun 14 22:58:00 2011 +0200
@@ -35,7 +35,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 2, sample size is: 2
+ query 2; still undecided: 1, sample size is: 1
2 total queries
new remote heads on branch 'default'
new remote head 1e108cc5548c
--- a/tests/test-schemes.t Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-schemes.t Tue Jun 14 22:58:00 2011 +0200
@@ -28,7 +28,7 @@
sending capabilities command
comparing with parts://localhost/
query 1; heads
- sending heads command
+ sending batch command
searching for changes
all remote heads known locally
no changes found
--- a/tests/test-setdiscovery.t Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-setdiscovery.t Tue Jun 14 22:58:00 2011 +0200
@@ -44,10 +44,7 @@
comparing with b
query 1; heads
searching for changes
- taking initial sample
- searching: 2 queries
- query 2; still undecided: 4, sample size is: 4
- 2 total queries
+ all local heads known remotely
common heads: b5714e113bc0 01241442b3c2
local is subset
@@ -83,9 +80,9 @@
comparing with b
query 1; heads
searching for changes
- taking quick initial sample
+ taking initial sample
searching: 2 queries
- query 2; still undecided: 35, sample size is: 35
+ query 2; still undecided: 29, sample size is: 29
2 total queries
common heads: bebd167eb94d
@@ -101,7 +98,7 @@
searching for changes
taking initial sample
searching: 2 queries
- query 2; still undecided: 3, sample size is: 3
+ query 2; still undecided: 2, sample size is: 2
2 total queries
common heads: bebd167eb94d
@@ -122,9 +119,9 @@
comparing with b
query 1; heads
searching for changes
- taking quick initial sample
+ taking initial sample
searching: 2 queries
- query 2; still undecided: 34, sample size is: 34
+ query 2; still undecided: 29, sample size is: 29
2 total queries
common heads: 2dc09a01254d
@@ -140,7 +137,7 @@
searching for changes
taking initial sample
searching: 2 queries
- query 2; still undecided: 30, sample size is: 30
+ query 2; still undecided: 29, sample size is: 29
2 total queries
common heads: 2dc09a01254d
@@ -163,7 +160,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 32, sample size is: 32
+ query 2; still undecided: 31, sample size is: 31
2 total queries
common heads: 66f7d451a68b
@@ -179,7 +176,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 32, sample size is: 32
+ query 2; still undecided: 31, sample size is: 31
2 total queries
common heads: 66f7d451a68b
@@ -202,7 +199,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 52, sample size is: 52
+ query 2; still undecided: 51, sample size is: 51
2 total queries
common heads: 66f7d451a68b
@@ -218,7 +215,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 32, sample size is: 32
+ query 2; still undecided: 31, sample size is: 31
2 total queries
common heads: 66f7d451a68b
@@ -241,7 +238,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 1050, sample size is: 11
+ query 2; still undecided: 1049, sample size is: 11
sampling from both directions
searching: 3 queries
query 3; still undecided: 31, sample size is: 31
@@ -260,7 +257,7 @@
searching for changes
taking quick initial sample
searching: 2 queries
- query 2; still undecided: 1030, sample size is: 11
+ query 2; still undecided: 1029, sample size is: 11
sampling from both directions
searching: 3 queries
query 3; still undecided: 16, sample size is: 16