Re: [PATCH 1/3] diff histogram: intern strings

> 
> 
> On 11/17/2021 6:20 AM, Phillip Wood via GitGitGadget wrote:
>> From: Phillip Wood <phillip.wood@dunelm.org.uk>
>>
>> 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 <phillip.wood@dunelm.org.uk>
>> ---
>>   xdiff/xhistogram.c |  5 ++---
>>   xdiff/xprepare.c   | 24 ++++++++----------------
>>   2 files changed, 10 insertions(+), 19 deletions(-)
>>
>> diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c
>> index e694bfd9e31..6c1c88a69a1 100644
>> --- a/xdiff/xhistogram.c
>> +++ b/xdiff/xhistogram.c
>> @@ -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.
> 
>> -	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) &&
>> -			    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.