Hi Stolee
On 17/11/2021 15:55, Derrick Stolee wrote:
On 11/17/2021 6:20 AM, Phillip Wood via GitGitGadget wrote:
From: Phillip Wood <phillip.wood@xxxxxxxxxxxxx>
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@xxxxxxxxxxxxx>
---
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?
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)
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.
I think that code in xdiffi.c is only used by the diff slider code that
implements diff.indentHeuristic, the Myers diff implementation just
compares the hash values. Before this change the diff slider code needed
to do the full check to be correct when processing the output of the
histogram algorithm.
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 for looking at this
Best Wishes
Phillip
Thanks,
-Stolee
