git diff is slow (--patience is fast)

git diff is slow (--patience is fast)

[Marat Radchenko]

Warning, downloaded files are 7.5Mb each.

~ $ git --version
git version 1.7.6
~ $ mkdir tmp
~ $ cd tmp
~/tmp $ git init
Initialized empty Git repository in /home/marat/tmp/.git/
~/tmp $ wget http://slonopotamus.org/git-diff/foo 2> /dev/null 
~/tmp $ git add -A
~/tmp $ git commit -am "initial"
[master (root-commit) 6b68e83] initial
 1 files changed, 410461 insertions(+), 0 deletions(-)
 create mode 100644 foo
~/tmp $ wget http://slonopotamus.org/git-diff/foo2 -O foo 2> /dev/null 
~/tmp $ time git diff > /dev/null 

real    0m6.513s
user    0m6.490s
sys     0m0.020s
~/tmp $ time git diff --patience > /dev/null 

real    0m0.237s
user    0m0.180s
sys     0m0.050s

Could something be done to `git diff` speed? I would be happy with patience 
diff, but other git commands call standard diff algorithm internally without 
giving an option to choose patience.

gprof output against git master:
http://slonopotamus.org/git-diff/gmon.txt

Re: git diff is slow (--patience is fast)

[Tay Ray Chuan]

On Tue, Aug 9, 2011 at 3:51 PM, Marat Radchenko <marat@slonopotamus.org> wrote:
> Warning, downloaded files are 7.5Mb each.

I'm having some speed issues. Is it possible to make your repo
publicly available (eg github)? Perhaps the compression git does for
its objects could help make downloads zippier.

-- 
Cheers,
Ray Chuan

Re: git diff is slow (--patience is fast)

[Marat Radchenko]

Good idea.

New steps to reproduce:
~ $ git clone git://slonopotamus.org/git-diff
Cloning into git-diff...
remote: Counting objects: 6, done.
remote: Compressing objects: 100% (4/4), done.
remote: Total 6 (delta 1), reused 0 (delta 0)
Receiving objects: 100% (6/6), 478.87 KiB | 722 KiB/s, done.
Resolving deltas: 100% (1/1), done.
~ $ cd git-diff
~/git-diff $ time git diff HEAD^ > /dev/null 

real    0m6.585s
user    0m6.540s
sys     0m0.040s
~/git-diff $ time git diff --patience HEAD^ > /dev/null 

real    0m0.259s
user    0m0.220s
sys     0m0.030s

Re: git diff is slow (--patience is fast)

[Tay Ray Chuan]

On Tue, Aug 9, 2011 at 7:39 PM, Marat Radchenko <marat@slonopotamus.org> wrote:
> Good idea.
>
> New steps to reproduce:
> ~ $ git clone git://slonopotamus.org/git-diff
> Cloning into git-diff...

Thanks.

I traced this to a O(n*m) spot in
xdiff/xprepare.c::xdl_classify_record(). Patch coming up.

-- 
Cheers,
Ray Chuan

[PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Tay Ray Chuan]

In xdl_cleanup_records(), we see O(n*m) performance, where n is the
number of records from xdf->dstart to xdf->dend, and m is the size of a
bucket in xdf->rhash (<= by mlim).

Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
in xdl_classify_record().

Reported-by: Marat Radchenko <marat@slonopotamus.org>
Signed-off-by: Tay Ray Chuan <rctay89@gmail.com>
---

On my msysgit machine:
  
  rctay@TEST-123 /tmp/slono
  $ time git show >/dev/null
  
  real    0m8.538s
  user    0m0.000s
  sys     0m0.031s
  
  rctay@TEST-123 /tmp/slono
  $ time /git/git show >/dev/null
  
  real    0m0.672s
  user    0m0.031s
  sys     0m0.031s


 xdiff/xprepare.c |   87 +++++++++++++++++++++++++++++++-----------------------
 1 files changed, 50 insertions(+), 37 deletions(-)

diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 620fc9a..1043fb7 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -36,6 +36,7 @@ typedef struct s_xdlclass {
 	char const *line;
 	long size;
 	long idx;
+	long len1, len2;
 } xdlclass_t;
 
 typedef struct s_xdlclassifier {
@@ -43,6 +44,8 @@ typedef struct s_xdlclassifier {
 	long hsize;
 	xdlclass_t **rchash;
 	chastore_t ncha;
+	xdlclass_t **rcrecs;
+	long alloc;
 	long count;
 	long flags;
 } xdlclassifier_t;
@@ -52,15 +55,15 @@ typedef struct s_xdlclassifier {
 
 static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
 static void xdl_free_classifier(xdlclassifier_t *cf);
-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
-			       xrecord_t *rec);
-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
+			       unsigned int hbits, xrecord_t *rec);
+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
 			   xdlclassifier_t *cf, xdfile_t *xdf);
 static void xdl_free_ctx(xdfile_t *xdf);
 static int xdl_clean_mmatch(char const *dis, long i, long s, long e);
-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
 static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);
-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
 
 
 
@@ -82,6 +85,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 	}
 	memset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *));
 
+	cf->alloc = size;
+	if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {
+
+		xdl_free(cf->rchash);
+		xdl_cha_free(&cf->ncha);
+		return -1;
+	}
+
 	cf->count = 0;
 
 	return 0;
@@ -95,11 +106,12 @@ static void xdl_free_classifier(xdlclassifier_t *cf) {
 }
 
 
-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
-			       xrecord_t *rec) {
+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
+			       unsigned int hbits, xrecord_t *rec) {
 	long hi;
 	char const *line;
 	xdlclass_t *rcrec;
+	xdlclass_t **rcrecs;
 
 	line = rec->ptr;
 	hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
@@ -115,13 +127,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 			return -1;
 		}
 		rcrec->idx = cf->count++;
+		if (cf->count > cf->alloc) {
+			cf->alloc *= 2;
+			if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {
+
+				return -1;
+			}
+			cf->rcrecs = rcrecs;
+		}
+		cf->rcrecs[rcrec->idx] = rcrec;
 		rcrec->line = line;
 		rcrec->size = rec->size;
 		rcrec->ha = rec->ha;
+		rcrec->len1 = rcrec->len2 = 0;
 		rcrec->next = cf->rchash[hi];
 		cf->rchash[hi] = rcrec;
 	}
 
+	(pass == 1) ? rcrec->len1++ : rcrec->len2++;
+
 	rec->ha = (unsigned long) rcrec->idx;
 
 	hi = (long) XDL_HASHLONG(rec->ha, hbits);
@@ -132,7 +156,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 }
 
 
-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
 			   xdlclassifier_t *cf, xdfile_t *xdf) {
 	unsigned int hbits;
 	long nrec, hsize, bsize;
@@ -185,7 +209,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
 			recs[nrec++] = crec;
 
 			if (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&
-				xdl_classify_record(cf, rhash, hbits, crec) < 0)
+				xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
 				goto abort;
 		}
 	}
@@ -257,30 +281,30 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 		return -1;
 	}
 
-	if (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
+	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
 
 		xdl_free_classifier(&cf);
 		return -1;
 	}
-	if (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
+	if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
 
 		xdl_free_ctx(&xe->xdf1);
 		xdl_free_classifier(&cf);
 		return -1;
 	}
 
-	if (!(xpp->flags & XDF_HISTOGRAM_DIFF))
-		xdl_free_classifier(&cf);
-
 	if (!(xpp->flags & XDF_PATIENCE_DIFF) &&
 			!(xpp->flags & XDF_HISTOGRAM_DIFF) &&
-			xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {
+			xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
 
 		xdl_free_ctx(&xe->xdf2);
 		xdl_free_ctx(&xe->xdf1);
 		return -1;
 	}
 
+	if (!(xpp->flags & XDF_HISTOGRAM_DIFF))
+		xdl_free_classifier(&cf);
+
 	return 0;
 }
 
