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
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)