Re: absurdly slow git-diff
On Fri, 7 Nov 2008, Linus Torvalds wrote:
Show 43 quoted lines
>
>
> On Fri, 7 Nov 2008, Davide Libenzi wrote:
> >
> > With +/- 100 lines (200 lines window):
> >
> > davide@alien:~$ time ./xdiff_test --diff 1 2 > /dev/null
> >
> > real 0m1.534s
> > user 0m1.466s
> > sys 0m0.040s
>
> I 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