@@ -355,11 +379,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
  * matches on the other file. Also, lines that have multiple matches
  * might be potentially discarded if they happear in a run of discardable.
  */
-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
-	long i, nm, rhi, nreff, mlim;
-	unsigned long hav;
+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
+	long i, nm, nreff;
 	xrecord_t **recs;
-	xrecord_t *rec;
+	xdlclass_t *rcrec;
 	char *dis, *dis1, *dis2;
 
 	if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
@@ -370,26 +393,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
 	dis1 = dis;
 	dis2 = dis1 + xdf1->nrec + 1;
 
-	if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
-		mlim = XDL_MAX_EQLIMIT;
 	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
-		hav = (*recs)->ha;
-		rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
-		for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++nm == mlim)
-				break;
-		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+		rcrec = cf->rcrecs[(*recs)->ha];
+		nm = rcrec ? rcrec->len2 : 0;
+		dis1[i] = (nm == 0) ? 0: 1;
 	}
 
-	if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
-		mlim = XDL_MAX_EQLIMIT;
 	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
-		hav = (*recs)->ha;
-		rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
-		for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++nm == mlim)
-				break;
-		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+		rcrec = cf->rcrecs[(*recs)->ha];
+		nm = rcrec ? rcrec->len1 : 0;
+		dis2[i] = (nm == 0) ? 0: 1;
 	}
 
 	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
@@ -451,10 +464,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
 }
 
 
-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {
+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
 
 	if (xdl_trim_ends(xdf1, xdf2) < 0 ||
-	    xdl_cleanup_records(xdf1, xdf2) < 0) {
+	    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {
 
 		return -1;
 	}
-- 
1.7.6

Re: [PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Tay Ray Chuan]

>From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001
From: Tay Ray Chuan <rctay89@gmail.com>
Date: Tue, 16 Aug 2011 11:35:28 +0800
Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in
 xdl_cleanup_records()

In xdl_cleanup_records(), we see O(n*m) performance, where n is the
number of records from xdf->dstart to xdf->dend, and m is the size of a
bucket in xdf->rhash (<= by mlim).

Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
in xdl_classify_record().

Reported-by: Marat Radchenko <marat@slonopotamus.org>
Signed-off-by: Tay Ray Chuan <rctay89@gmail.com>
---

Junio, this one is rebased on v1.7.6, instead of rc/histogram-diff.

 xdiff/xprepare.c |   85 +++++++++++++++++++++++++++++++-----------------------
 1 files changed, 49 insertions(+), 36 deletions(-)

diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 1689085..ebbec19 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -34,6 +34,7 @@ typedef struct s_xdlclass {
 	char const *line;
 	long size;
 	long idx;
+	long len1, len2;
 } xdlclass_t;
 
 typedef struct s_xdlclassifier {
@@ -41,6 +42,8 @@ typedef struct s_xdlclassifier {
 	long hsize;
 	xdlclass_t **rchash;
 	chastore_t ncha;
+	xdlclass_t **rcrecs;
+	long alloc;
 	long count;
 	long flags;
 } xdlclassifier_t;
@@ -50,15 +53,15 @@ typedef struct s_xdlclassifier {
 
 static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
 static void xdl_free_classifier(xdlclassifier_t *cf);
-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
-			       xrecord_t *rec);
-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
+			       unsigned int hbits, xrecord_t *rec);
+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
 			   xdlclassifier_t *cf, xdfile_t *xdf);
 static void xdl_free_ctx(xdfile_t *xdf);
 static int xdl_clean_mmatch(char const *dis, long i, long s, long e);
-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
 static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);
-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
 
 
 
@@ -83,6 +86,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 	for (i = 0; i < cf->hsize; i++)
 		cf->rchash[i] = NULL;
 
