diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -443,33 +443,65 @@
             if closesbranch:
                 self._closednodes.add(cl.node(r))
 
-        # fetch current topological heads to speed up filtering
-        topoheads = set(cl.headrevs())
-
         # new tip revision which we found after iterating items from new
         # branches
         ntiprev = self.tiprev
 
-        # if older branchheads are reachable from new ones, they aren't
-        # really branchheads. Note checking parents is insufficient:
-        # 1 (branch a) -> 2 (branch b) -> 3 (branch a)
+        # Delay fetching the topological heads until they are needed.
+        # A repository without non-continous branches can skip this part.
+        topoheads = None
+
+        # If a changeset is visible, its parents must be visible too, so
+        # use the faster unfiltered parent accessor.
+        parentrevs = repo.unfiltered().changelog.parentrevs
+
         for branch, newheadrevs in pycompat.iteritems(newbranches):
+            # The set of branchheads is the union of the existing branchheads
+            # with the heads of new revisions of that branch, but without
+            # existing branchheads that are ancestors of new revisions.
+            # The latter condition is necessary for non-continous branches,
+            # i.e. 1 (branch a) -> 2 (branch b) -> 3 (branch a).
+            #
+            # The newrev loop processes all new revisions in order and updates
+            # the branchheads for the simple case of continous branches.
+            # The sorting ensures that parents are processed first and the root
+            # of a potential non-continous branch is seen first.
+            # It followes that all revisions that are not a child of the branch
+            # are candidates for such branches and therefore kept on the
+            # uncertain set. The exception is a local branch root with no
+            # pre-existing branchheads. This is the initial start of a branch
+            # and safe.
+            #
+            # If the newrev loop left any uncertain candidates for potential
+            # non-continous branches around, further checks are necessary.
+            # If all the remaining pre-existing branchheads (i.e. those without
+            # a child in the new revision set) are still topological heads,
+            # they are automatically also branchheads. Otherwise a full
+            # ancestor check is necessary to filter out obsoleted branchheads.
+
             bheads = self._entries.setdefault(branch, [])
             bheadset = {cl.rev(node) for node in bheads}
-
-            # This have been tested True on all internal usage of this function.
-            # run it again in case of doubt
-            # assert not (set(bheadrevs) & set(newheadrevs))
-            bheadset.update(newheadrevs)
+            uncertain = set()
+            for newrev in sorted(newheadrevs):
+                parents = [p for p in parentrevs(newrev) if p != nullrev]
+                gotit = False
+                for p in parents:
+                    if p in bheadset:
+                        bheadset.remove(p)
+                        gotit = True
+                    elif getbranchinfo(p)[0] == branch:
+                        gotit = True
+                if not gotit and bheadset:
+                    uncertain.add(newrev)
+                bheadset.add(newrev)
 
-            # This prunes out two kinds of heads - heads that are superseded by
-            # a head in newheadrevs, and newheadrevs that are not heads because
-            # an existing head is their descendant.
-            uncertain = bheadset - topoheads
             if uncertain:
-                floorrev = min(uncertain)
-                ancestors = set(cl.ancestors(newheadrevs, floorrev))
-                bheadset -= ancestors
+                if topoheads is None:
+                    topoheads = set(cl.headrevs())
+                if bheadset - topoheads:
+                    floorrev = min(bheadset)
+                    ancestors = set(cl.ancestors(newheadrevs, floorrev))
+                    bheadset -= ancestors
             bheadrevs = sorted(bheadset)
             self[branch] = [cl.node(rev) for rev in bheadrevs]
             tiprev = bheadrevs[-1]
diff --git a/relnotes/next b/relnotes/next
--- a/relnotes/next
+++ b/relnotes/next
@@ -39,6 +39,10 @@
 
  * External hooks are now called with `HGPLAIN=1` preset.
 
+ * The `branchmap` cache is updated more intelligently and can be
+   significantly faster for repositories with many branches and changesets.
+
+
 == New Experimental Features ==
 
 * `experimental.single-head-per-branch:public-changes-only` can be used