This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9631

branchmap: avoid ancestor computations in absence of non-continous branches
ClosedPublic

Authored by joerg.sonnenberger on Dec 18 2020, 8:45 AM.

Details

Reviewers
marmoute
Group Reviewers
hg-reviewers
Commits
rHGc4b792fa109e: branchmap: avoid ancestor computations in absence of non-continous branches
rHGf5d7df7262ec: branchmap: avoid ancestor computations in absence of non-continous branches
Summary

The branchhead computation is one of the more heavy operations for
bigger repositories as it has to scan all changesets and potentially
involves the expensive computation of the ancestor sets. Redo the
computation to handle the common cases directly and use tighter
conditions for when the ancestor scan is necessary. Most importantly,
avoid it completely if the non-continous branches are processed in one
update as seen in the initial computation after a clone.

For the Mercurial repository, it gives a small 2-3% performance boost.
For the NetBSD test repository, it cuts the time in half.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

joerg.sonnenberger retitled this revision from branchmap: avoid ancestor computations for absent non-continous branches to branchmap: avoid ancestor computations in absence of non-continous branches.Dec 18 2020, 8:52 AM
joerg.sonnenberger updated this revision to Diff 24393.
marmoute requested changes to this revision.Dec 18 2020, 9:01 AM
marmoute added a subscriber: marmoute.

I did not had time to actually look at the code, but from IRC discussion with Joerg. I suspect this code breaks on the following graph:

A4
|\
| \
|  B1
|  |
A2 A3
| /
|/
|
A1

We need to make sure they are properly tested (which could be the case already)

This revision now requires changes to proceed.Dec 18 2020, 9:01 AM
marmoute added a comment.Jan 13 2021, 10:34 AM

The logic looks sound.

I think we can push this optimization further around topological heads.

  • Topological heads does not need to be put in the uncertain set (alternatively → they can be filtered before we try to resolve the uncertain set).
  • Topological heads are "certain" to be heads to any topo-heads < to the first uncertain heads can be "skipped" as it won't contribut to the filtering. That can significatly increase the "floor" we use for ancestors computation speeding this up.

I am fine with such optimisation to happens as follow up.

mercurial/branchmap.py
520–521

Not that in theory, turning cl.ancestors into a set can be quite expensive. The return of ancestors is a expected to be lazy ancestors object expected to be good at membership test. So I would expect something like that to be faster:

ancestors = cl.ancestors(newheadrevs, floorrev) #floorrev is non-necessary
certain = {r for r in uncertain if r not in ancestors}

(and if it is not, we should fix lazy ancestors)

marmoute accepted this revision.Jan 13 2021, 10:35 AM
joerg.sonnenberger added a comment.Jan 13 2021, 11:24 AM

The meaning of the uncertain set has changed somewhat. It is the set of changesets that might have a redundant branchhead as ancestor. As such, the topological heads don't help to reduce the uncertain set.

mercurial/branchmap.py
520–521

At least the Python version doesn't seem to cache the computed ancestors, so it would recompute the set when len(uncertain) > 1?

marmoute added a comment.Jan 13 2021, 11:33 AM

note: I a seeing weird number when checking this against mozilla-unified.

old time: ! wall 1.913970 comb 1.910000 user 1.870000 sys 0.040000 (median of 5)
new_time: ! wall 2.269365 comb 2.260000 user 2.240000 sys 0.020000 (median of 5)

I will rerun more test on a more stable machine and come back with more number

joerg.sonnenberger added a commit: rHGf5d7df7262ec: branchmap: avoid ancestor computations in absence of non-continous branches.Jan 13 2021, 2:41 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGf5d7df7262ec: branchmap: avoid ancestor computations in absence of non-continous branches (authored by joerg.sonnenberger). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/branchmap.py (85 lines)
Mrelnotes/next (4 lines)
Mtests/test-branches.t (254 lines)

Diff 24814

mercurial/branchmap.py