+	cf->alloc = size;
+	if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {
+
+		xdl_free(cf->rchash);
+		xdl_cha_free(&cf->ncha);
+		return -1;
+	}
+
 	cf->count = 0;
 
 	return 0;
@@ -96,11 +107,12 @@ static void xdl_free_classifier(xdlclassifier_t *cf) {
 }
 
 
-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
-			       xrecord_t *rec) {
+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
+			       unsigned int hbits, xrecord_t *rec) {
 	long hi;
 	char const *line;
 	xdlclass_t *rcrec;
+	xdlclass_t **rcrecs;
 
 	line = rec->ptr;
 	hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
@@ -116,13 +128,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 			return -1;
 		}
 		rcrec->idx = cf->count++;
+		if (cf->count > cf->alloc) {
+			cf->alloc *= 2;
+			if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {
+
+				return -1;
+			}
+			cf->rcrecs = rcrecs;
+		}
+		cf->rcrecs[rcrec->idx] = rcrec;
 		rcrec->line = line;
 		rcrec->size = rec->size;
 		rcrec->ha = rec->ha;
+		rcrec->len1 = rcrec->len2 = 0;
 		rcrec->next = cf->rchash[hi];
 		cf->rchash[hi] = rcrec;
 	}
 
+	(pass == 1) ? rcrec->len1++ : rcrec->len2++;
+
 	rec->ha = (unsigned long) rcrec->idx;
 
 	hi = (long) XDL_HASHLONG(rec->ha, hbits);
@@ -133,7 +157,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 }
 
 
-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
 			   xdlclassifier_t *cf, xdfile_t *xdf) {
 	unsigned int hbits;
 	long i, nrec, hsize, bsize;
@@ -200,7 +224,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
 			crec->ha = hav;
 			recs[nrec++] = crec;
 
-			if (xdl_classify_record(cf, rhash, hbits, crec) < 0) {
+			if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) {
 
 				xdl_free(rhash);
 				xdl_free(recs);
@@ -276,28 +300,28 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 		return -1;
 	}
 
-	if (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
+	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
 
 		xdl_free_classifier(&cf);
 		return -1;
 	}
-	if (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
+	if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
 
 		xdl_free_ctx(&xe->xdf1);
 		xdl_free_classifier(&cf);
 		return -1;
 	}
 
-	xdl_free_classifier(&cf);
-
 	if (!(xpp->flags & XDF_PATIENCE_DIFF) &&
-			xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {
+			xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
 
 		xdl_free_ctx(&xe->xdf2);
 		xdl_free_ctx(&xe->xdf1);
 		return -1;
 	}
 
+	xdl_free_classifier(&cf);
+
 	return 0;
 }
 
@@ -372,11 +396,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
  * matches on the other file. Also, lines that have multiple matches
  * might be potentially discarded if they happear in a run of discardable.
  */
-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
-	long i, nm, rhi, nreff, mlim;
-	unsigned long hav;
+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
+	long i, nm, nreff;
 	xrecord_t **recs;
-	xrecord_t *rec;
+	xdlclass_t *rcrec;
 	char *dis, *dis1, *dis2;
 
 	if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
@@ -387,26 +410,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
 	dis1 = dis;
 	dis2 = dis1 + xdf1->nrec + 1;
 
-	if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
-		mlim = XDL_MAX_EQLIMIT;
 	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
-		hav = (*recs)->ha;
-		rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
-		for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++nm == mlim)
-				break;
-		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+		rcrec = cf->rcrecs[(*recs)->ha];
+		nm = rcrec ? rcrec->len2 : 0;
+		dis1[i] = (nm == 0) ? 0: 1;
 	}
 
-	if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
-		mlim = XDL_MAX_EQLIMIT;
 	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
