Re: absurdly slow git-diff

From

Junio C Hamano <gitster@pobox.com>

Date

Nov 8, 2008, 05:30 UTC

Message-ID

<7v7i7eeqcz.fsf@gitster.siamese.dyndns.org>

In-Reply-To

<alpine.DEB.1.10.0811071547080.8736@alien.or.mcafeemobile.com>

Davide Libenzi <davidel@xmailserver.org> writes:

> Yeah, similar. Mine is below. There's one less branch in the for loops.

-- >8 --
From: Davide Libenzi <davidel@xmailserver.org>
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