newbranches = {} newbranches = {}
getbranchinfo = repo.revbranchcache().branchinfo getbranchinfo = repo.revbranchcache().branchinfo
for r in revgen: for r in revgen:
branch, closesbranch = getbranchinfo(r) branch, closesbranch = getbranchinfo(r)
newbranches.setdefault(branch, []).append(r) newbranches.setdefault(branch, []).append(r)
if closesbranch: if closesbranch:
self._closednodes.add(cl.node(r)) 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 # new tip revision which we found after iterating items from new
# branches # branches
ntiprev = self.tiprev ntiprev = self.tiprev
# if older branchheads are reachable from new ones, they aren't # Delay fetching the topological heads until they are needed.
# really branchheads. Note checking parents is insufficient: # A repository without non-continous branches can skip this part.
# 1 (branch a) -> 2 (branch b) -> 3 (branch a) 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): for branch, newheadrevs in pycompat.iteritems(newbranches):
# For every branch, compute the new branchheads.
# A branchhead is a revision such that no descendant is on
# the same branch.
#
# The branchheads are computed iteratively in revision order.
# This ensures topological order, i.e. parents are processed
# before their children. Ancestors are inclusive here, i.e.
# any revision is an ancestor of itself.
#
# Core observations:
# - The current revision is always a branchhead for the
# repository up to that point.
# - It is the first revision of the branch if and only if
# there was no branchhead before. In that case, it is the
# only branchhead as there are no possible ancestors on
# the same branch.
# - If a parent is on the same branch, a branchhead can
# only be an ancestor of that parent, if it is parent
# itself. Otherwise it would have been removed as ancestor
# of that parent before.
# - Therefore, if all parents are on the same branch, they
# can just be removed from the branchhead set.
# - If one parent is on the same branch and the other is not
# and there was exactly one branchhead known, the existing
# branchhead can only be an ancestor if it is the parent.
# Otherwise it would have been removed as ancestor of
# the parent before. The other parent therefore can't have
# a branchhead as ancestor.
# - In all other cases, the parents on different branches
# could have a branchhead as ancestor. Those parents are
# kept in the "uncertain" set. If all branchheads are also
# topological heads, they can't have descendants and further
# checks can be skipped. Otherwise, the ancestors of the
# "uncertain" set are removed from branchheads.
# This computation is heavy and avoided if at all possible.
bheads = self._entries.setdefault(branch, []) bheads = self._entries.setdefault(branch, [])
bheadset = {cl.rev(node) for node in bheads} bheadset = {cl.rev(node) for node in bheads}
uncertain = set()
for newrev in sorted(newheadrevs):
if not bheadset:
bheadset.add(newrev)
continue
parents = [p for p in parentrevs(newrev) if p != nullrev]
samebranch = set()
otherbranch = set()
for p in parents:
if p in bheadset or getbranchinfo(p)[0] == branch:
samebranch.add(p)
else:
otherbranch.add(p)
if otherbranch and not (len(bheadset) == len(samebranch) == 1):
uncertain.update(otherbranch)
bheadset.difference_update(samebranch)
bheadset.add(newrev)
# 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)
# 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: if uncertain:
floorrev = min(uncertain) if topoheads is None:
topoheads = set(cl.headrevs())
if bheadset - topoheads:
floorrev = min(bheadset)
ancestors = set(cl.ancestors(newheadrevs, floorrev)) ancestors = set(cl.ancestors(newheadrevs, floorrev))
bheadset -= ancestors bheadset -= ancestors
marmouteUnsubmitted
Not Done

Not that in theory, turning cl.ancestors into a set can be quite expensive. The return of ancestors is a expected to be lazy ancestors object expected to be good at membership test. So I would expect something like that to be faster:

ancestors = cl.ancestors(newheadrevs, floorrev) #floorrev is non-necessary
certain = {r for r in uncertain if r not in ancestors}

(and if it is not, we should fix lazy ancestors)

marmoute: Not that in theory, turning cl.ancestors into a set can be quite expensive. The return of…
joerg.sonnenbergerAuthorUnsubmitted
Done

At least the Python version doesn't seem to cache the computed ancestors, so it would recompute the set when len(uncertain) > 1?

joerg.sonnenberger: At least the Python version doesn't seem to cache the computed ancestors, so it would recompute…
bheadrevs = sorted(bheadset) bheadrevs = sorted(bheadset)
self[branch] = [cl.node(rev) for rev in bheadrevs] self[branch] = [cl.node(rev) for rev in bheadrevs]
tiprev = bheadrevs[-1] tiprev = bheadrevs[-1]
if tiprev > ntiprev: if tiprev > ntiprev:
ntiprev = tiprev ntiprev = tiprev
if ntiprev > self.tiprev: if ntiprev > self.tiprev:
self.tiprev = ntiprev self.tiprev = ntiprev

