Davide Libenzi <davidel@xxxxxxxxxxxxxxx> writes: > Yeah, similar. Mine is below. There's one less branch in the for loops. Thanks, will apply like this, but I am not sure if you meant windowN or just window... -- >8 -- From: Davide Libenzi <davidel@xxxxxxxxxxxxxxx> Date: Fri, 7 Nov 2008 21:24:33 -0800 Subject: [PATCH] xdiff: give up scanning similar lines early In a corner case of large files whose lines do not match uniquely, the loop to eliminate a line that matches multiple locations adjacent to a run of lines that do not uniquely match wasted too much cycles. Fix this by giving up early after scanning 100 lines in both direction. --- xdiff/xprepare.c | 15 +++++++++++++-- 1 files changed, 13 insertions(+), 2 deletions(-) diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index e87ab57..6a70cdf 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 { @@ -313,6 +312,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 -- 1.6.0.3.674.gdf99f -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html