{"thread":{"id":"63351","subject":"[PATCH] xdiff: disable cleanup_records heuristic with --minimal","startedAt":"2025-04-25T16:00:50Z","lastAt":"2025-05-06T22:50:05Z","messageCount":9,"participants":["Niels Glodny","Phillip Wood","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"516813","messageId":"20250425155951.1227700-1-n.glodny@campus.lmu.de","threadId":"63351","inReplyTo":null,"subject":"[PATCH] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Niels Glodny","fromEmail":"n.glodny@campus.lmu.de","sentAt":"2025-04-25T15:59:51Z","receivedAt":"2025-04-25T16:00:50Z","isPatch":true,"sender":{"key":"n.glodny@campus.lmu.de","avatar":"https://avatars.githubusercontent.com/u/33730531?v=4"},"body":"The cleanup_records function marks some lines as changed\nbefore running the actual diff algorithm. For most lines,\nthis is a good performance optimization, but it also marks\nlines that are surrounded by many changed lines as changed\nas well. This can cause redundant changes and longer-than-\nnecessary diffs.\n\nWhether this results in better-looking diffs is subjective.\nHowever, the --minimal flag explicitly requests the shortest\npossible diff.\n\nThe performance impact of this change is negligible, and it\nresults in shorter diffs in about 1.3% of diffs in Git's\nhistory.\n\nSigned-off-by: Niels Glodny <n.glodny@campus.lmu.de>\n---\n t/meson.build           |  1 +\n t/t4071-diff-minimal.sh | 16 ++++++++++++++++\n xdiff/xprepare.c        | 22 +++++++++++++---------\n 3 files changed, 30 insertions(+), 9 deletions(-)\n create mode 100755 t/t4071-diff-minimal.sh\n\ndiff --git a/t/meson.build b/t/meson.build\nindex bfb744e886..8f2e9d2c50 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -501,6 +501,7 @@ integration_tests = [\n   't4068-diff-symmetric-merge-base.sh',\n   't4069-remerge-diff.sh',\n   't4070-diff-pairs.sh',\n+  't4071-diff-minimal.sh',\n   't4100-apply-stat.sh',\n   't4101-apply-nonl.sh',\n   't4102-apply-rename.sh',\ndiff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh\nnew file mode 100755\nindex 0000000000..3ad759dab4\n--- /dev/null\n+++ b/t/t4071-diff-minimal.sh\n@@ -0,0 +1,16 @@\n+#!/bin/sh\n+\n+test_description='minimal diff algorithm'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'minimal diff should not mark changes between changed lines' '\n+\tprintf \"x\\nx\\nx\\nx\\n\" >pre &&\n+\tprintf \"x\\nx\\nx\\nA\\nB\\nC\\nD\\nx\\nE\\nF\\nG\\n\" >post &&\n+\ttest_must_fail git diff --no-index \\\n+\t\t--minimal pre post >diff &&\n+\t! grep \"+x\" diff &&\n+\t! grep \"-x\" diff\n+'\n+\n+test_done\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex c84549f6c5..cb0b6c9fd6 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -61,9 +61,11 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf);\n static void xdl_free_ctx(xdfile_t *xdf);\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e);\n-static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1,\n+\t\t\t       xdfile_t *xdf2, int need_min);\n static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);\n-static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1,\n+\t\t\t     xdfile_t *xdf2, int need_min);\n \n \n \n@@ -279,7 +281,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \n \tif ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&\n \t    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&\n-\t    xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {\n+\t    xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2,\n+\t\t\t      (xpp->flags & XDF_NEED_MINIMAL) != 0) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf2);\n \t\txdl_free_ctx(&xe->xdf1);\n@@ -363,7 +366,8 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n  * matches on the other file. Also, lines that have multiple matches\n  * might be potentially discarded if they happear in a run of discardable.\n  */\n-static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1,\n+\t\t\t       xdfile_t *xdf2, int need_min) {\n \tlong i, nm, nreff, mlim;\n \txrecord_t **recs;\n \txdlclass_t *rcrec;\n@@ -379,7 +383,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n \t\trcrec = cf->rcrecs[(*recs)->ha];\n \t\tnm = rcrec ? rcrec->len2 : 0;\n-\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n \t}\n \n \tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n@@ -387,7 +391,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n \t\trcrec = cf->rcrecs[(*recs)->ha];\n \t\tnm = rcrec ? rcrec->len1 : 0;\n-\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n \t}\n \n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n@@ -449,10 +453,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {\n }\n \n \n-static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n-\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1,\n+\txdfile_t *xdf2, int need_min) {\n \tif (xdl_trim_ends(xdf1, xdf2) < 0 ||\n-\t    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {\n+\t    xdl_cleanup_records(cf, xdf1, xdf2, need_min) < 0) {\n \n \t\treturn -1;\n \t}\n\nbase-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3\n-- \n2.34.1\n\n"},{"id":"516854","messageId":"23078e29-8f1f-4eb3-be71-7ef419252bab@gmail.com","threadId":"63351","inReplyTo":"20250425155951.1227700-1-n.glodny@campus.lmu.de","subject":"Re: [PATCH] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-04-27T15:04:10Z","receivedAt":"2025-04-27T15:04:14Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Niels\n\nOn 25/04/2025 16:59, Niels Glodny wrote:\n> The cleanup_records function marks some lines as changed\n> before running the actual diff algorithm. For most lines,\n> this is a good performance optimization, but it also marks\n> lines that are surrounded by many changed lines as changed\n> as well. This can cause redundant changes and longer-than-\n> necessary diffs.\n\nNicely explained. We normally wrap commit messages at 72 characters\n\n> Whether this results in better-looking diffs is subjective.\n> However, the --minimal flag explicitly requests the shortest\n> possible diff.\n\nLooking at the diff for 2ff58dec493 (refs: introduce function to batch \nrefname availability checks, 2025-03-12) I'd say it is definitely less \nreadable with this change but some of the changes in 320f2061b63 (t0602: \nuse subshell to ensure working directory unchanged, 2025-02-28) are more \nreadable. Anyway as you say if we promise to find the minimal diff then \nthat is what we should do.\n> The performance impact of this change is negligible, and it\n> results in shorter diffs in about 1.3% of diffs in Git's\n> history.\n\nHave you got any numbers for the performance change?\n\nI think the premise of this patch is sound, I've left a couple of \ncomments below as I think we can simplify the code changes.\n\n> diff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh\n> new file mode 100755\n> index 0000000000..3ad759dab4\n> --- /dev/null\n> +++ b/t/t4071-diff-minimal.sh\n> @@ -0,0 +1,16 @@\n> +#!/bin/sh\n> +\n> +test_description='minimal diff algorithm'\n> +\n> +. ./test-lib.sh\n> +\n> +test_expect_success 'minimal diff should not mark changes between changed lines' '\n> +\tprintf \"x\\nx\\nx\\nx\\n\" >pre &&\n> +\tprintf \"x\\nx\\nx\\nA\\nB\\nC\\nD\\nx\\nE\\nF\\nG\\n\" >post &&\n> +\ttest_must_fail git diff --no-index \\\n> +\t\t--minimal pre post >diff &&\n> +\t! grep \"+x\" diff &&\n> +\t! grep \"-x\" diff\n> +'\n\nThanks for taking the trouble to add a new test. We have a few test \nhelper functions which we could use here.\n\n\ttest_write_lines x x x x >pre &&\n\ttest_write_lines x x x A B C D x E F G >post &&\n\ttest_expect_code 1 git diff --no-index --minimal pre post >diff &&\n\ttest_grep ! ^[-+]x diff\n\ntest_expect_code ensures that the non-zero exit code is from the files \nnot matching rather than another error like an invalid option or missing \nfile. test_grep will display the file if there are matches which helps \nwhen debugging test failures.\n\n > [...]> -static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t \n*xdf1, xdfile_t *xdf2) {\n> +static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1,\n> +\t\t\t       xdfile_t *xdf2, int need_min) {\n>   \tlong i, nm, nreff, mlim;\n>   \txrecord_t **recs;\n>   \txdlclass_t *rcrec;\n> @@ -379,7 +383,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\nxdlclassifier_t carries a copy of the flag that were interested in so I \nthink at the start of xdl_cleanup_records we can add\n\n\tint need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n\nand then we don't need to change the signature.\n\n>   \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n>   \t\trcrec = cf->rcrecs[(*recs)->ha];\n>   \t\tnm = rcrec ? rcrec->len2 : 0;\n> -\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n> +\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n\nIf we want a minimal diff then we force dis1[i] to be 1 so that this \nline will never be marked as changed before searching for the longest \ncommon sequence. Well spotted.\n\nBest Wishes\n\nPhillip\n\n>   \t}\n>   \n>   \tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n> @@ -387,7 +391,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n>   \t\trcrec = cf->rcrecs[(*recs)->ha];\n>   \t\tnm = rcrec ? rcrec->len1 : 0;\n> -\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n> +\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n>   \t}\n>   \n>   \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n> @@ -449,10 +453,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {\n>   }\n>   \n>   \n> -static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n> -\n> +static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1,\n> +\txdfile_t *xdf2, int need_min) {\n>   \tif (xdl_trim_ends(xdf1, xdf2) < 0 ||\n> -\t    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {\n> +\t    xdl_cleanup_records(cf, xdf1, xdf2, need_min) < 0) {\n>   \n>   \t\treturn -1;\n>   \t}\n> \n> base-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3\n\n"},{"id":"516868","messageId":"f3140b32-5a25-448b-a99c-1604f6237cb8@campus.lmu.de","threadId":"63351","inReplyTo":"23078e29-8f1f-4eb3-be71-7ef419252bab@gmail.com","subject":"Re: [PATCH] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Niels Glodny","fromEmail":"n.glodny@campus.lmu.de","sentAt":"2025-04-27T21:44:21Z","receivedAt":"2025-04-27T21:44:30Z","isPatch":true,"sender":{"key":"n.glodny@campus.lmu.de","avatar":"https://avatars.githubusercontent.com/u/33730531?v=4"},"body":"Hi Phillip,\n\nthank you for your detailed comments.\n\n> Have you got any numbers for the performance change?\n\nI have been using \"git log -p -3000 --minimal > /dev/null\", as in p4000-diff-algorithms.sh. With this patch, I get\n\n  Time (mean ± σ):      2.363 s ±  0.023 s (25 runs)\n\nWithout this patch, I get\n\n  Time (mean ± σ):      2.362 s ±  0.035 s  (25 runs)\n\nSo the difference is well within the margin of error. It doesn't look like it has any measurable impact on performance.\n\n> 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.\n\nThanks a lot! I'll apply your suggestions and send a revised version shortly.\n\nRegards,\n\nNiels\n\n\n\n"},{"id":"516870","messageId":"20250427220653.2325573-1-n.glodny@campus.lmu.de","threadId":"63351","inReplyTo":"20250425155951.1227700-1-n.glodny@campus.lmu.de","subject":"[PATCH v2] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Niels Glodny","fromEmail":"n.glodny@campus.lmu.de","sentAt":"2025-04-27T22:06:53Z","receivedAt":"2025-04-27T22:08:08Z","isPatch":true,"sender":{"key":"n.glodny@campus.lmu.de","avatar":"https://avatars.githubusercontent.com/u/33730531?v=4"},"body":"The cleanup_records function marks some lines as changed before running\nthe actual diff algorithm. For most lines, this is a good performance\noptimization, but it also marks lines that are surrounded by many\nchanged lines as changed as well. This can cause redundant changes and\nlonger-than-necessary diffs.\n\nWhether this results in better-looking diffs is subjective. However, the\n--minimal flag explicitly requests the shortest possible diff.\n\nA performance impact of this is not measurable, and it results in\nshorter diffs in about 1.3% of diffs in Git's history.\n\nSigned-off-by: Niels Glodny <n.glodny@campus.lmu.de>\n---\n t/meson.build           |  1 +\n t/t4071-diff-minimal.sh | 14 ++++++++++++++\n xdiff/xprepare.c        |  5 +++--\n 3 files changed, 18 insertions(+), 2 deletions(-)\n create mode 100755 t/t4071-diff-minimal.sh\n\ndiff --git a/t/meson.build b/t/meson.build\nindex bfb744e886..8f2e9d2c50 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -501,6 +501,7 @@ integration_tests = [\n   't4068-diff-symmetric-merge-base.sh',\n   't4069-remerge-diff.sh',\n   't4070-diff-pairs.sh',\n+  't4071-diff-minimal.sh',\n   't4100-apply-stat.sh',\n   't4101-apply-nonl.sh',\n   't4102-apply-rename.sh',\ndiff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh\nnew file mode 100755\nindex 0000000000..4c484dadfb\n--- /dev/null\n+++ b/t/t4071-diff-minimal.sh\n@@ -0,0 +1,14 @@\n+#!/bin/sh\n+\n+test_description='minimal diff algorithm'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'minimal diff should not mark changes between changed lines' '\n+\ttest_write_lines x x x x >pre &&\n+\ttest_write_lines x x x A B C D x E F G >post &&\n+\ttest_expect_code 1 git diff --no-index --minimal pre post >diff &&\n+\ttest_grep ! ^[+-]x diff \n+'\n+\n+test_done\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex c84549f6c5..e1d4017b2d 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -368,6 +368,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \txrecord_t **recs;\n \txdlclass_t *rcrec;\n \tchar *dis, *dis1, *dis2;\n+\tint need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n \n \tif (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))\n \t\treturn -1;\n@@ -379,7 +380,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n \t\trcrec = cf->rcrecs[(*recs)->ha];\n \t\tnm = rcrec ? rcrec->len2 : 0;\n-\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n \t}\n \n \tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n@@ -387,7 +388,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n \t\trcrec = cf->rcrecs[(*recs)->ha];\n \t\tnm = rcrec ? rcrec->len1 : 0;\n-\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n \t}\n \n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n\nbase-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3\n-- \n2.34.1\n\n"},{"id":"516900","messageId":"xmqq4iy8dxo2.fsf@gitster.g","threadId":"63351","inReplyTo":"f3140b32-5a25-448b-a99c-1604f6237cb8@campus.lmu.de","subject":"Re: [PATCH] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-04-28T17:05:17Z","receivedAt":"2025-04-28T17:05:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Niels Glodny <n.glodny@campus.lmu.de> writes:\n\n> Hi Phillip,\n>\n> thank you for your detailed comments.\n>\n>> Have you got any numbers for the performance change?\n>\n> I have been using \"git log -p -3000 --minimal > /dev/null\", as in\n> p4000-diff-algorithms.sh. With this patch, I get\n>\n>   Time (mean ± σ):      2.363 s ±  0.023 s (25 runs)\n>\n> Without this patch, I get\n>\n>   Time (mean ± σ):      2.362 s ±  0.035 s  (25 runs)\n>\n> So the difference is well within the margin of error. It doesn't\n> look like it has any measurable impact on performance.\n\nThat is an excellent observation and result.  It should be added to\nthe proposed commit log message, if not already.  The commit log is\nwhere you answer questions, similar to what were raised during\nreview by your reviewers, that future readers of \"git log -p\" would\nhave about your change.  For them you won't be easily available to\nanswer their questions, and that is why we stress on the need for\nwell-written commit log messages.\n\nThanks.\n"},{"id":"516942","messageId":"10aed56b-8036-4458-97ad-7fa319b18f10@gmail.com","threadId":"63351","inReplyTo":"20250427220653.2325573-1-n.glodny@campus.lmu.de","subject":"Re: [PATCH v2] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-04-29T09:00:32Z","receivedAt":"2025-04-29T09:00:41Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Niels\n\nOn 27/04/2025 23:06, Niels Glodny wrote:\n> The cleanup_records function marks some lines as changed before running\n> the actual diff algorithm. For most lines, this is a good performance\n> optimization, but it also marks lines that are surrounded by many\n> changed lines as changed as well. This can cause redundant changes and\n> longer-than-necessary diffs.\n> \n> Whether this results in better-looking diffs is subjective. However, the\n> --minimal flag explicitly requests the shortest possible diff.\n> \n> A performance impact of this is not measurable, and it results in\n> shorter diffs in about 1.3% of diffs in Git's history.\n\nThanks for re-rolling, the changes all look good to me. As Junio said it \nwould be helpful to put the performance numbers in the commit message.\n\nThanks\n\nPhillip\n\n> Signed-off-by: Niels Glodny <n.glodny@campus.lmu.de>\n> ---\n>   t/meson.build           |  1 +\n>   t/t4071-diff-minimal.sh | 14 ++++++++++++++\n>   xdiff/xprepare.c        |  5 +++--\n>   3 files changed, 18 insertions(+), 2 deletions(-)\n>   create mode 100755 t/t4071-diff-minimal.sh\n> \n> diff --git a/t/meson.build b/t/meson.build\n> index bfb744e886..8f2e9d2c50 100644\n> --- a/t/meson.build\n> +++ b/t/meson.build\n> @@ -501,6 +501,7 @@ integration_tests = [\n>     't4068-diff-symmetric-merge-base.sh',\n>     't4069-remerge-diff.sh',\n>     't4070-diff-pairs.sh',\n> +  't4071-diff-minimal.sh',\n>     't4100-apply-stat.sh',\n>     't4101-apply-nonl.sh',\n>     't4102-apply-rename.sh',\n> diff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh\n> new file mode 100755\n> index 0000000000..4c484dadfb\n> --- /dev/null\n> +++ b/t/t4071-diff-minimal.sh\n> @@ -0,0 +1,14 @@\n> +#!/bin/sh\n> +\n> +test_description='minimal diff algorithm'\n> +\n> +. ./test-lib.sh\n> +\n> +test_expect_success 'minimal diff should not mark changes between changed lines' '\n> +\ttest_write_lines x x x x >pre &&\n> +\ttest_write_lines x x x A B C D x E F G >post &&\n> +\ttest_expect_code 1 git diff --no-index --minimal pre post >diff &&\n> +\ttest_grep ! ^[+-]x diff\n> +'\n> +\n> +test_done\n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index c84549f6c5..e1d4017b2d 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -368,6 +368,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \txrecord_t **recs;\n>   \txdlclass_t *rcrec;\n>   \tchar *dis, *dis1, *dis2;\n> +\tint need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n>   \n>   \tif (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))\n>   \t\treturn -1;\n> @@ -379,7 +380,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n>   \t\trcrec = cf->rcrecs[(*recs)->ha];\n>   \t\tnm = rcrec ? rcrec->len2 : 0;\n> -\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n> +\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n>   \t}\n>   \n>   \tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n> @@ -387,7 +388,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n>   \t\trcrec = cf->rcrecs[(*recs)->ha];\n>   \t\tnm = rcrec ? rcrec->len1 : 0;\n> -\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n> +\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n>   \t}\n>   \n>   \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n> \n> base-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3\n\n"},{"id":"516950","messageId":"20250429140949.2634935-1-n.glodny@campus.lmu.de","threadId":"63351","inReplyTo":"20250425155951.1227700-1-n.glodny@campus.lmu.de","subject":"[PATCH v3] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Niels Glodny","fromEmail":"n.glodny@campus.lmu.de","sentAt":"2025-04-29T14:09:49Z","receivedAt":"2025-04-29T14:11:09Z","isPatch":true,"sender":{"key":"n.glodny@campus.lmu.de","avatar":"https://avatars.githubusercontent.com/u/33730531?v=4"},"body":"The cleanup_records function marks some lines as changed before running\nthe actual diff algorithm. For most lines, this is a good performance\noptimization, but it also marks lines that are surrounded by many\nchanged lines as changed as well. This can cause redundant changes and\nlonger-than-necessary diffs.\n\nWhether this results in better-looking diffs is subjective. However, the\n--minimal flag explicitly requests the shortest possible diff.\n\nThe change results in shorter diffs in about 1.3% of all diffs in Git's\nhistory. Performance wise, I have measured the impact on\n\"git log -p -3000 --minimal > /dev/null\". With this change, I get\n  Time (mean ± σ): 2.363 s ±  0.023 s (25 runs)\nand without this patch I measured\n  Time (mean ± σ): 2.362 s ±  0.035 s (25 runs).\nAs the difference is well within the margin of error, this does not seem\nto have an impact on performance.\n\nSigned-off-by: Niels Glodny <n.glodny@campus.lmu.de>\n---\n t/meson.build           |  1 +\n t/t4071-diff-minimal.sh | 14 ++++++++++++++\n xdiff/xprepare.c        |  5 +++--\n 3 files changed, 18 insertions(+), 2 deletions(-)\n create mode 100755 t/t4071-diff-minimal.sh\n\ndiff --git a/t/meson.build b/t/meson.build\nindex bfb744e886..8f2e9d2c50 100644\n--- a/t/meson.build\n+++ b/t/meson.build\n@@ -501,6 +501,7 @@ integration_tests = [\n   't4068-diff-symmetric-merge-base.sh',\n   't4069-remerge-diff.sh',\n   't4070-diff-pairs.sh',\n+  't4071-diff-minimal.sh',\n   't4100-apply-stat.sh',\n   't4101-apply-nonl.sh',\n   't4102-apply-rename.sh',\ndiff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh\nnew file mode 100755\nindex 0000000000..4c484dadfb\n--- /dev/null\n+++ b/t/t4071-diff-minimal.sh\n@@ -0,0 +1,14 @@\n+#!/bin/sh\n+\n+test_description='minimal diff algorithm'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'minimal diff should not mark changes between changed lines' '\n+\ttest_write_lines x x x x >pre &&\n+\ttest_write_lines x x x A B C D x E F G >post &&\n+\ttest_expect_code 1 git diff --no-index --minimal pre post >diff &&\n+\ttest_grep ! ^[+-]x diff \n+'\n+\n+test_done\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex c84549f6c5..e1d4017b2d 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -368,6 +368,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \txrecord_t **recs;\n \txdlclass_t *rcrec;\n \tchar *dis, *dis1, *dis2;\n+\tint need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n \n \tif (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))\n \t\treturn -1;\n@@ -379,7 +380,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n \t\trcrec = cf->rcrecs[(*recs)->ha];\n \t\tnm = rcrec ? rcrec->len2 : 0;\n-\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n \t}\n \n \tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n@@ -387,7 +388,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n \t\trcrec = cf->rcrecs[(*recs)->ha];\n \t\tnm = rcrec ? rcrec->len1 : 0;\n-\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n \t}\n \n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n\nbase-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3\n-- \n2.34.1\n\n"},{"id":"517340","messageId":"f2b34e81-fb86-4a30-9aa7-67e6f5758168@gmail.com","threadId":"63351","inReplyTo":"20250429140949.2634935-1-n.glodny@campus.lmu.de","subject":"Re: [PATCH v3] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2025-05-06T13:21:01Z","receivedAt":"2025-05-06T13:21:00Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Niels\n\nOn 29/04/2025 15:09, Niels Glodny wrote:\n> The cleanup_records function marks some lines as changed before running\n> the actual diff algorithm. For most lines, this is a good performance\n> optimization, but it also marks lines that are surrounded by many\n> changed lines as changed as well. This can cause redundant changes and\n> longer-than-necessary diffs.\n> \n> Whether this results in better-looking diffs is subjective. However, the\n> --minimal flag explicitly requests the shortest possible diff.\n> \n> The change results in shorter diffs in about 1.3% of all diffs in Git's\n> history. Performance wise, I have measured the impact on\n> \"git log -p -3000 --minimal > /dev/null\". With this change, I get\n>    Time (mean ± σ): 2.363 s ±  0.023 s (25 runs)\n> and without this patch I measured\n>    Time (mean ± σ): 2.362 s ±  0.035 s (25 runs).\n> As the difference is well within the margin of error, this does not seem\n> to have an impact on performance.\n\nThanks for adding the performance information, this version looks good \nto me.\n\nBest Wishes\n\nPhillip\n\n> Signed-off-by: Niels Glodny <n.glodny@campus.lmu.de>\n> ---\n>   t/meson.build           |  1 +\n>   t/t4071-diff-minimal.sh | 14 ++++++++++++++\n>   xdiff/xprepare.c        |  5 +++--\n>   3 files changed, 18 insertions(+), 2 deletions(-)\n>   create mode 100755 t/t4071-diff-minimal.sh\n> \n> diff --git a/t/meson.build b/t/meson.build\n> index bfb744e886..8f2e9d2c50 100644\n> --- a/t/meson.build\n> +++ b/t/meson.build\n> @@ -501,6 +501,7 @@ integration_tests = [\n>     't4068-diff-symmetric-merge-base.sh',\n>     't4069-remerge-diff.sh',\n>     't4070-diff-pairs.sh',\n> +  't4071-diff-minimal.sh',\n>     't4100-apply-stat.sh',\n>     't4101-apply-nonl.sh',\n>     't4102-apply-rename.sh',\n> diff --git a/t/t4071-diff-minimal.sh b/t/t4071-diff-minimal.sh\n> new file mode 100755\n> index 0000000000..4c484dadfb\n> --- /dev/null\n> +++ b/t/t4071-diff-minimal.sh\n> @@ -0,0 +1,14 @@\n> +#!/bin/sh\n> +\n> +test_description='minimal diff algorithm'\n> +\n> +. ./test-lib.sh\n> +\n> +test_expect_success 'minimal diff should not mark changes between changed lines' '\n> +\ttest_write_lines x x x x >pre &&\n> +\ttest_write_lines x x x A B C D x E F G >post &&\n> +\ttest_expect_code 1 git diff --no-index --minimal pre post >diff &&\n> +\ttest_grep ! ^[+-]x diff\n> +'\n> +\n> +test_done\n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index c84549f6c5..e1d4017b2d 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -368,6 +368,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \txrecord_t **recs;\n>   \txdlclass_t *rcrec;\n>   \tchar *dis, *dis1, *dis2;\n> +\tint need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n>   \n>   \tif (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))\n>   \t\treturn -1;\n> @@ -379,7 +380,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n>   \t\trcrec = cf->rcrecs[(*recs)->ha];\n>   \t\tnm = rcrec ? rcrec->len2 : 0;\n> -\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n> +\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n>   \t}\n>   \n>   \tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n> @@ -387,7 +388,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>   \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n>   \t\trcrec = cf->rcrecs[(*recs)->ha];\n>   \t\tnm = rcrec ? rcrec->len1 : 0;\n> -\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n> +\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;\n>   \t}\n>   \n>   \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n> \n> base-commit: f65182a99e545d2f2bc22e6c1c2da192133b16a3\n\n"},{"id":"517401","messageId":"xmqq4ixxfj6t.fsf@gitster.g","threadId":"63351","inReplyTo":"f2b34e81-fb86-4a30-9aa7-67e6f5758168@gmail.com","subject":"Re: [PATCH v3] xdiff: disable cleanup_records heuristic with --minimal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-05-06T22:50:02Z","receivedAt":"2025-05-06T22:50:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Phillip Wood <phillip.wood123@gmail.com> writes:\n\n> Hi Niels\n>\n> On 29/04/2025 15:09, Niels Glodny wrote:\n>> The cleanup_records function marks some lines as changed before running\n>> the actual diff algorithm. For most lines, this is a good performance\n>> optimization, but it also marks lines that are surrounded by many\n>> changed lines as changed as well. This can cause redundant changes and\n>> longer-than-necessary diffs.\n>> Whether this results in better-looking diffs is subjective. However,\n>> the\n>> --minimal flag explicitly requests the shortest possible diff.\n>> The change results in shorter diffs in about 1.3% of all diffs in\n>> Git's\n>> history. Performance wise, I have measured the impact on\n>> \"git log -p -3000 --minimal > /dev/null\". With this change, I get\n>>    Time (mean ± σ): 2.363 s ±  0.023 s (25 runs)\n>> and without this patch I measured\n>>    Time (mean ± σ): 2.362 s ±  0.035 s (25 runs).\n>> As the difference is well within the margin of error, this does not seem\n>> to have an impact on performance.\n>\n> Thanks for adding the performance information, this version looks good\n> to me.\n>\n> Best Wishes\n>\n> Phillip\n\nYup, thanks, both of you.\n"}]}