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

[Derrick Stolee <stolee@gmail.com>]

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.

Thanks,
-Stolee