view .hgtags @ 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

d40cc5aacc31ed673d9b5b24f98bee78c283062c 0.4f
1c590d34bf61e2ea12c71738e5a746cd74586157 0.4e
7eca4cfa8aad5fce9a04f7d8acadcd0452e2f34e 0.4d
b4d0c3786ad3e47beacf8412157326a32b6d25a4 0.4c
f40273b0ad7b3a6d3012fd37736d0611f41ecf54 0.5
0a28dfe59f8fab54a5118c5be4f40da34a53cdb7 0.5b
12e0fdbc57a0be78f0e817fd1d170a3615cd35da 0.6
4ccf3de52989b14c3d84e1097f59e39a992e00bd 0.6b
eac9c8efcd9bd8244e72fb6821f769f450457a32 0.6c
979c049974485125e1f9357f6bbe9c1b548a64c3 0.7
3a56574f329a368d645853e0f9e09472aee62349 0.8
6a03cff2b0f5d30281e6addefe96b993582f2eac 0.8.1
35fb62a3a673d5322f6274a44ba6456e5e4b3b37 0.9
2be3001847cb18a23c403439d9e7d0ace30804e9 0.9.1
36a957364b1b89c150f2d0e60a99befe0ee08bd3 0.9.2
27230c29bfec36d5540fbe1c976810aefecfd1d2 0.9.3
fb4b6d5fe100b0886f8bc3d6731ec0e5ed5c4694 0.9.4
23889160905a1b09fffe1c07378e9fc1827606eb 0.9.5
bae2e9c838e90a393bae3973a7850280413e091a 1.0
d5cbbe2c49cee22a9fbeb9ea41daa0ac4e26b846 1.0.1
d2375bbee6d47e62ba8e415c86e83a465dc4dce9 1.0.2
2a67430f92f15ea5159c26b09ec4839a0c549a26 1.1
3773e510d433969e277b1863c317b674cbee2065 1.1.1
11a4eb81fb4f4742451591489e2797dc47903277 1.1.2
11efa41037e280d08cfb07c09ad485df30fb0ea8 1.2
02981000012e3adf40c4849bd7b3d5618f9ce82d 1.2.1
196d40e7c885fa6e95f89134809b3ec7bdbca34b 1.3
3ef6c14a1e8e83a31226f5881b7fe6095bbfa6f6 1.3.1
31ec469f9b556f11819937cf68ee53f2be927ebf 1.4
439d7ea6fe3aa4ab9ec274a68846779153789de9 1.4.1
296a0b14a68621f6990c54fdba0083f6f20935bf 1.4.2
4aa619c4c2c09907034d9824ebb1dd0e878206eb 1.4.3
ff2704a8ded37fbebd8b6eb5ec733731d725da8a 1.5
2b01dab594167bc0dd33331dbaa6dca3dca1b3aa 1.5.1
39f725929f0c48c5fb3b90c071fc3066012456ca 1.5.2
fdcf80f26604f233dc4d8f0a5ef9d7470e317e8a 1.5.3
24fe2629c6fd0c74c90bd066e77387c2b02e8437 1.5.4
f786fc4b8764cd2a5526d259cf2f94d8a66924d9 1.6
bf1774d95bde614af3956d92b20e2a0c68c5fec7 1.6.1
c00f03a4982e467fb6b6bd45908767db6df4771d 1.6.2
ff5cec76b1c5b6be9c3bb923aae8c3c6d079d6b9 1.6.3
93d8bff78c96fe7e33237b257558ee97290048a4 1.6.4
333421b9e0f96c7bc788e5667c146a58a9440a55 1.7
4438875ec01bd0fc32be92b0872eb6daeed4d44f 1.7.1
6aff4f144ad356311318b0011df0bb21f2c97429 1.7.2
e3bf16703e2601de99e563cdb3a5d50b64e6d320 1.7.3
a6c855c32ea081da3c3b8ff628f1847ff271482f 1.7.4
2b2155623ee2559caf288fd333f30475966c4525 1.7.5
2616325766e3504c8ae7c84bd15ee610901fe91d 1.8
aa1f3be38ab127280761889d2dca906ca465b5f4 1.8.1
b032bec2c0a651ca0ddecb65714bfe6770f67d70 1.8.2
3cb1e95676ad089596bd81d0937cad37d6e3b7fb 1.8.3
733af5d9f6b22387913e1d11350fb8cb7c1487dd 1.8.4
de9eb6b1da4fc522b1cab16d86ca166204c24f25 1.9
4a43e23b8c55b4566b8200bf69fe2158485a2634 1.9.1
d629f1e89021103f1753addcef6b310e4435b184 1.9.2
351a9292e430e35766c552066ed3e87c557b803b 1.9.3
384082750f2c51dc917d85a7145748330fa6ef4d 2.0-rc
41453d55b481ddfcc1dacb445179649e24ca861d 2.0
195dbd1cef0c2f9f8bcf4ea303238105f716bda3 2.0.1
6344043924497cd06d781d9014c66802285072e4 2.0.2
db33555eafeaf9df1e18950e29439eaa706d399b 2.1-rc
2aa5b51f310fb3befd26bed99c02267f5c12c734 2.1
53e2cd303ecf8ca7c7eeebd785c34e5ed6b0f4a4 2.1.1
b9bd95e61b49c221c4cca24e6da7c946fc02f992 2.1.2
d9e2f09d5488c395ae9ddbb320ceacd24757e055 2.2-rc
00182b3d087909e3c3ae44761efecdde8f319ef3 2.2
5983de86462c5a9f42a3ad0f5e90ce5b1d221d25 2.2.1
85a358df5bbbe404ca25730c9c459b34263441dc 2.2.2
b013baa3898e117959984fc64c29d8c784d2f28b 2.2.3
a06e2681dd1786e2354d84a5fa9c1c88dd4fa3e0 2.3-rc
7f5094bb3f423fc799e471aac2aee81a7ce57a0b 2.3
072209ae4ddb654eb2d5fd35bff358c738414432 2.3.1
b3f0f9a39c4e1d0250048cd803ab03542d6f140a 2.3.2
d118a4f4fd16d9b558ec3f3e87bfee772861d2b7 2.4-rc
195ad823b5d58c68903a6153a25e3fb4ed25239d 2.4