diff --git a/mercurial/hg.py b/mercurial/hg.py
--- a/mercurial/hg.py
+++ b/mercurial/hg.py
@@ -336,6 +336,16 @@ def clone(ui, peeropts, source, dest=Non
 
             destlock = copystore(ui, srcrepo, destpath)
 
+            # Recomputing branch cache might be slow on big repos,
+            # so just copy it
+            dstcachedir = os.path.join(destpath, 'cache')
+            srcbranchcache = srcrepo.sjoin('cache/branchheads')
+            dstbranchcache = os.path.join(dstcachedir, 'branchheads')
+            if os.path.exists(srcbranchcache):
+                if not os.path.exists(dstcachedir):
+                    os.mkdir(dstcachedir)
+                util.copyfile(srcbranchcache, dstbranchcache)
+
             # we need to re-init the repo after manually copying the data
             # into it
             destpeer = peer(ui, peeropts, dest)
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -2472,6 +2472,12 @@ class localrepository(object):
     def stream_in(self, remote, requirements):
         lock = self.lock()
         try:
+            # Save remote branchmap. We will use it later
+            # to speed up branchcache creation
+            rbranchmap = None
+            if remote.capable("branchmap"):
+                rbranchmap = remote.branchmap()
+
             fp = remote.stream_out()
             l = fp.readline()
             try:
@@ -2532,6 +2538,17 @@ class localrepository(object):
             self._applyrequirements(requirements)
             self._writerequirements()
 
+            if rbranchmap:
+                rbheads = []
+                for bheads in rbranchmap.itervalues():
+                    rbheads.extend(bheads)
+
+                self.branchcache = rbranchmap
+                if rbheads:
+                    rtiprev = max((int(self.changelog.rev(node))
+                            for node in rbheads))
+                    self._writebranchcache(self.branchcache,
+                            self[rtiprev].node(), rtiprev)
             self.invalidate()
             return len(self.heads()) + 1
         finally:
diff --git a/tests/test-http-proxy.t b/tests/test-http-proxy.t
--- a/tests/test-http-proxy.t
+++ b/tests/test-http-proxy.t
@@ -99,6 +99,7 @@ do not use the proxy if it is in the no 
   1 files updated, 0 files merged, 0 files removed, 0 files unresolved
   $ cat proxy.log
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=branchmap HTTP/1.1" - - (glob)
   * - - [*] "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)