Mercurial > hg
view tests/test-bdiff.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
author | Siddharth Agarwal <sid0@fb.com> |
---|---|
date | Mon, 26 Nov 2012 11:46:51 -0800 |
parents | eeac5e179243 |
children | 2e54aaa65afc |
line wrap: on
line source
import struct from mercurial import bdiff, mpatch def test1(a, b): d = bdiff.bdiff(a, b) c = a if d: c = mpatch.patches(a, [d]) if c != b: print "***", repr(a), repr(b) print "bad:" print repr(c)[:200] print repr(d) def test(a, b): print "***", repr(a), repr(b) test1(a, b) test1(b, a) test("a\nc\n\n\n\n", "a\nb\n\n\n") test("a\nb\nc\n", "a\nc\n") test("", "") test("a\nb\nc", "a\nb\nc") test("a\nb\nc\nd\n", "a\nd\n") test("a\nb\nc\nd\n", "a\nc\ne\n") test("a\nb\nc\n", "a\nc\n") test("a\n", "c\na\nb\n") test("a\n", "") test("a\n", "b\nc\n") test("a\n", "c\na\n") test("", "adjfkjdjksdhfksj") test("", "ab") test("", "abc") test("a", "a") test("ab", "ab") test("abc", "abc") test("a\n", "a\n") test("a\nb", "a\nb") #issue1295 def showdiff(a, b): bin = bdiff.bdiff(a, b) pos = 0 while pos < len(bin): p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12]) pos += 12 print p1, p2, repr(bin[pos:pos + l]) pos += l showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n") showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n") print "done" def testfixws(a, b, allws): c = bdiff.fixws(a, allws) if c != b: print "*** fixws", repr(a), repr(b), allws print "got:" print repr(c) testfixws(" \ta\r b\t\n", "ab\n", 1) testfixws(" \ta\r b\t\n", " a b\n", 0) testfixws("", "", 1) testfixws("", "", 0) print "done"