Re: [PATCH 1/3] diff histogram: intern strings
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Nov 17, 2021, 15:55 UTC
- Message-ID
- <2b2bd380-540f-959b-b950-cfdc95cbff29@gmail.com>
- In-Reply-To
- <38c771a74d2a348e6a752555f95b746de029b1d7.1637148025.git.gitgitgadget@gmail.com>
On 11/17/2021 6:20 AM, Phillip Wood via GitGitGadget wrote:
Show 37 quoted lines
> 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.
Show 14 quoted lines
> - 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