| Submitter | Matt Mackall |
|---|---|
| Date | April 23, 2016, 3:41 p.m. |
| Message ID | <5a887b289abf6d5e7947.1461426078@ruin.waste.org> |
| Download | mbox | patch |
| Permalink | /patch/14773/ |
| State | Superseded |
| Commit | f1ca249696ed61fbc1f5e4076cfadd2a039293f8 |
| Headers | show |
Comments
On Sat, 23 Apr 2016 10:41:18 -0500, Matt Mackall wrote: > # HG changeset patch > # User Matt Mackall <mpm@selenic.com> > # Date 1461294251 18000 > # Thu Apr 21 22:04:11 2016 -0500 > # Branch stable > # Node ID 5a887b289abf6d5e7947fa3fac98a658cbdcebe1 > # Parent 7d0c61d568ac831fd59f6aaf480418acedae1eda > bdiff: balance recursion to avoid quadratic behavior (issue4704) > 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. > +++ b/tests/test-issue4074.t Thu Apr 21 22:04:11 2016 -0500 > @@ -0,0 +1,27 @@ > +A script to generate nasty diff worst-case scenarios: Should we guard the test by '#require no-pure' ?
On Tue, Apr 26, 2016 at 12:45:25AM +0900, Yuya Nishihara wrote: > On Sat, 23 Apr 2016 10:41:18 -0500, Matt Mackall wrote: > > # HG changeset patch > > # User Matt Mackall <mpm@selenic.com> > > # Date 1461294251 18000 > > # Thu Apr 21 22:04:11 2016 -0500 > > # Branch stable > > # Node ID 5a887b289abf6d5e7947fa3fac98a658cbdcebe1 > > # Parent 7d0c61d568ac831fd59f6aaf480418acedae1eda > > bdiff: balance recursion to avoid quadratic behavior (issue4704) > > > 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. > > > +++ b/tests/test-issue4074.t Thu Apr 21 22:04:11 2016 -0500 > > @@ -0,0 +1,27 @@ > > +A script to generate nasty diff worst-case scenarios: > > Should we guard the test by '#require no-pure' ? Absolutely. > _______________________________________________ > Mercurial-devel mailing list > Mercurial-devel@mercurial-scm.org > https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Patch
diff -r 7d0c61d568ac -r 5a887b289abf mercurial/bdiff.c --- a/mercurial/bdiff.c Thu Apr 21 21:53:18 2016 -0500 +++ b/mercurial/bdiff.c Thu Apr 21 22:04:11 2016 -0500 @@ -148,7 +148,7 @@ static int longest_match(struct line *a, struct line *b, struct pos *pos, int a1, int a2, int b1, int b2, int *omi, int *omj) { - int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k; + int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k, half = (a1 + a2) / 2; for (i = a1; i < a2; i++) { /* skip all lines in b after the current block */ @@ -165,8 +165,9 @@ pos[j].pos = i; pos[j].len = k; - /* best match so far? */ - if (k > mk || (k == mk && i <= mi)) { + /* best match so far? we prefer matches closer + to the middle to balance recursion */ + if (k > mk || (k == mk && (i <= mi || i < half))) { mi = i; mj = j; mk = k; diff -r 7d0c61d568ac -r 5a887b289abf tests/test-issue4074.t --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test-issue4074.t Thu Apr 21 22:04:11 2016 -0500 @@ -0,0 +1,27 @@ +A script to generate nasty diff worst-case scenarios: + + $ cat > s.py <<EOF + > import random + > for x in xrange(100000): + > print + > if random.randint(0, 100) >= 50: + > x += 1 + > print hex(x) + > EOF + + $ hg init a + $ cd a + +Check in a big file: + + $ python ../s.py > a + $ hg ci -qAm0 + +Modify it: + + $ python ../s.py > a + +Time a check-in, should never take more than 10 seconds user time: + + $ hg ci --time -m1 + time: real .* secs .user [0-9][.].* sys .* (re)