-		hav = (*recs)->ha;
-		rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
-		for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++nm == mlim)
-				break;
-		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+		rcrec = cf->rcrecs[(*recs)->ha];
+		nm = rcrec ? rcrec->len1 : 0;
+		dis2[i] = (nm == 0) ? 0: 1;
 	}
 
 	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
@@ -468,10 +481,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
 }
 
 
-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {
+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
 
 	if (xdl_trim_ends(xdf1, xdf2) < 0 ||
-	    xdl_cleanup_records(xdf1, xdf2) < 0) {
+	    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {
 
 		return -1;
 	}
-- 
1.7.6

Re: [PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Junio C Hamano]

Tay Ray Chuan <rctay89@gmail.com> writes:

> From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001
> From: Tay Ray Chuan <rctay89@gmail.com>
> Date: Tue, 16 Aug 2011 11:35:28 +0800
> Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in
>  xdl_cleanup_records()

You do not need these four lines. Thanks.

> In xdl_cleanup_records(), we see O(n*m) performance, where n is the
> number of records from xdf->dstart to xdf->dend, and m is the size of a
> bucket in xdf->rhash (<= by mlim).
>
> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
> in xdl_classify_record().

Could we have some benchmarks to let the readers get a feel of how much
improvement this patch brings in?

This tries to trade cycles with memory, right? How much bloat are we
talking about here?

[PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Tay Ray Chuan]

In xdl_cleanup_records(), we see O(n*m) performance, where n is the
number of records from xdf->dstart to xdf->dend, and m is the size of a
bucket in xdf->rhash (<= by mlim).

Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
in xdl_classify_record().

Reported-by: Marat Radchenko <marat@slonopotamus.org>
Signed-off-by: Tay Ray Chuan <rctay89@gmail.com>
---

Changed in v2:
 - free() xdlclassifier_t->rcrecs

On Wed, Aug 17, 2011 at 1:39 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Tay Ray Chuan <rctay89@gmail.com> writes:
>
>> From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001
>> From: Tay Ray Chuan <rctay89@gmail.com>
>> Date: Tue, 16 Aug 2011 11:35:28 +0800
>> Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in
>> ?xdl_cleanup_records()
>
> You do not need these four lines. Thanks.

Oops, I directly pasted git-format-patch output into Claws-mail, sorry
about that.

>> In xdl_cleanup_records(), we see O(n*m) performance, where n is the
>> number of records from xdf->dstart to xdf->dend, and m is the size of a
>> bucket in xdf->rhash (<= by mlim).
>>
>> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
>> in xdl_classify_record().
>
> Could we have some benchmarks to let the readers get a feel of how much
> improvement this patch brings in?

On my msysgit machine with Marat's problematic repo
(git://slonopotamus.org/git-diff):

 rctay@TEST-123 /tmp/slono
 $ time git show >/dev/null

 real    0m8.538s
 user    0m0.000s
 sys     0m0.031s

 rctay@TEST-123 /tmp/slono
 $ time /git/git show >/dev/null

 real    0m0.672s
 user    0m0.031s
 sys     0m0.031s

> This tries to trade cycles with memory, right? How much bloat are we
> talking about here?

The main source of memory bloat would be the xdlclassifier_t->rcrecs
lookup table. This is needed to find the classifier record (xdlclass_t)
associated with a xrecord_t.

In an earlier iteration, I had a pointer on each xrecord_t to the
classifier record, instead of a lookup table, but I casted it to void*,
since I wasn't sure if the xdlclass_t definition should be shifted to
xtypes.h (and thus made public to xdiff and git).

The first is cleaner but the second is lighter. I'd appreciate comments
on this.

 xdiff/xprepare.c |   86 +++++++++++++++++++++++++++++++----------------------
 1 files changed, 50 insertions(+), 36 deletions(-)

diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 1689085..05a8f01 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -34,6 +34,7 @@ typedef struct s_xdlclass {
 	char const *line;
 	long size;
 	long idx;
+	long len1, len2;
 } xdlclass_t;

 typedef struct s_xdlclassifier {
@@ -41,6 +42,8 @@ typedef struct s_xdlclassifier {
 	long hsize;
 	xdlclass_t **rchash;
 	chastore_t ncha;
+	xdlclass_t **rcrecs;
+	long alloc;
 	long count;
 	long flags;
 } xdlclassifier_t;
@@ -50,15 +53,15 @@ typedef struct s_xdlclassifier {

 static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
 static void xdl_free_classifier(xdlclassifier_t *cf);
-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
-			       xrecord_t *rec);
-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
+			       unsigned int hbits, xrecord_t *rec);
+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
 			   xdlclassifier_t *cf, xdfile_t *xdf);
 static void xdl_free_ctx(xdfile_t *xdf);
 static int xdl_clean_mmatch(char const *dis, long i, long s, long e);
-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
 static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);
-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);



