Re: [PATCH] xdiff: disable cleanup_records heuristic with --minimal
- From
- Phillip Wood <phillip.wood123@gmail.com>
- Date
- Apr 27, 2025, 15:04 UTC
- Message-ID
- <23078e29-8f1f-4eb3-be71-7ef419252bab@gmail.com>
- In-Reply-To
- <20250425155951.1227700-1-n.glodny@campus.lmu.de>
Hi Niels
On 25/04/2025 16:59, Niels Glodny wrote:
Show 6 quoted lines
> The cleanup_records function marks some lines as changed > before running the actual diff algorithm. For most lines, > this is a good performance optimization, but it also marks > lines that are surrounded by many changed lines as changed > as well. This can cause redundant changes and longer-than- > necessary diffs.
Nicely explained. We normally wrap commit messages at 72 characters
> Whether this results in better-looking diffs is subjective. > However, the --minimal flag explicitly requests the shortest > possible diff.
Looking at the diff for 2ff58dec493 (refs: introduce function to batch refname availability checks, 2025-03-12) I'd say it is definitely less readable with this change but some of the changes in 320f2061b63 (t0602: use subshell to ensure working directory unchanged, 2025-02-28) are more readable. Anyway as you say if we promise to find the minimal diff then that is what we should do.
> The performance impact of this change is negligible, and it > results in shorter diffs in about 1.3% of diffs in Git's > history.
Have you got any numbers for the performance change?
I think the premise of this patch is sound, I've left a couple of comments below as I think we can simplify the code changes.
Show 20 quoted lines
> diff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh > new file mode 100755 > index 0000000000..3ad759dab4 > --- /dev/null > +++ b/t/t4071-diff-minimal.sh > @@ -0,0 +1,16 @@ > +#!/bin/sh > + > +test_description='minimal diff algorithm' > + > +. ./test-lib.sh > + > +test_expect_success 'minimal diff should not mark changes between changed lines' ' > + printf "x\nx\nx\nx\n" >pre && > + printf "x\nx\nx\nA\nB\nC\nD\nx\nE\nF\nG\n" >post && > + test_must_fail git diff --no-index \ > + --minimal pre post >diff && > + ! grep "+x" diff && > + ! grep "-x" diff > +'
Thanks for taking the trouble to add a new test. We have a few test helper functions which we could use here.
test_write_lines x x x x >pre && test_write_lines x x x A B C D x E F G >post && test_expect_code 1 git diff --no-index --minimal pre post >diff && test_grep ! ^[-+]x diff
test_expect_code ensures that the non-zero exit code is from the files not matching rather than another error like an invalid option or missing file. test_grep will display the file if there are matches which helps when debugging test failures.
> [...]> -static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t
*xdf1, xdfile_t *xdf2) {Show 6 quoted lines
> +static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1,
> + xdfile_t *xdf2, int need_min) {
> long i, nm, nreff, mlim;
> xrecord_t **recs;
> xdlclass_t *rcrec;
> @@ -379,7 +383,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdxdlclassifier_t carries a copy of the flag that were interested in so I think at the start of xdl_cleanup_records we can add
int need_min = !!(cf->flags & XDF_NEED_MINIMAL);
and then we don't need to change the signature.
Show 5 quoted lines
> for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
> rcrec = cf->rcrecs[(*recs)->ha];
> nm = rcrec ? rcrec->len2 : 0;
> - dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
> + dis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;If we want a minimal diff then we force dis1[i] to be 1 so that this line will never be marked as changed before searching for the longest common sequence. Well spotted.
Best Wishes
Phillip
Show 28 quoted lines
> }
>
> if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
> @@ -387,7 +391,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
> for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
> rcrec = cf->rcrecs[(*recs)->ha];
> nm = rcrec ? rcrec->len1 : 0;
> - dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
> + dis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;
> }
>
> for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
> @@ -449,10 +453,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
> }
>
>
> -static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
> -
> +static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1,
> + xdfile_t *xdf2, int need_min) {
> if (xdl_trim_ends(xdf1, xdf2) < 0 ||
> - xdl_cleanup_records(cf, xdf1, xdf2) < 0) {
> + xdl_cleanup_records(cf, xdf1, xdf2, need_min) < 0) {
>
> return -1;
> }
>
> base-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3