Patchwork [3,of,3] branchmap: pre-filter topological heads before ancestors based filtering

login
register
mail settings
Submitter Pierre-Yves David
Date Aug. 30, 2014, 3:02 p.m.
Message ID <b01aa903e3a716657b29.1409410974@marginatus.alto.octopoid.net>
Download mbox | patch
Permalink /patch/5641/
State Accepted
Headers show

Comments

Pierre-Yves David - Aug. 30, 2014, 3:02 p.m.
# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 1409394792 -7200
#      Sat Aug 30 12:33:12 2014 +0200
# Node ID b01aa903e3a716657b297f643e8931b0d0b90c09
# Parent  bf342ea7ec283b44b0d382efd8869ab8f1caa125
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
Augie Fackler - Aug. 31, 2014, 9:17 a.m.
Queued, thanks.

On Aug 30, 2014, at 5:02 PM, Pierre-Yves David <pierre-yves.david@ens-lyon.org> wrote:

> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david@fb.com>
> # Date 1409394792 -7200
> #      Sat Aug 30 12:33:12 2014 +0200
> # Node ID b01aa903e3a716657b297f643e8931b0d0b90c09
> # Parent  bf342ea7ec283b44b0d382efd8869ab8f1caa125
> 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
> @@ -237,10 +237,14 @@ class branchcache(dict):
>         for r in revgen:
>             branch, closesbranch = getbranchinfo(r)
>             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)
>         for branch, newheadrevs in newbranches.iteritems():
>             bheads = self.setdefault(branch, [])
> @@ -253,12 +257,15 @@ class branchcache(dict):
>             bheadset.update(newheadrevs)
> 
>             # 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]
>             if tiprev > self.tiprev:
>                 self.tipnode = cl.node(tiprev)
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel

Patch

diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -237,10 +237,14 @@  class branchcache(dict):
         for r in revgen:
             branch, closesbranch = getbranchinfo(r)
             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)
         for branch, newheadrevs in newbranches.iteritems():
             bheads = self.setdefault(branch, [])
@@ -253,12 +257,15 @@  class branchcache(dict):
             bheadset.update(newheadrevs)
 
             # 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]
             if tiprev > self.tiprev:
                 self.tipnode = cl.node(tiprev)