Re: Bug: git log --numstat counts wrong

Alexander Pepper [off-list ref] writes:

Am 21.09.2011 um 14:24 schrieb Junio C Hamano:

quoted

quoted

$ git log --numstat 48a07e7e533f507228e8d1c99d4d48e175e14260
[...]
11      10      src/java/voldemort/server/storage/StorageService.java

Didn't we update it this already? I seem to get 10/9 here not 11/10.

Current 'maint' (cd2b8ae9), 'master' (4b5eac7f)...

That's a tad old master you seem to have.

Strangely, bisection points at 27af01d5523, which was supposed to be only
about performance and never about correctness. There is something fishy
going on....

Am 21.09.2011 um 22:35 schrieb Junio C Hamano:

That's a tad old master you seem to have.

Up until now I only followed the github clone, but that seems to be dated. Since kernel.org is still down, I'll now follow the google code clone.


Am 21.09.2011 um 22:35 schrieb Junio C Hamano:

quoted

Am 21.09.2011 um 14:24 schrieb Junio C Hamano:

quoted

quoted

$ git log --numstat 48a07e7e533f507228e8d1c99d4d48e175e14260
[...]
11      10      src/java/voldemort/server/storage/StorageService.java

Didn't we update it this already? I seem to get 10/9 here not 11/10.

Current 'maint' (cd2b8ae9), 'master' (4b5eac7f)...

Strangely, bisection points at 27af01d5523, which was supposed to be only
about performance and never about correctness. There is something fishy
going on....

I also did some tests, and besides --numstat also git show sometimes show different patches in comparison to older git versions. The last version with the "old" git show output is 1.7.7.rc0 and the first version with the "new" git show output is 1.7.7.rc1.

with git version 1.7.7.rc0:
$ git show 679e1d5cd007a0a9cb2813bd155622d7a1e904bd :
[...]

diff --git a/src/java/voldemort/store/stats/RequestCounter.java b/src/java/voldemort/store/stats/RequestCounter.java
index b012e98..c6be603 100644
--- a/src/java/voldemort/store/stats/RequestCounter.java
+++ b/src/java/voldemort/store/stats/RequestCounter.java

