Mercurial > hg
view tests/test-histedit-outgoing.t @ 17970:0b03454abae7
ancestor: faster algorithm for difference of ancestor sets
One of the major reasons rebase is slow in large repositories is
the computation of the detach set: the set of ancestors of the
changesets to rebase not in the destination parent. This is currently
done via a revset that does two walks all the way to the root of
the DAG. Instead of doing that, to find ancestors of a set <revs>
not in another set <common> we walk up the tree in reverse revision
number order, maintaining sets of nodes visited from <revs>, <common>
or both.
For the common case where the sets are close both topologically and
in revision number (relative to repository size), this has been
found to speed up rebase by around 15-20%. When the nodes are farther
apart and the DAG is highly branching, it is harder to say which
would win.
Here's how long computing the detach set takes in a linear repository
with over 400000 changesets, rebasing near tip:
Rebasing across 4 changesets
Revset method: 2.2s
New algorithm: 0.00015s
Rebasing across 250 changesets
Revset method: 2.2s
New algorithm: 0.00069s
Rebasing across 10000 changesets
Revset method: 2.4s
New algorithm: 0.019s
author | Siddharth Agarwal <sid0@fb.com> |
---|---|
date | Mon, 26 Nov 2012 11:46:51 -0800 |
parents | f3a7f05f474a |
children | 0023a6e49268 |
line wrap: on
line source
$ cat >> $HGRCPATH <<EOF > [extensions] > graphlog= > histedit= > EOF $ initrepos () > { > hg init r > cd r > for x in a b c ; do > echo $x > $x > hg add $x > hg ci -m $x > done > cd .. > hg clone r r2 | grep -v updating > cd r2 > for x in d e f ; do > echo $x > $x > hg add $x > hg ci -m $x > done > cd .. > hg init r3 > cd r3 > for x in g h i ; do > echo $x > $x > hg add $x > hg ci -m $x > done > cd .. > } $ initrepos 3 files updated, 0 files merged, 0 files removed, 0 files unresolved show the edit commands offered by outgoing $ cd r2 $ HGEDITOR=cat hg histedit --outgoing ../r | grep -v comparing | grep -v searching pick 055a42cdd887 3 d pick e860deea161a 4 e pick 652413bf663e 5 f # Edit history between 055a42cdd887 and 652413bf663e # # Commands: # p, pick = use commit # e, edit = use commit, but stop for amending # f, fold = use commit, but fold into previous commit (combines N and N-1) # d, drop = remove commit from history # m, mess = edit message without changing commit content # 0 files updated, 0 files merged, 0 files removed, 0 files unresolved $ cd .. show the error from unrelated repos $ cd r3 $ HGEDITOR=cat hg histedit --outgoing ../r | grep -v comparing | grep -v searching abort: repository is unrelated [1] $ cd .. show the error from unrelated repos $ cd r3 $ HGEDITOR=cat hg histedit --force --outgoing ../r comparing with ../r searching for changes warning: repository is unrelated pick 2a4042b45417 0 g pick 68c46b4927ce 1 h pick 51281e65ba79 2 i # Edit history between 2a4042b45417 and 51281e65ba79 # # Commands: # p, pick = use commit # e, edit = use commit, but stop for amending # f, fold = use commit, but fold into previous commit (combines N and N-1) # d, drop = remove commit from history # m, mess = edit message without changing commit content # 0 files updated, 0 files merged, 0 files removed, 0 files unresolved $ cd ..