Mercurial > hg
annotate tests/test-dirstate-race.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 | 28e2e3804f2e |
children | c850f0ed54c1 |
rev | line source |
---|---|
12279 | 1 $ hg init |
2 $ echo a > a | |
3 $ hg add a | |
4 $ hg commit -m test | |
5 | |
6 Do we ever miss a sub-second change?: | |
6327
6d952dc2abc9
dirstate: refactor granularity code, add a test
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
7 |
12279 | 8 $ for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20; do |
9 > hg co -qC 0 | |
10 > echo b > a | |
11 > hg st | |
12 > done | |
13 M a | |
14 M a | |
15 M a | |
16 M a | |
17 M a | |
18 M a | |
19 M a | |
20 M a | |
21 M a | |
22 M a | |
23 M a | |
24 M a | |
25 M a | |
26 M a | |
27 M a | |
28 M a | |
29 M a | |
30 M a | |
31 M a | |
32 M a | |
6327
6d952dc2abc9
dirstate: refactor granularity code, add a test
Matt Mackall <mpm@selenic.com>
parents:
diff
changeset
|
33 |