Re: absurdly slow git-diff
From: Davide Libenzi <hidden>
Date: 2016-06-15 22:45:37
Subsystem:
the rest · Maintainer:
Linus Torvalds
On Fri, 7 Nov 2008, Linus Torvalds wrote:
quoted hunk ↗ jump to hunk
On Fri, 7 Nov 2008, Davide Libenzi wrote:quoted
With +/- 100 lines (200 lines window): davide@alien:~$ time ./xdiff_test --diff 1 2 > /dev/null real 0m1.534s user 0m1.466s sys 0m0.040sI assume the patch is something like the appended? Linus --- xdiff/xprepare.c | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-)diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index e87ab57..4bebd76 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c@@ -318,7 +318,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { * Note that we always call this function with dis[i] > 1, so the * current line (i) is already a multimatch line. */ - for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) { + for (r = 1, rdis0 = 0, rpdis0 = 1; r < 100 && (i - r) >= s; r++) { if (!dis[i - r]) rdis0++; else if (dis[i - r] == 2)@@ -334,7 +334,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { */ if (rdis0 == 0) return 0; - for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) { + for (r = 1, rdis1 = 0, rpdis1 = 1; r < 100 && (i + r) <= e; r++) { if (!dis[i + r]) rdis1++; else if (dis[i + r] == 2)
Yeah, similar. Mine is below. There's one less branch in the for loops. - Davide
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index deba25a..3ebd87c 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c@@ -23,10 +23,9 @@ #include "xinclude.h" - #define XDL_KPDIS_RUN 4 #define XDL_MAX_EQLIMIT 1024 - +#define XDL_SIMSCAN_WINDOWN 100 typedef struct s_xdlclass {
@@ -246,6 +245,18 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { long r, rdis0, rpdis0, rdis1, rpdis1; /* + * Limits the window the is examined during the similar-lines + * scan. The loops below stops when dis[i - r] == 1 (line that + * has no match), but there are corner cases where the loop + * proceed all the way to the extremities by causing huge + * performance penalties in case of big files. + */ + if (i - s > XDL_SIMSCAN_WINDOWN) + s = i - XDL_SIMSCAN_WINDOWN; + if (e - i > XDL_SIMSCAN_WINDOWN) + e = i + XDL_SIMSCAN_WINDOWN; + + /* * Scans the lines before 'i' to find a run of lines that either * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1). * Note that we always call this function with dis[i] > 1, so the