view tests/test-dispatch.py @ 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

import os
from mercurial import dispatch

def testdispatch(cmd):
    """Simple wrapper around dispatch.dispatch()

    Prints command and result value, but does not handle quoting.
    """
    print "running: %s" % (cmd,)
    req = dispatch.request(cmd.split())
    result = dispatch.dispatch(req)
    print "result: %r" % (result,)


testdispatch("init test1")
os.chdir('test1')

# create file 'foo', add and commit
f = open('foo', 'wb')
f.write('foo\n')
f.close()
testdispatch("add foo")
testdispatch("commit -m commit1 -d 2000-01-01 foo")

# append to file 'foo' and commit
f = open('foo', 'ab')
f.write('bar\n')
f.close()
testdispatch("commit -m commit2 -d 2000-01-02 foo")

# check 88803a69b24 (fancyopts modified command table)
testdispatch("log -r 0")
testdispatch("log -r tip")