diff -r 83527d9f1f13 -r aa836f56c3cc mercurial/keepalive.py
--- a/mercurial/keepalive.py	Sat Apr 15 11:29:42 2017 +0200
+++ b/mercurial/keepalive.py	Thu Apr 13 18:04:38 2017 -0700
@@ -298,11 +298,12 @@
 
     def _start_transaction(self, h, req):
         # What follows mostly reimplements HTTPConnection.request()
-        # except it adds self.parent.addheaders in the mix.
-        headers = dict(self.parent.addheaders)
-        headers.update(req.headers)
-        headers.update(req.unredirected_hdrs)
-        headers = dict((n.lower(), v) for n, v in headers.items())
+        # except it adds self.parent.addheaders in the mix and sends headers
+        # in a deterministic order (to make testing easier).
+        headers = util.sortdict(self.parent.addheaders)
+        headers.update(sorted(req.headers.items()))
+        headers.update(sorted(req.unredirected_hdrs.items()))
+        headers = util.sortdict((n.lower(), v) for n, v in headers.items())
         skipheaders = {}
         for n in ('host', 'accept-encoding'):
             if n in headers: