Mercurial > hg
annotate tests/test-bdiff.py.out @ 30561:7c0c722d568d
bdiff: early pruning of common prefix before doing expensive computations
It seems quite common that files don't change completely. New lines are often
pretty much appended, and modifications will often only change a small section
of the file which on average will be in the middle.
There can thus be a big win by pruning a common prefix before starting the more
expensive search for longest common substrings.
Worst case, it will scan through a long sequence of similar bytes without
encountering a newline. Splitlines will then have to do the same again ...
twice for each side. If similar lines are found, splitlines will save the
double iteration and hashing of the lines ... plus there will be less lines to
find common substrings in.
This change might in some cases make the algorith pick shorter or less optimal
common substrings. We can't have the cake and eat it.
This make hg --time bundle --base null -r 4.0 go from 14.5 to 15 s - a 3%
increase.
On mozilla-unified:
perfbdiff -m 3041e4d59df2
! wall 0.053088 comb 0.060000 user 0.060000 sys 0.000000 (best of 100) to
! wall 0.024618 comb 0.020000 user 0.020000 sys 0.000000 (best of 116)
perfbdiff 0e9928989e9c --alldata --count 10
! wall 0.702075 comb 0.700000 user 0.700000 sys 0.000000 (best of 15) to
! wall 0.579235 comb 0.580000 user 0.580000 sys 0.000000 (best of 18)
author | Mads Kiilerich <madski@unity3d.com> |
---|---|
date | Wed, 16 Nov 2016 19:45:35 +0100 |
parents | 96f2f50d923f |
children | 1b393a93a7df |
rev | line source |
---|---|
30427
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
1 test 'a\nc\n\n\n\n' 'a\nb\n\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
2 test 'a\nb\nc\n' 'a\nc\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
3 test '' '' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
4 test 'a\nb\nc' 'a\nb\nc' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
5 test 'a\nb\nc\nd\n' 'a\nd\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
6 test 'a\nb\nc\nd\n' 'a\nc\ne\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
7 test 'a\nb\nc\n' 'a\nc\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
8 test 'a\n' 'c\na\nb\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
9 test 'a\n' '' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
10 test 'a\n' 'b\nc\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
11 test 'a\n' 'c\na\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
12 test '' 'adjfkjdjksdhfksj' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
13 test '' 'ab' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
14 test '' 'abc' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
15 test 'a' 'a' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
16 test 'ab' 'ab' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
17 test 'abc' 'abc' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
18 test 'a\n' 'a\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
19 test 'a\nb' 'a\nb' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
20 showdiff( |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
21 'x\n\nx\n\nx\n\nx\n\nz\n', |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
22 'x\n\nx\n\ny\n\nx\n\nx\n\nz\n'): |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
23 'x\n\nx\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
24 6 6 '' -> 'y\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
25 'x\n\nx\n\nz\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
26 showdiff( |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
27 'x\n\nx\n\nx\n\nx\n\nz\n', |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
28 'x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n'): |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
29 'x\n\nx\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
30 6 6 '' -> 'y\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
31 'x\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
32 9 9 '' -> 'y\n\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
33 'x\n\nz\n' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
34 showdiff( |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
35 'a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n', |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
36 'a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n'): |
30561
7c0c722d568d
bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents:
30433
diff
changeset
|
37 'a\nb\nb\n' |
7c0c722d568d
bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents:
30433
diff
changeset
|
38 6 6 '' -> 'a\nb\nb\nb\nc\n.\n' |
7c0c722d568d
bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents:
30433
diff
changeset
|
39 'b\nc\n.\nd\ne\n' |
30427
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
40 16 18 '.\n' -> '' |
ede7bc45bf0a
tests: make test-bdiff.py easier to maintain
Mads Kiilerich <madski@unity3d.com>
parents:
29013
diff
changeset
|
41 'f\n' |
400
8b067bde6679
Add a fast binary diff extension (not yet used)
mpm@selenic.com
parents:
diff
changeset
|
42 done |
15530
eeac5e179243
mdiff: replace wscleanup() regexps with C loops
Patrick Mezard <pmezard@gmail.com>
parents:
8449
diff
changeset
|
43 done |
30431
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
44 Nice diff for a trivial change: |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
45 showdiff( |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
46 '<0\n-\n<1\n-\n<2\n-\n<3\n-\n<4\n-\n', |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
47 '>0\n-\n>1\n-\n>2\n-\n>3\n-\n>4\n-\n'): |
30431
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
48 0 3 '<0\n' -> '>0\n' |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
49 '-\n' |
30431
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
50 5 8 '<1\n' -> '>1\n' |
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
51 '-\n' |
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
52 10 13 '<2\n' -> '>2\n' |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
53 '-\n' |
30431
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
54 15 18 '<3\n' -> '>3\n' |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
55 '-\n' |
30431
8c0c75aa3ff4
bdiff: give slight preference to longest matches in the middle of the B side
Mads Kiilerich <madski@unity3d.com>
parents:
30429
diff
changeset
|
56 20 23 '<4\n' -> '>4\n' |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
57 '-\n' |
30432
3633403888ae
bdiff: give slight preference to appending lines
Mads Kiilerich <madski@unity3d.com>
parents:
30431
diff
changeset
|
58 Diff 1 to 3 lines - preference for appending: |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
59 showdiff( |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
60 'a\n', |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
61 'a\na\na\n'): |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
62 'a\n' |
30432
3633403888ae
bdiff: give slight preference to appending lines
Mads Kiilerich <madski@unity3d.com>
parents:
30431
diff
changeset
|
63 2 2 '' -> 'a\na\n' |
3633403888ae
bdiff: give slight preference to appending lines
Mads Kiilerich <madski@unity3d.com>
parents:
30431
diff
changeset
|
64 Diff 1 to 5 lines - preference for appending: |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
65 showdiff( |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
66 'a\n', |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
67 'a\na\na\na\na\n'): |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
68 'a\n' |
30432
3633403888ae
bdiff: give slight preference to appending lines
Mads Kiilerich <madski@unity3d.com>
parents:
30431
diff
changeset
|
69 2 2 '' -> 'a\na\na\na\n' |
30433
96f2f50d923f
bdiff: give slight preference to removing trailing lines
Mads Kiilerich <madski@unity3d.com>
parents:
30432
diff
changeset
|
70 Diff 3 to 1 lines - preference for removing trailing lines: |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
71 showdiff( |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
72 'a\na\na\n', |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
73 'a\n'): |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
74 'a\n' |
30433
96f2f50d923f
bdiff: give slight preference to removing trailing lines
Mads Kiilerich <madski@unity3d.com>
parents:
30432
diff
changeset
|
75 2 6 'a\na\n' -> '' |
96f2f50d923f
bdiff: give slight preference to removing trailing lines
Mads Kiilerich <madski@unity3d.com>
parents:
30432
diff
changeset
|
76 Diff 5 to 1 lines - preference for removing trailing lines: |
30428
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
77 showdiff( |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
78 'a\na\na\na\na\n', |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
79 'a\n'): |
3743e5dbb824
tests: explore some bdiff cases
Mads Kiilerich <madski@unity3d.com>
parents:
30427
diff
changeset
|
80 'a\n' |
30433
96f2f50d923f
bdiff: give slight preference to removing trailing lines
Mads Kiilerich <madski@unity3d.com>
parents:
30432
diff
changeset
|
81 2 10 'a\na\na\na\n' -> '' |