# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 2014-08-30 10:33:12
# Node ID 9c3c3dc14a65b3923811d3edca394f45b98d4c06
# Parent  3c8fb24334e9efce745abecbfd08b511ea40b490

branchmap: pre-filter topological heads before ancestors based filtering

We know that topological heads will not be ancestors of anything, so we filter
them out to potentially reduce the range of the ancestors computation.

On a strongly headed repo this gives humble speedup:

    from 0.1984 to 0.1629

diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -239,6 +239,10 @@ class branchcache(dict):
             newbranches.setdefault(branch, []).append(r)
             if closesbranch:
                 self._closednodes.add(cl.node(r))
+
+        # fetch current topological heads to speed up filtering
+        topoheads = set(cl.headrevs())
+
         # 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)
@@ -255,8 +259,11 @@ class branchcache(dict):
             # 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.
-            ancestors = set(cl.ancestors(newheadrevs, min(bheadset)))
-            bheadset -= ancestors
+            uncertain = bheadset - topoheads
+            if uncertain:
+                floorrev = min(uncertain)
+                ancestors = set(cl.ancestors(newheadrevs, floorrev))
+                bheadset -= ancestors
             bheadrevs = sorted(bheadset)
             self[branch] = [cl.node(rev) for rev in bheadrevs]
             tiprev = bheadrevs[-1]