@@ -83,6 +86,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 	for (i = 0; i < cf->hsize; i++)
 		cf->rchash[i] = NULL;

+	cf->alloc = size;
+	if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {
+
+		xdl_free(cf->rchash);
+		xdl_cha_free(&cf->ncha);
+		return -1;
+	}
+
 	cf->count = 0;

 	return 0;
@@ -91,16 +102,18 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {

 static void xdl_free_classifier(xdlclassifier_t *cf) {

+	xdl_free(cf->rcrecs);
 	xdl_free(cf->rchash);
 	xdl_cha_free(&cf->ncha);
 }


-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
-			       xrecord_t *rec) {
+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
+			       unsigned int hbits, xrecord_t *rec) {
 	long hi;
 	char const *line;
 	xdlclass_t *rcrec;
+	xdlclass_t **rcrecs;

 	line = rec->ptr;
 	hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
@@ -116,13 +129,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 			return -1;
 		}
 		rcrec->idx = cf->count++;
+		if (cf->count > cf->alloc) {
+			cf->alloc *= 2;
+			if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {
+
+				return -1;
+			}
+			cf->rcrecs = rcrecs;
+		}
+		cf->rcrecs[rcrec->idx] = rcrec;
 		rcrec->line = line;
 		rcrec->size = rec->size;
 		rcrec->ha = rec->ha;
+		rcrec->len1 = rcrec->len2 = 0;
 		rcrec->next = cf->rchash[hi];
 		cf->rchash[hi] = rcrec;
 	}

+	(pass == 1) ? rcrec->len1++ : rcrec->len2++;
+
 	rec->ha = (unsigned long) rcrec->idx;

 	hi = (long) XDL_HASHLONG(rec->ha, hbits);
@@ -133,7 +158,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned
 }