@@ -64,16 +64,21 @@ public class RequestCounter {
         Accumulator accum = values.get();
         long now = System.currentTimeMillis();
 
-        if(now - accum.startTimeMS > durationMS) {
-            Accumulator newWithTotal = accum.newWithTotal();
-            values.set(newWithTotal);
-
-            /*
-             * try to set.  if we fail, then someone else set it, so just keep going
-             */
-            if(values.compareAndSet(accum, newWithTotal)) {
-                return newWithTotal;
-            }
+        /*
+         *  if still in the window, just return it
+         */
+        if(now - accum.startTimeMS <= durationMS) {
+            return accum;
+        }
+
+        /*
+         * try to set.  if we fail, then someone else set it, so just return that new one
+         */
+
+        Accumulator newWithTotal = accum.newWithTotal();
+
+        if(values.compareAndSet(accum, newWithTotal)) {
+            return newWithTotal;
         }
 
         return values.get();

with git version 1.7.7.rc1:
$ git show 679e1d5cd007a0a9cb2813bd155622d7a1e904bd
[...]

diff --git a/src/java/voldemort/store/stats/RequestCounter.java b/src/java/voldemort/store/stats/RequestCounter.java
index b012e98..c6be603 100644
--- a/src/java/voldemort/store/stats/RequestCounter.java
+++ b/src/java/voldemort/store/stats/RequestCounter.java

@@ -64,16 +64,21 @@ public class RequestCounter {
         Accumulator accum = values.get();
         long now = System.currentTimeMillis();
 
-        if(now - accum.startTimeMS > durationMS) {
-            Accumulator newWithTotal = accum.newWithTotal();
-            values.set(newWithTotal);
+        /*
+         *  if still in the window, just return it
+         */
+        if(now - accum.startTimeMS <= durationMS) {
+            return accum;
+        }
 
-            /*
-             * try to set.  if we fail, then someone else set it, so just keep going
-             */
-            if(values.compareAndSet(accum, newWithTotal)) {
-                return newWithTotal;
-            }
+        /*
+         * try to set.  if we fail, then someone else set it, so just return that new one
+         */
+
+        Accumulator newWithTotal = accum.newWithTotal();
+
+        if(values.compareAndSet(accum, newWithTotal)) {
+            return newWithTotal;
         }
 
         return values.get();

The difference is, that now it's shown as two delete and two added hunks instead of one bigger delete and one bigger added hunk.

with git version 1.7.7.rc1:
$ git show 679e1d5cd007a0a9cb2813bd155622d7a1e904bd | diffstat
 RequestCounter.java |   23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

with git version 1.7.7.rc0:
$ git show 679e1d5cd007a0a9cb2813bd155622d7a1e904bd | diffstat
 RequestCounter.java |   25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

When used git version 1.7.7.rc1 I didn't observed any case where git show and git log --numstat mismatch. I'm only a little confused, that 'git show' yields different results, depending on the git version.

Greetings from Berlin
Alex

Am 21.09.2011 22:35, schrieb Junio C Hamano:

Alexander Pepper [off-list ref] writes:

quoted

Am 21.09.2011 um 14:24 schrieb Junio C Hamano:

quoted

quoted

$ git log --numstat 48a07e7e533f507228e8d1c99d4d48e175e14260
[...]
11      10      src/java/voldemort/server/storage/StorageService.java

Didn't we update it this already? I seem to get 10/9 here not 11/10.

Current 'maint' (cd2b8ae9), 'master' (4b5eac7f)...

That's a tad old master you seem to have.

Strangely, bisection points at 27af01d5523, which was supposed to be only
about performance and never about correctness. There is something fishy
going on....

The patch below reverts a part of 27af01d5523 that's not explained in its
commit message and doesn't seem to contribute to the intended speedup.  It
seems to restore the original diff output.  I don't know how it's actually
doing that, though, as I haven't dug into the code at all.

Alexander, can you confirm that this patch restores the old behaviour of
git diff and git show for your test cases?

Ray, are you able to write a commit message for this patch if it turns out
to be useful?

René

diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 5a33d1a..e419f4f 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c

@@ -383,7 +383,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
  * might be potentially discarded if they happear in a run of discardable.
  */
 static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
-	long i, nm, nreff;
+	long i, nm, nreff, mlim;
 	xrecord_t **recs;
 	xdlclass_t *rcrec;
 	char *dis, *dis1, *dis2;

@@ -396,16 +396,20 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
 	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++) {
 		rcrec = cf->rcrecs[(*recs)->ha];
 		nm = rcrec ? rcrec->len2 : 0;
-		dis1[i] = (nm == 0) ? 0: 1;
+		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 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++) {
 		rcrec = cf->rcrecs[(*recs)->ha];
 		nm = rcrec ? rcrec->len1 : 0;
-		dis2[i] = (nm == 0) ? 0: 1;
+		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
 	}
 
 	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];

On Fri, Sep 23, 2011 at 12:15 AM, René Scharfe
[off-list ref] wrote:

Thanks for the patch, René.

Sorry for not explaining that part of the change.

My understanding of mlim is that it "caps" how deep the for loop at
around line 387 goes through a hash bucket/record chaing to find a
matching record from side A in side B (and vice-versa in a later
loop), probably to prevent running time from becoming too long.

But with 27af01d, this is no longer a concern. We can get an *exact*,
pre-computed count of matching records in the other side, so we don't
have go through the hash bucket. Thus mlim is no longer needed.

So re-introducing mlim doesn't seem right, even though it may fix this
"bug" (ie restore the old behaviour).

-- 
Cheers,
Ray Chuan

From: René Scharfe <redacted>

27af01d (xdiff/xprepare: improve O(n*m) performance in
xdl_cleanup_records(), 2011-08-17) was supposed to be a performance
boost only. However, it unexpectedly changed the behaviour of diff.

Revert a part of 27af01d that removes logic that mark lines as
"multi-match" (ie. dis[i] == 2). This was preventing the multi-match
discard heuristic (performed in xdl_cleanup_records() and
xdl_clean_mmatch()) from executing.

Reported-by: Alexander Pepper <redacted>
Signed-off-by: Tay Ray Chuan <redacted>

---

Junio, this replaces the patch the one in the
'rs/diff-cleanup-records-fix' topic in 'pu'. The only difference is in
the patch message.

René, will need your SOB on this. Thanks for working to produce the
patch. Please disregard my earlier message [1], further reading has
shown my previous understanding to be wrong.

[1] [off-list ref]
---
 xdiff/xprepare.c |   10 +++++++---
 1 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 05a8f01..4c447ca 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c

@@ -398,7 +398,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
  * might be potentially discarded if they happear in a run of discardable.
  */
 static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
-	long i, nm, nreff;
+	long i, nm, nreff, mlim;
 	xrecord_t **recs;
 	xdlclass_t *rcrec;
 	char *dis, *dis1, *dis2;

@@ -411,16 +411,20 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
 	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++) {
 		rcrec = cf->rcrecs[(*recs)->ha];
 		nm = rcrec ? rcrec->len2 : 0;
-		dis1[i] = (nm == 0) ? 0: 1;
+		dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 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++) {
 		rcrec = cf->rcrecs[(*recs)->ha];
 		nm = rcrec ? rcrec->len1 : 0;
-		dis2[i] = (nm == 0) ? 0: 1;
+		dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
 	}
 
 	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];

-- 
1.7.7.rc3.432.g6bcf0

Am 25.09.2011 15:39, schrieb Tay Ray Chuan:

From: René Scharfe <redacted>

27af01d (xdiff/xprepare: improve O(n*m) performance in
xdl_cleanup_records(), 2011-08-17) was supposed to be a performance
boost only. However, it unexpectedly changed the behaviour of diff.

Revert a part of 27af01d that removes logic that mark lines as
"multi-match" (ie. dis[i] == 2). This was preventing the multi-match
discard heuristic (performed in xdl_cleanup_records() and
xdl_clean_mmatch()) from executing.

Reported-by: Alexander Pepper <redacted>
Signed-off-by: Tay Ray Chuan <redacted>

---

Junio, this replaces the patch the one in the
'rs/diff-cleanup-records-fix' topic in 'pu'. The only difference is in
the patch message.

René, will need your SOB on this. Thanks for working to produce the
patch. Please disregard my earlier message [1], further reading has
shown my previous understanding to be wrong.

Signed-off-by: Rene Scharfe <redacted>