This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2601

xdiff: reduce indent heuristic overhead
ClosedPublic

Authored by quark on Mar 3 2018, 3:07 PM.

Details

Reviewers
indygreg
durin42
Group Reviewers
hg-reviewers
Commits
rHGc420792217c8: xdiff: reduce indent heuristic overhead
rHG9f2597a6620e: xdiff: reduce indent heuristic overhead
Summary

Adds some threshold to avoid expensive cases, like:

#!python
open('a', 'w').write(" \n" * 1000000)
open('b', 'w').write(" \n" * 1000001)

The indent heuristic is O(N * 20) (N = 1000000) for the above case, and
makes diff much slower.

Before this patch (system git 2.14.2):

git diff --no-indent-heuristic a b  0.21s user 0.03s system 100% cpu 0.239 total
git diff --indent-heuristic a b     0.77s user 0.02s system 99% cpu 0.785 total

After this patch (git 2fc74f41, with xdiffi.c patched):

# with the changed xdiffi.c
git diff --indent-heuristic a b      0.16s user 0.01s system 90% cpu 0.188 total
git diff --no-indent-heuristic a b   0.18s user 0.01s system 99% cpu 0.192 total

Now turning on indent-heuristic has no visible impact on performance.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Mar 3 2018, 3:07 PM
quark updated this revision to Diff 6475.Mar 3 2018, 3:30 PM
indygreg accepted this revision.Mar 3 2018, 4:09 PM
This revision is now accepted and ready to land.Mar 3 2018, 4:09 PM
durin42 accepted this revision.Mar 3 2018, 6:12 PM
Closed by commit rHG9f2597a6620e: xdiff: reduce indent heuristic overhead (authored by quark). · Explain WhyMar 3 2018, 6:40 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/thirdparty/xdiff/xdiffi.c (38 lines)

Diff 6515

mercurial/thirdparty/xdiff/xdiffi.c

static void xdl_bug(const char *msg) static void xdl_bug(const char *msg)
{ {
fprintf(stderr, "BUG: %s\n", msg); fprintf(stderr, "BUG: %s\n", msg);
exit(1); exit(1);
} }
/* /*
* For indentation heuristic, skip searching for better slide position after
* checking MAX_BORING lines without finding an improvement. This defends the
* indentation heuristic logic against pathological cases. The value is not
* picked scientifically but should be good enough.
*/
#define MAX_BORING 100
/*
* Move back and forward change groups for a consistent and pretty diff output. * Move back and forward change groups for a consistent and pretty diff output.
* This also helps in finding joinable change groups and reducing the diff * This also helps in finding joinable change groups and reducing the diff
* size. * size.
*/ */
int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
struct xdlgroup g, go; struct xdlgroup g, go;
long earliest_end, end_matching_other; long earliest_end, end_matching_other;
long groupsize; long groupsize;
* are worse. We compute a badness "score" for each split, * are worse. We compute a badness "score" for each split,
* and add the scores for the two splits to define a * and add the scores for the two splits to define a
* "score" for each position that the group can be shifted * "score" for each position that the group can be shifted
* to. Then we pick the shift with the lowest score. * to. Then we pick the shift with the lowest score.
*/ */
long shift, best_shift = -1; long shift, best_shift = -1;
struct split_score best_score; struct split_score best_score;
for (shift = earliest_end; shift <= g.end; shift++) { /*
* This is O(N * MAX_BLANKS) (N = shift-able lines).
* Even with MAX_BLANKS bounded to a small value, a
* large N could still make this loop take several
* times longer than the main diff algorithm. The
* "boring" value is to help cut down N to something
* like (MAX_BORING + groupsize).
*
* Scan from bottom to top. So we can exit the loop
* without compromising the assumption "for a same best
* score, pick the bottommost shift".
*/
int boring = 0;
for (shift = g.end; shift >= earliest_end; shift--) {
struct split_measurement m; struct split_measurement m;
struct split_score score = {0, 0}; struct split_score score = {0, 0};
int cmp;
measure_split(xdf, shift, &m); measure_split(xdf, shift, &m);
score_add_split(&m, &score); score_add_split(&m, &score);
measure_split(xdf, shift - groupsize, &m); measure_split(xdf, shift - groupsize, &m);
score_add_split(&m, &score); score_add_split(&m, &score);
if (best_shift == -1 ||
score_cmp(&score, &best_score) <= 0) { if (best_shift == -1) {
cmp = -1;
} else {
cmp = score_cmp(&score, &best_score);
}
if (cmp < 0) {
boring = 0;
best_score.effective_indent = score.effective_indent; best_score.effective_indent = score.effective_indent;
best_score.penalty = score.penalty; best_score.penalty = score.penalty;
best_shift = shift; best_shift = shift;
} else {
boring += 1;
if (boring >= MAX_BORING)
break;
} }
} }
while (g.end > best_shift) { while (g.end > best_shift) {
if (group_slide_up(xdf, &g, flags)) if (group_slide_up(xdf, &g, flags))
xdl_bug("best shift unreached"); xdl_bug("best shift unreached");
if (group_previous(xdfo, &go)) if (group_previous(xdfo, &go))
xdl_bug("group sync broken sliding to blank line"); xdl_bug("group sync broken sliding to blank line");