-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
 			   xdlclassifier_t *cf, xdfile_t *xdf) {
 	unsigned int hbits;
 	long i, nrec, hsize, bsize;
@@ -200,7 +225,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
 			crec->ha = hav;
 			recs[nrec++] = crec;

-			if (xdl_classify_record(cf, rhash, hbits, crec) < 0) {
+			if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) {

 				xdl_free(rhash);
 				xdl_free(recs);
@@ -276,28 +301,28 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
 		return -1;
 	}

-	if (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
+	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {

 		xdl_free_classifier(&cf);
 		return -1;
 	}
-	if (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
+	if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {

 		xdl_free_ctx(&xe->xdf1);
 		xdl_free_classifier(&cf);
 		return -1;
 	}

-	xdl_free_classifier(&cf);
-
 	if (!(xpp->flags & XDF_PATIENCE_DIFF) &&
-			xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {
+			xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {

 		xdl_free_ctx(&xe->xdf2);
 		xdl_free_ctx(&xe->xdf1);
 		return -1;
 	}

+	xdl_free_classifier(&cf);
+
 	return 0;
 }

@@ -372,11 +397,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
  * matches on the other file. Also, lines that have multiple matches
  * might be potentially discarded if they happear in a run of discardable.
  */
-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
-	long i, nm, rhi, nreff, mlim;
-	unsigned long hav;
+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
+	long i, nm, nreff;
 	xrecord_t **recs;
-	xrecord_t *rec;
+	xdlclass_t *rcrec;
 	char *dis, *dis1, *dis2;

 	if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
@@ -387,26 +411,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
 	dis1 = dis;
 	dis2 = dis1 + xdf1->nrec + 1;

-	if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
-		mlim = XDL_MAX_EQLIMIT;
 	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
-		hav = (*recs)->ha;
-		rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
-		for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++nm == mlim)
-				break;
-		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+		rcrec = cf->rcrecs[(*recs)->ha];
+		nm = rcrec ? rcrec->len2 : 0;
+		dis1[i] = (nm == 0) ? 0: 1;
 	}

-	if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
-		mlim = XDL_MAX_EQLIMIT;
 	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
-		hav = (*recs)->ha;
-		rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
-		for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
-			if (rec->ha == hav && ++nm == mlim)
-				break;
-		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+		rcrec = cf->rcrecs[(*recs)->ha];
+		nm = rcrec ? rcrec->len1 : 0;
+		dis2[i] = (nm == 0) ? 0: 1;
 	}

 	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
@@ -468,10 +482,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
 }


-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {
+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {

 	if (xdl_trim_ends(xdf1, xdf2) < 0 ||
-	    xdl_cleanup_records(xdf1, xdf2) < 0) {
+	    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {

 		return -1;
 	}
--
1.7.6.12.g6486a.dirty

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Jeff King]

On Wed, Aug 17, 2011 at 09:53:57AM +0800, Tay Ray Chuan wrote:

> > Could we have some benchmarks to let the readers get a feel of how much
> > improvement this patch brings in?
> 
> On my msysgit machine with Marat's problematic repo
> (git://slonopotamus.org/git-diff):
> 
>  rctay@TEST-123 /tmp/slono
>  $ time git show >/dev/null
> 
>  real    0m8.538s
>  user    0m0.000s
>  sys     0m0.031s
> 
>  rctay@TEST-123 /tmp/slono
>  $ time /git/git show >/dev/null
> 
>  real    0m0.672s
>  user    0m0.031s
>  sys     0m0.031s

Wait, what? It was using 0 seconds of user time before, but still taking
8.5 seconds? What was it doing? Did you actually warm up your disk cache
before taking these measurements?

-Peff

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Tay Ray Chuan]

On Wed, Aug 17, 2011 at 1:21 PM, Jeff King <peff@peff.net> wrote:
> Wait, what? It was using 0 seconds of user time before, but still taking
> 8.5 seconds? What was it doing? Did you actually warm up your disk cache
> before taking these measurements?

Three runs on the same machine, after a restart.

  $ time git show >/dev/null

  real    0m6.505s
  user    0m0.031s
  sys     0m0.015s

  rctay@TEST-123 /tmp/slono
  $ time git show >/dev/null

  real    0m5.429s
  user    0m0.000s
  sys     0m0.031s

  rctay@TEST-123 /tmp/slono
  $ time git show >/dev/null

  real    0m5.336s
  user    0m0.000s
  sys     0m0.016s

-- 
Cheers,
Ray Chuan

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Jeff King]

On Wed, Aug 17, 2011 at 11:55:32PM +0800, Tay Ray Chuan wrote:

> On Wed, Aug 17, 2011 at 1:21 PM, Jeff King <peff@peff.net> wrote:
> > Wait, what? It was using 0 seconds of user time before, but still taking
> > 8.5 seconds? What was it doing? Did you actually warm up your disk cache
> > before taking these measurements?
> 
> Three runs on the same machine, after a restart.
> 
>   $ time git show >/dev/null
> 
>   real    0m6.505s
>   user    0m0.031s
>   sys     0m0.015s
> [...]

So it is spending only .046s of CPU time, but is taking 6.5 seconds of
wall clock time. Which implies to me that the dataset doesn't fit in
your disk cache, or it is swapping a lot. Or you are on a really
bogged-down multiuser system. :)