relnotes/next

showing 2 or 3 snapshots of the conflicting pieces of code, it showing 2 or 3 snapshots of the conflicting pieces of code, it
shows one snapshot and a diff. This may be useful when at least one shows one snapshot and a diff. This may be useful when at least one
side of the conflict is similar to the base. The new marker style side of the conflict is similar to the base. The new marker style
is also supported by "premerge" as is also supported by "premerge" as
`merge-tools.<tool>.premerge=keep-mergediff`. `merge-tools.<tool>.premerge=keep-mergediff`.
* External hooks are now called with `HGPLAIN=1` preset. * 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 == == New Experimental Features ==
* `experimental.single-head-per-branch:public-changes-only` can be used * `experimental.single-head-per-branch:public-changes-only` can be used
restrict the single head check to public revision. This is useful for restrict the single head check to public revision. This is useful for
overlay repository that have both a publishing and non-publishing view overlay repository that have both a publishing and non-publishing view
of the same storage. of the same storage.

tests/test-branches.t

$ hg ci -m "branch closed" --close-branch $ hg ci -m "branch closed" --close-branch
abort: can only close branch heads abort: can only close branch heads
(use --force-close-branch to close branch from a non-head changeset) (use --force-close-branch to close branch from a non-head changeset)
[10] [10]
$ hg ci -m "branch closed" --force-close-branch $ hg ci -m "branch closed" --force-close-branch
created new head created new head
$ cd ..
Test various special cases for the branchmap
--------------------------------------------
Basic fork of the same branch
$ hg init branchmap-testing1
$ cd branchmap-testing1
$ hg debugbuild '@A . :base . :p1 *base /p1'
$ hg log -G
o changeset: 3:71ca9a6d524e
|\ branch: A
| | tag: tip
| | parent: 2:a3b807b3ff0b
| | parent: 1:99ba08759bc7
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:03 1970 +0000
| | summary: r3
| |
| o changeset: 2:a3b807b3ff0b
| | branch: A
| | parent: 0:2ab8003a1750
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:02 1970 +0000
| | summary: r2
| |
o | changeset: 1:99ba08759bc7
|/ branch: A
| tag: p1
| user: debugbuilddag
| date: Thu Jan 01 00:00:01 1970 +0000
| summary: r1
|
o changeset: 0:2ab8003a1750
branch: A
tag: base
user: debugbuilddag
date: Thu Jan 01 00:00:00 1970 +0000
summary: r0
$ hg branches
A 3:71ca9a6d524e
$ hg clone -r 1 -r 2 . ../branchmap-testing1-clone
adding changesets
adding manifests
adding file changes
added 3 changesets with 0 changes to 0 files (+1 heads)
new changesets 2ab8003a1750:a3b807b3ff0b
updating to branch A
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd ../branchmap-testing1-clone
$ hg pull ../branchmap-testing1
pulling from ../branchmap-testing1
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 0 changes to 0 files (-1 heads)
new changesets 71ca9a6d524e
(run 'hg update' to get a working copy)
$ hg branches
A 3:71ca9a6d524e
$ cd ..
Switching to a different branch and back
$ hg init branchmap-testing2
$ cd branchmap-testing2
$ hg debugbuild '@A . @B . @A .'
$ hg log -G
o changeset: 2:9699e9f260b5
| branch: A
| tag: tip
| user: debugbuilddag
| date: Thu Jan 01 00:00:02 1970 +0000
| summary: r2
|
o changeset: 1:0bc7d348d965
| branch: B
| user: debugbuilddag
| date: Thu Jan 01 00:00:01 1970 +0000
| summary: r1
|
o changeset: 0:2ab8003a1750
branch: A
user: debugbuilddag
date: Thu Jan 01 00:00:00 1970 +0000
summary: r0
$ hg branches
A 2:9699e9f260b5
B 1:0bc7d348d965 (inactive)
$ hg clone -r 1 . ../branchmap-testing2-clone
adding changesets
adding manifests
adding file changes
added 2 changesets with 0 changes to 0 files
new changesets 2ab8003a1750:0bc7d348d965
updating to branch B
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd ../branchmap-testing2-clone
$ hg pull ../branchmap-testing2
pulling from ../branchmap-testing2
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 0 changes to 0 files
new changesets 9699e9f260b5
(run 'hg update' to get a working copy)
$ hg branches
A 2:9699e9f260b5
B 1:0bc7d348d965 (inactive)
$ cd ..
A fork on a branch switching to a different branch and back
is still collecting the fork.
$ hg init branchmap-testing3
$ cd branchmap-testing3
$ hg debugbuild '@A . :base . :p1 *base @B . @A /p1'
$ hg log -G
o changeset: 4:3614a1711d23
|\ branch: A
| | tag: tip
| | parent: 3:e9c8abcf65aa
| | parent: 1:99ba08759bc7
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:04 1970 +0000
| | summary: r4
| |
| o changeset: 3:e9c8abcf65aa
| | branch: B
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:03 1970 +0000
| | summary: r3
| |
| o changeset: 2:a3b807b3ff0b
| | branch: A
| | parent: 0:2ab8003a1750
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:02 1970 +0000
| | summary: r2
| |
o | changeset: 1:99ba08759bc7
|/ branch: A
| tag: p1
| user: debugbuilddag
| date: Thu Jan 01 00:00:01 1970 +0000
| summary: r1
|
o changeset: 0:2ab8003a1750
branch: A
tag: base
user: debugbuilddag
date: Thu Jan 01 00:00:00 1970 +0000
summary: r0
$ hg branches
A 4:3614a1711d23
B 3:e9c8abcf65aa (inactive)
$ hg clone -r 1 -r 3 . ../branchmap-testing3-clone
adding changesets
adding manifests
adding file changes
added 4 changesets with 0 changes to 0 files (+1 heads)
new changesets 2ab8003a1750:e9c8abcf65aa
updating to branch A
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd ../branchmap-testing3-clone
$ hg pull ../branchmap-testing3
pulling from ../branchmap-testing3
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 0 changes to 0 files (-1 heads)
new changesets 3614a1711d23
(run 'hg update' to get a working copy)
$ hg branches
A 4:3614a1711d23
B 3:e9c8abcf65aa (inactive)
$ cd ..
Intermediary parents are on different branches.
$ hg init branchmap-testing4
$ cd branchmap-testing4
$ hg debugbuild '@A . @B :base . @A :p1 *base @C . @A /p1'
$ hg log -G
o changeset: 4:4bf67499b70a
|\ branch: A
| | tag: tip
| | parent: 3:4a546028fa8f
| | parent: 1:0bc7d348d965
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:04 1970 +0000
| | summary: r4
| |
| o changeset: 3:4a546028fa8f
| | branch: C
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:03 1970 +0000
| | summary: r3
| |
| o changeset: 2:a3b807b3ff0b
| | branch: A
| | parent: 0:2ab8003a1750
| | user: debugbuilddag
| | date: Thu Jan 01 00:00:02 1970 +0000
| | summary: r2
| |
o | changeset: 1:0bc7d348d965
|/ branch: B
| tag: p1
| user: debugbuilddag
| date: Thu Jan 01 00:00:01 1970 +0000
| summary: r1
|
o changeset: 0:2ab8003a1750
branch: A
tag: base
user: debugbuilddag
date: Thu Jan 01 00:00:00 1970 +0000
summary: r0
$ hg branches
A 4:4bf67499b70a
C 3:4a546028fa8f (inactive)
B 1:0bc7d348d965 (inactive)
$ hg clone -r 1 -r 3 . ../branchmap-testing4-clone
adding changesets
adding manifests
adding file changes
added 4 changesets with 0 changes to 0 files (+1 heads)
new changesets 2ab8003a1750:4a546028fa8f
updating to branch B
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd ../branchmap-testing4-clone
$ hg pull ../branchmap-testing4
pulling from ../branchmap-testing4
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 0 changes to 0 files (-1 heads)
new changesets 4bf67499b70a
(run 'hg update' to get a working copy)
$ hg branches
A 4:4bf67499b70a
C 3:4a546028fa8f (inactive)
B 1:0bc7d348d965 (inactive)
$ cd ..