bdiff: balance recursion to avoid quadratic behavior (issue4704)
For highly structured files like JSON or XML dumps with large numbers
of duplicate lines (eg braces) and isolated matching lines, bdiff
could find large numbers of equally good spans. Because it prefers
earlier matches, this would result in pathologically unbalance
recursion that resulted in quadratic performance.
This patch makes it prefer matches closer to the middle that tend to
balance recursion. This change improves the speed of a pathological
test case from 1100s to 9s.
Included is a smaller test that has a roughly 50x safety margin on the
performance it accepts. It's likely to fail on pure builds because
difflib also has a recursion-balancing problem.
$ hg init test
$ cd test
$ echo foo>foo
$ hg addremove
adding foo
$ hg commit -m "1"
$ hg verify
checking changesets
checking manifests
crosschecking files in changesets and manifests
checking files
1 files, 1 changesets, 1 total revisions
$ hg clone . ../branch
updating to branch default
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cd ../branch
$ hg co
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ echo bar>>foo
$ hg commit -m "2"
$ cd ../test
$ hg pull ../branch
pulling from ../branch
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 1 changes to 1 files
(run 'hg update' to get a working copy)
$ hg verify
checking changesets
checking manifests
crosschecking files in changesets and manifests
checking files
1 files, 2 changesets, 2 total revisions
$ hg co
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ cat foo
foo
bar
$ hg manifest --debug
6f4310b00b9a147241b071a60c28a650827fb03d 644 foo
update to rev 0 with a date
$ hg upd -d foo 0
abort: you can't specify a revision and a date
[255]
$ cd ..