xdiff: speedup histogram diff

From: Phillip Wood <[email protected]>

Histogram is the only diff algorithm not to call xdl_classify_record(). xdl_classify_record() ensures that the hash values of two strings that are not equal differ which means that it is not necessary to use xdl_recmatch() when comparing lines, all that is necessary is to compare the hash values. This gives a 7% reduction in the runtime of "git log --patch" when using the histogram diff algorithm.

Test HEAD^ HEAD
-----------------------------------------------------------------------------

4000.1: log -3000 (baseline)          0.18(0.14+0.04)   0.19(0.17+0.02) +5.6%
4000.2: log --raw -3000 (tree-only)   0.99(0.77+0.21)   0.98(0.78+0.20) -1.0%
4000.3: log -p -3000 (Myers)          4.84(4.31+0.51)   4.81(4.15+0.64) -0.6%
4000.4: log -p -3000 --histogram      6.34(5.86+0.46)   5.87(5.19+0.66) -7.4%
4000.5: log -p -3000 --patience       5.39(4.60+0.76)   5.35(4.60+0.73) -0.7%

Signed-off-by Phillip Wood <[email protected]>

---
 xdiff/xhistogram.c |  5 ++---
 xdiff/xprepare.c   | 24 ++++++++----------------
 2 files changed, 10 insertions(+), 19 deletions(-)

xdiff/xhistogram.c +0 -0

index e694bfd9e31..6c1c88a69a1 100644

xdiff/xhistogram.c +5 -10

-	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
-		hbits = hsize = 0;
-	else {
-		hbits = xdl_hashbits((unsigned int) narec);
-		hsize = 1 << hbits;
-		if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
-			goto abort;
-		memset(rhash, 0, hsize * sizeof(xrecord_t *));
-	}
+	hbits = xdl_hashbits((unsigned int) narec);
+	hsize = 1 << hbits;
+	if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
+		goto abort;
+	memset(rhash, 0, hsize * sizeof(xrecord_t *));
 
-			if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&

xdiff/xhistogram.c struct region { · line 95

Quoted 13 lines

xdiff/xhistogram.c +2 -3

index e694bfd9e31..6c1c88a69a1 100644
@@ -91,9 +91,8 @@ struct region {
 static int cmp_recs(xpparam_t const *xpp,
 	xrecord_t *r1, xrecord_t *r2)
 {
-	return r1->ha == r2->ha &&
-		xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
-			    xpp->flags);
+	return r1->ha == r2->ha;
+

nit: stray newline.

The only meaningful change here is that you are relying entirely on the hash and not checking the content again. This means that hash collisions on this 32-bit hash could start introducing different results. Are we worried about that?

The existence of these conditions gave me pause, so I went to look for where they were inserted. They were made in 9f37c27 (xdiff/xprepare: skip classification, 2011-07-12) with the justification that

We don't need any of that in histogram diff, so we omit calls to these functions. We also skip allocating memory to the hash table, rhash, as it is no longer used.

This gives us a small boost in performance.

But you are actually _using_ these preparation steps, which means you are re-adding the cost of hashing but overall improving because you use the data correctly. Excellent.

Quoted 29 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Histogram is the only diff algorithm not to call xdl_classify_record(). xdl_classify_record() ensures that the hash values of two strings that are not equal differ which means that it is not necessary to use xdl_recmatch() when comparing lines, all that is necessary is to compare the hash values. This gives a 7% reduction in the runtime of "git log --patch" when using the histogram diff algorithm.

Test HEAD^ HEAD
-----------------------------------------------------------------------------

4000.1: log -3000 (baseline)          0.18(0.14+0.04)   0.19(0.17+0.02) +5.6%
4000.2: log --raw -3000 (tree-only)   0.99(0.77+0.21)   0.98(0.78+0.20) -1.0%
4000.3: log -p -3000 (Myers)          4.84(4.31+0.51)   4.81(4.15+0.64) -0.6%
4000.4: log -p -3000 --histogram      6.34(5.86+0.46)   5.87(5.19+0.66) -7.4%
4000.5: log -p -3000 --patience       5.39(4.60+0.76)   5.35(4.60+0.73) -0.7%

Signed-off-by Phillip Wood <[email protected]>

---
  xdiff/xhistogram.c |  5 ++---
  xdiff/xprepare.c   | 24 ++++++++----------------
  2 files changed, 10 insertions(+), 19 deletions(-)

xdiff/xhistogram.c +0 -0

index e694bfd9e31..6c1c88a69a1 100644

xdiff/xhistogram.c struct region { · line 95

Quoted 8 lines

xdiff/xhistogram.c +2 -3

@@ -91,9 +91,8 @@ struct region {
  static int cmp_recs(xpparam_t const *xpp,
  	xrecord_t *r1, xrecord_t *r2)
  {
-	return r1->ha == r2->ha &&
-		xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
-			    xpp->flags);
+	return r1->ha == r2->ha;
+

nit: stray newline.

The only meaningful change here is that you are relying entirely on the hash and not checking the content again. This means that hash collisions on this 32-bit hash could start introducing different results. Are we worried about that?

I see that a similar hash-comparison is done in xpatience.c without further checking the contents, but xdiffi.c compares the hashes and then checks with xdl_recmatch(). So, we are still not reaching full consistency across all diff algorithms with how we handle these comparisons. I think it is good to have at least one that can be used if/when we hit these hash collisions within a diff, but it can be hard to communicate to a user why they need to change a diff algorithm for such an internal reason.

The following bits looked scary at first, but you are just removing the special-casing of XDF_HISTOGRAM_DIFF from the preparation stage.

Quoted 16 lines

xdiff/xhistogram.c +5 -10

-	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
-		hbits = hsize = 0;
-	else {
-		hbits = xdl_hashbits((unsigned int) narec);
-		hsize = 1 << hbits;
-		if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
-			goto abort;
-		memset(rhash, 0, hsize * sizeof(xrecord_t *));
-	}
+	hbits = xdl_hashbits((unsigned int) narec);
+	hsize = 1 << hbits;
+	if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
+		goto abort;
+	memset(rhash, 0, hsize * sizeof(xrecord_t *));
 
-			if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&

xdiff/xhistogram.c struct region {

Quoted 10 lines

xdiff/xhistogram.c +3 -5

-			    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
+			if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
 
-	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&
-	    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
+	if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
 
-	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)
-		xdl_free_classifier(&cf);
+	xdl_free_classifier(&cf);

The existence of these conditions gave me pause, so I went to look for where they were inserted. They were made in 9f37c27 (xdiff/xprepare: skip classification, 2011-07-12) with the justification that

We don't need any of that in histogram diff, so we omit calls to these functions. We also skip allocating memory to the hash table, rhash, as it is no longer used.

This gives us a small boost in performance.

But you are actually _using_ these preparation steps, which means you are re-adding the cost of hashing but overall improving because you use the data correctly. Excellent.

Thanks,
-Stolee

Quoted 47 lines · Derrick Stolee

Quoted 34 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Histogram is the only diff algorithm not to call xdl_classify_record(). xdl_classify_record() ensures that the hash values of two strings that are not equal differ which means that it is not necessary to use xdl_recmatch() when comparing lines, all that is necessary is to compare the hash values. This gives a 7% reduction in the runtime of "git log --patch" when using the histogram diff algorithm.

Test HEAD^ HEAD
-----------------------------------------------------------------------------
4000.1: log -3000 (baseline) 0.18(0.14+0.04) 0.19(0.17+0.02)
+5.6%
4000.2: log --raw -3000 (tree-only) 0.99(0.77+0.21) 0.98(0.78+0.20)
-1.0%
4000.3: log -p -3000 (Myers) 4.84(4.31+0.51) 4.81(4.15+0.64)
-0.6%
4000.4: log -p -3000 --histogram 6.34(5.86+0.46) 5.87(5.19+0.66)
-7.4%
4000.5: log -p -3000 --patience 5.39(4.60+0.76) 5.35(4.60+0.73)
-0.7%

Signed-off-by Phillip Wood <[email protected]>

---
  xdiff/xhistogram.c |  5 ++---
  xdiff/xprepare.c   | 24 ++++++++----------------
  2 files changed, 10 insertions(+), 19 deletions(-)

xdiff/xhistogram.c +0 -0

index e694bfd9e31..6c1c88a69a1 100644

xdiff/xhistogram.c struct region { · line 95

Quoted 8 lines

xdiff/xhistogram.c +2 -3

@@ -91,9 +91,8 @@ struct region {
  static int cmp_recs(xpparam_t const *xpp,
  	xrecord_t *r1, xrecord_t *r2)
  {
-	return r1->ha == r2->ha &&
-		xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
-			    xpp->flags);
+	return r1->ha == r2->ha;
+

nit: stray newline.

Quoted 4 lines

The only meaningful change here is that you are relying entirely on the hash and not checking the content again. This means that hash collisions on this 32-bit hash could start introducing different results. Are we worried about that?

xdiff-interface.c limits the size of the file that can be passed to just below 1GB so we are safe. The other diff algorithms are already using this optimization. (the hash is 64 bits on most platforms, the xdiff code could really benefit from a unsigned long -> size_t cleanup)

Histogram is the only diff algorithm not to call xdl_classify_record(). Calling xdl_classify_record() means that it is not necessary to use xdl_recmatch() when comparing lines, all that is necessary is to compare the hash values. This gives a 7% reduction in the runtime of "git log --patch" when using the histogram diff algorithm.

I think the really important thing to point out is that xdl_classify_record() ensures that the ha attribute is different for different text. AFAIR it even "linearizes" the ha values, i.e. they won't be all over the place but start at 0 (or 1).

So no, I'm not worried about collisions. That would be a bug in xdl_classify_record() and I think we would have caught this bug by now.

Quoted 5 lines · Johannes Schindelin

I think the really important thing to point out is that xdl_classify_record() ensures that the ha attribute is different for different text. AFAIR it even "linearizes" the ha values, i.e. they won't be all over the place but start at 0 (or 1).

Quoted 2 lines

So no, I'm not worried about collisions. That would be a bug in xdl_classify_record() and I think we would have caught this bug by now.

Ah, thanks for that explanation. That addresses my collision concern from earlier in the thread completely.

Quoted 10 lines · Jeff King

Quoted 7 lines · Johannes Schindelin

I think the really important thing to point out is that xdl_classify_record() ensures that the ha attribute is different for different text. AFAIR it even "linearizes" the ha values, i.e. they won't be all over the place but start at 0 (or 1).

So no, I'm not worried about collisions. That would be a bug in xdl_classify_record() and I think we would have caught this bug by now.

Quoted 2 lines

Ah, thanks for that explanation. That addresses my collision concern from earlier in the thread completely.

Yes, thanks for clarifying I should have been clearer in my reply to Stolee. The reason I was waffling on about file sizes is that there can only be a collision if there are more than 2^32 unique lines. I think the minimum file size where that happens is just below 10GB when one side of the diff has 2^31 lines and the other has 2^31 + 1 lines and all the lines are unique.

Quoted 7 lines · Jeff King

Quoted 5 lines · Johannes Schindelin

I think the really important thing to point out is that xdl_classify_record() ensures that the ha attribute is different for different text. AFAIR it even "linearizes" the ha values, i.e. they won't be all over the place but start at 0 (or 1).

Quoted 6 lines

Quoted 3 lines

So no, I'm not worried about collisions. That would be a bug in xdl_classify_record() and I think we would have caught this bug by now.

Ah, thanks for that explanation. That addresses my collision concern from earlier in the thread completely.

Yes, thanks for clarifying I should have been clearer in my reply to Stolee. The reason I was waffling on about file sizes is that there can only be a collision if there are more than 2^32 unique lines. I think the minimum file size where that happens is just below 10GB when one side of the diff has 2^31 lines and the other has 2^31 + 1 lines and all the lines are unique.

Quoted 11 lines · Phillip Wood

Quoted 10 lines · Jeff King

Quoted 7 lines · Johannes Schindelin

I think the really important thing to point out is that xdl_classify_record() ensures that the ha attribute is different for different text. AFAIR it even "linearizes" the ha values, i.e. they won't be all over the place but start at 0 (or 1).

So no, I'm not worried about collisions. That would be a bug in xdl_classify_record() and I think we would have caught this bug by now.

Quoted 8 lines

Quoted 2 lines

Ah, thanks for that explanation. That addresses my collision concern from earlier in the thread completely.

Yes, thanks for clarifying I should have been clearer in my reply to Stolee. The reason I was waffling on about file sizes is that there can only be a collision if there are more than 2^32 unique lines. I think the minimum file size where that happens is just below 10GB when one side of the diff has 2^31 lines and the other has 2^31 + 1 lines and all the lines are unique.

Right, that makes more sense (and we are not likely to lift the 1GB limit anytime soon; there are tons of 32-bit variables and potential integer overflows all through the xdiff code).

Quoted 3 lines

Right, that makes more sense (and we are not likely to lift the 1GB limit anytime soon; there are tons of 32-bit variables and potential integer overflows all through the xdiff code).

Interestingly:

    $ du -sh 8gb*
    8.1G    8gb
    8.1G    8gb.cp
    $ ~/g/git/git -P -c core.bigFileThreshold=10g diff -U0 --no-index --no-color-moved 2gb 2gb.cp
    diff --git a/8gb b/8gb.cp
    index a886cdfe5ce..4965a132d44 100644
    --- a/8gb
    +++ b/8gb.cp
    @@ -17,0 +18 @@ more
    +blah

And the only change I made was:

    diff --git a/xdiff-interface.c b/xdiff-interface.c
    index 75b32aef51d..cb8ca5f5d0a 100644
    --- a/xdiff-interface.c
    +++ b/xdiff-interface.c
    @@ -117,9 +117,6 @@ int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t co
            mmfile_t a = *mf1;
            mmfile_t b = *mf2;
     
    -       if (mf1->size > MAX_XDIFF_SIZE || mf2->size > MAX_XDIFF_SIZE)
    -               return -1;
    -
            if (!xecfg->ctxlen && !(xecfg->flags & XDL_EMIT_FUNCCONTEXT))
                    trim_common_tail(&a, &b);

Perhaps we're being overly concervative with these hardcoded limits, at least on some platforms? This is Linux x86_64.

I understand from skimming the above that it's about the pathological case, these two files are the same except for a trailer at the end.