But if I understand correctly, your patch is about increasing runtime
performance of a slow algorithm. So is actually the improvement of an
O(m*n) algorithm to an O(n) one, or does your new algorithm have better
memory access patterns that avoid trashing swap?

Downloading the files from the original problem report, I see much
different timings:

  [before]
  $ time git diff >/dev/null
  real    0m7.690s
  user    0m7.648s
  sys     0m0.024s

  [after (your v2 patch)]
  real    0m0.272s
  user    0m0.236s
  sys     0m0.036s

So I think your patch _is_ an improvement in algorithmic runtime. I just
don't see how your numbers make any sense. Am I missing something? Is
msysgit's bash "time" just broken?

-Peff

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Tay Ray Chuan]

On Fri, Aug 19, 2011 at 6:44 AM, Jeff King <peff@peff.net> wrote:
> On Wed, Aug 17, 2011 at 11:55:32PM +0800, Tay Ray Chuan wrote:
>
>> On Wed, Aug 17, 2011 at 1:21 PM, Jeff King <peff@peff.net> wrote:
>> > Wait, what? It was using 0 seconds of user time before, but still taking
>> > 8.5 seconds? What was it doing? Did you actually warm up your disk cache
>> > before taking these measurements?
>>
>> Three runs on the same machine, after a restart.
>>
>>   $ time git show >/dev/null
>>
>>   real    0m6.505s
>>   user    0m0.031s
>>   sys     0m0.015s
>> [...]
>
> So it is spending only .046s of CPU time, but is taking 6.5 seconds of
> wall clock time. Which implies to me that the dataset doesn't fit in
> your disk cache, or it is swapping a lot. Or you are on a really
> bogged-down multiuser system. :)
>
> But if I understand correctly, your patch is about increasing runtime
> performance of a slow algorithm. So is actually the improvement of an
> O(m*n) algorithm to an O(n) one, or does your new algorithm have better
> memory access patterns that avoid trashing swap?
>
> [snip]
>
> So I think your patch _is_ an improvement in algorithmic runtime. I just
> don't see how your numbers make any sense. Am I missing something? Is
> msysgit's bash "time" just broken?

Nope, available memory is more than enough, so I don't believe
swapping is taking place. I think it's more likely that it's an issue
with time on msysgit.

Johannes, care to shed some light on this?

-- 
Cheers,
Ray Chuan

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Johannes Sixt]

Am 19.08.2011 19:12, schrieb Tay Ray Chuan:
>> Is msysgit's bash "time" just broken?

I think it is broken. The only thing I would use it is to record elapsed 
time (the 'real' part).

-- Hannes

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Marat Radchenko]

Tay Ray Chuan <rctay89 <at> gmail.com> writes:
> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
> in xdl_classify_record().
> 
> Reported-by: Marat Radchenko <marat <at> slonopotamus.org>
> Signed-off-by: Tay Ray Chuan <rctay89 <at> gmail.com>

So, will this be applied to git master? Very impressive speed improvement.

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Marat Radchenko]

Marat Radchenko <marat <at> slonopotamus.org> writes:
> So, will this be applied to git master? Very impressive speed improvement.

Sorry, just discovered it is already in pu.

Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

[Marat Radchenko]

On ср 17 авг 2011 05:53:57 MSD, Tay Ray Chuan <rctay89@gmail.com> wrote:

> In xdl_cleanup_records(), we see O(n*m) performance, where n is the
> number of records from xdf->dstart to xdf->dend, and m is the size of a
> bucket in xdf->rhash (<= by mlim).
> 
> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
> in xdl_classify_record().

Thanks for your patch, btw, now diff is much faster