Mercurial > hg
changeset 22357:9c3c3dc14a65
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
| author | Pierre-Yves David <pierre-yves.david@fb.com> |
|---|---|
| date | Sat, 30 Aug 2014 12:33:12 +0200 |
| parents | 3c8fb24334e9 |
| children | 198e2da3ee20 |
| files | mercurial/branchmap.py |
| diffstat | 1 files changed, 9 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/branchmap.py Sat Aug 30 12:20:50 2014 +0200 +++ b/mercurial/branchmap.py Sat Aug 30 12:33:12 2014 +0200 @@ -239,6 +239,10 @@ 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 @@ # 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]