{"thread":{"id":"65415","subject":"[PATCH 0/4] xdiff: reduce the size of a couple of arrays","startedAt":"2026-04-02T14:58:01Z","lastAt":"2026-05-04T14:06:41Z","messageCount":14,"participants":["Phillip Wood","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"540762","messageId":"cover.1775141855.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":null,"subject":"[PATCH 0/4] xdiff: reduce the size of a couple of arrays","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-04-02T14:57:40Z","receivedAt":"2026-04-02T14:58:01Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nWhen the myers algorithm is selected the input files are pre-processed\nto remove any common prefix and suffix. There are a couple of places\nwhere we allocate arrays large enough to hold the whole file when\nthey only need to be big enough to hold the remaining lines after the\ncommon prefix and suffix have been removed. This series adjusts those\nallocations to avoid allocating space for the common lines.\n\nThese patches are based on 'en/xdiff-cleanup-3'\n\nBase-Commit: 7ff1460b62ffc8f18a5478be5aba9d4599afb635\nPublished-As: https://github.com/phillipwood/git/releases/tag/pw%2Fxdiff-reduce-array-sizes%2Fv1\nView-Changes-At: https://github.com/phillipwood/git/compare/7ff1460b6...a3438dc09\nFetch-It-Via: git fetch https://github.com/phillipwood/git pw/xdiff-reduce-array-sizes/v1\n\n\nPhillip Wood (4):\n  xdiff: reduce size of action arrays\n  xdiff: cleanup xdl_clean_mmatch()\n  xprepare: simplify error handling\n  xdiff: reduce the size of array\n\n xdiff/xprepare.c | 46 ++++++++++++++++++++++------------------------\n 1 file changed, 22 insertions(+), 24 deletions(-)\n\n-- \n2.52.0.362.g884e03848a9.dirty\n\n"},{"id":"540763","messageId":"447b8c0af1746d61bfa26e7908a784583ab5dc2e.1775141855.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1775141855.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 1/4] xdiff: reduce size of action arrays","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-04-02T14:57:41Z","receivedAt":"2026-04-02T14:58:02Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nWhen the myers algorithm is selected the input files are pre-processed\nto remove any common prefix and suffix. Then any lines that appear\nonly in one side of the diff are marked as changed and frequently\noccurring lines are marked as changed if they are adjacent to a\nchanged line. This step requires a couple of temporary arrays. As as\nthe common prefix and suffix have already been removed, the arrays\nonly need to be big enough to hold the lines between them, not the\nwhole file. Reduce the size of the arrays and adjust the loops that\nuse them accordingly while taking care to keep indexing the arrays\nin xdfile_t with absolute line numbers.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 31 +++++++++++++++++--------------\n 1 file changed, 17 insertions(+), 14 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 1f2e8c6b4b9..4bb3a8ef41c 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -273,16 +273,19 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tuint8_t *action1 = NULL, *action2 = NULL;\n \tbool need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n \tint ret = 0;\n+\tptrdiff_t off = xdf1->dstart;\n+\tptrdiff_t len1 = xdf1->dend - off + 1;\n+\tptrdiff_t len2 = xdf2->dend - off + 1;\n \n \t/*\n \t * Create temporary arrays that will help us decide if\n \t * changed[i] should remain false, or become true.\n \t */\n-\tif (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {\n+\tif (!XDL_CALLOC_ARRAY(action1, len1)) {\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n-\tif (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {\n+\tif (!XDL_CALLOC_ARRAY(action2, len2)) {\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n@@ -299,8 +302,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t/*\n \t * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.\n \t */\n-\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n-\t\tsize_t mph1 = xdf1->recs[i].minimal_perfect_hash;\n+\tfor (i = 0; i < len1; i++) {\n+\t\tsize_t mph1 = xdf1->recs[i + off].minimal_perfect_hash;\n \t\trcrec = cf->rcrecs[mph1];\n \t\tnm = rcrec ? rcrec->len2 : 0;\n \t\tif (nm == 0)\n@@ -311,8 +314,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t\t\taction1[i] = INVESTIGATE;\n \t}\n \n-\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n-\t\tsize_t mph2 = xdf2->recs[i].minimal_perfect_hash;\n+\tfor (i = 0; i < len2; i++) {\n+\t\tsize_t mph2 = xdf2->recs[i + off].minimal_perfect_hash;\n \t\trcrec = cf->rcrecs[mph2];\n \t\tnm = rcrec ? rcrec->len1 : 0;\n \t\tif (nm == 0)\n@@ -328,37 +331,37 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t * false, or become true.\n \t */\n \txdf1->nreff = 0;\n-\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n+\tfor (i = 0; i < len1; i++) {\n \t\tif (action1[i] == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))\n+\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n \t\t\t\taction1[i] = KEEP;\n \t\t\telse\n \t\t\t\taction1[i] = DISCARD;\n \t\t}\n \n \t\tif (action1[i] == KEEP) {\n-\t\t\txdf1->reference_index[xdf1->nreff++] = i;\n+\t\t\txdf1->reference_index[xdf1->nreff++] = i + off;\n \t\t\t/* changed[i] remains false */\n \t\t} else if (action1[i] == DISCARD)\n-\t\t\txdf1->changed[i] = true;\n+\t\t\txdf1->changed[i + off] = true;\n \t\telse\n \t\t\tBUG(\"Illegal state for action1[i]\");\n \t}\n \n \txdf2->nreff = 0;\n-\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n+\tfor (i = 0; i < len2; i++) {\n \t\tif (action2[i] == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))\n+\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n \t\t\t\taction2[i] = KEEP;\n \t\t\telse\n \t\t\t\taction2[i] = DISCARD;\n \t\t}\n \n \t\tif (action2[i] == KEEP) {\n-\t\t\txdf2->reference_index[xdf2->nreff++] = i;\n+\t\t\txdf2->reference_index[xdf2->nreff++] = i + off;\n \t\t\t/* changed[i] remains false */\n \t\t} else if (action2[i] == DISCARD)\n-\t\t\txdf2->changed[i] = true;\n+\t\t\txdf2->changed[i + off] = true;\n \t\telse\n \t\t\tBUG(\"Illegal state for action2[i]\");\n \t}\n-- \n2.52.0.362.g884e03848a9.dirty\n\n"},{"id":"540764","messageId":"78e9313fd44c7cd9f820109edb103a680aa73ad3.1775141855.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1775141855.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 2/4] xdiff: cleanup xdl_clean_mmatch()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-04-02T14:57:42Z","receivedAt":"2026-04-02T14:58:03Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nRemove the \"s\" parameter as, since the last commit, this function\nis always called with s == 0. Also change parameter \"e\" to expect a\nlength, rather than the index of the last line to simplify the caller.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 7 ++++---\n 1 file changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 4bb3a8ef41c..f8e6a6d74d5 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -197,8 +197,9 @@ void xdl_free_env(xdfenv_t *xe) {\n }\n \n \n-static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t s, ptrdiff_t e) {\n+static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t len) {\n \tptrdiff_t r, rdis0, rpdis0, rdis1, rpdis1;\n+\tptrdiff_t s = 0, e = len - 1;\n \n \t/*\n \t * Limits the window that is examined during the similar-lines\n@@ -333,7 +334,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \txdf1->nreff = 0;\n \tfor (i = 0; i < len1; i++) {\n \t\tif (action1[i] == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n+\t\t\tif (!xdl_clean_mmatch(action1, i, len1))\n \t\t\t\taction1[i] = KEEP;\n \t\t\telse\n \t\t\t\taction1[i] = DISCARD;\n@@ -351,7 +352,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \txdf2->nreff = 0;\n \tfor (i = 0; i < len2; i++) {\n \t\tif (action2[i] == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n+\t\t\tif (!xdl_clean_mmatch(action2, i, len2))\n \t\t\t\taction2[i] = KEEP;\n \t\t\telse\n \t\t\t\taction2[i] = DISCARD;\n-- \n2.52.0.362.g884e03848a9.dirty\n\n"},{"id":"540765","messageId":"cdcad99edc403a9e0d1d21592fa295477282421c.1775141855.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1775141855.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 3/4] xprepare: simplify error handling","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-04-02T14:57:43Z","receivedAt":"2026-04-02T14:58:03Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nIf either of the two allocations fail we want to take the same action\nso use a single if statement. This saves a few lines and makes it\neasier for the next commit to add a couple more allocations.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 7 ++-----\n 1 file changed, 2 insertions(+), 5 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex f8e6a6d74d5..cf4ac34f047 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -282,11 +282,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t * Create temporary arrays that will help us decide if\n \t * changed[i] should remain false, or become true.\n \t */\n-\tif (!XDL_CALLOC_ARRAY(action1, len1)) {\n-\t\tret = -1;\n-\t\tgoto cleanup;\n-\t}\n-\tif (!XDL_CALLOC_ARRAY(action2, len2)) {\n+\tif (!XDL_CALLOC_ARRAY(action1, len1) ||\n+\t    !XDL_CALLOC_ARRAY(action2, len2)) {\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n-- \n2.52.0.362.g884e03848a9.dirty\n\n"},{"id":"540766","messageId":"a3438dc09335ce46c0141c80d18d71cefcb96a4f.1775141855.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1775141855.git.phillip.wood@dunelm.org.uk","subject":"[PATCH 4/4] xdiff: reduce the size of array","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-04-02T14:57:44Z","receivedAt":"2026-04-02T14:58:04Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nWhen the myers algorithm is selected the input files are pre-processed\nto remove any common prefix and suffix and any lines that appear\nin only one file. This requires a map to be created between the\nlines that are processed by the myers algorithm and the lines in\nthe original file. That map does not include the common lines at the\nbeginning and end of the files but the array is allocated to be the\nsize of the whole file. Move the allocation into xdl_cleanup_records()\nwhere the map is populated and we know how big it needs to be.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 11 ++++-------\n 1 file changed, 4 insertions(+), 7 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex cf4ac34f047..c5a3c9cde76 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -171,12 +171,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n \tif (!XDL_CALLOC_ARRAY(xdf->changed, xdf->nrec + 2))\n \t\tgoto abort;\n \n-\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&\n-\t    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {\n-\t\tif (!XDL_ALLOC_ARRAY(xdf->reference_index, xdf->nrec + 1))\n-\t\t\tgoto abort;\n-\t}\n-\n \txdf->changed += 1;\n \txdf->nreff = 0;\n \txdf->dstart = 0;\n@@ -283,7 +277,10 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t * changed[i] should remain false, or become true.\n \t */\n \tif (!XDL_CALLOC_ARRAY(action1, len1) ||\n-\t    !XDL_CALLOC_ARRAY(action2, len2)) {\n+\t    !XDL_CALLOC_ARRAY(action2, len2) ||\n+\t    !XDL_ALLOC_ARRAY(xdf1->reference_index, len1) ||\n+\t    !XDL_ALLOC_ARRAY(xdf2->reference_index, len2))\n+\t{\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n-- \n2.52.0.362.g884e03848a9.dirty\n\n"},{"id":"540787","messageId":"xmqqy0j5p3ur.fsf@gitster.g","threadId":"65415","inReplyTo":"447b8c0af1746d61bfa26e7908a784583ab5dc2e.1775141855.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 1/4] xdiff: reduce size of action arrays","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-04-02T19:19:24Z","receivedAt":"2026-04-02T19:19:26Z","isPatch":true,"body":"Phillip Wood <phillip.wood123@gmail.com> writes:\n\n> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>\n> When the myers algorithm is selected the input files are pre-processed\n> to remove any common prefix and suffix. Then any lines that appear\n> only in one side of the diff are marked as changed and frequently\n> occurring lines are marked as changed if they are adjacent to a\n> changed line. This step requires a couple of temporary arrays. As as\n> the common prefix and suffix have already been removed, the arrays\n> only need to be big enough to hold the lines between them, not the\n> whole file. Reduce the size of the arrays and adjust the loops that\n> use them accordingly while taking care to keep indexing the arrays\n> in xdfile_t with absolute line numbers.\n\n\"As as\"???\n\n> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n> ---\n>  xdiff/xprepare.c | 31 +++++++++++++++++--------------\n>  1 file changed, 17 insertions(+), 14 deletions(-)\n>\n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index 1f2e8c6b4b9..4bb3a8ef41c 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -273,16 +273,19 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \tuint8_t *action1 = NULL, *action2 = NULL;\n>  \tbool need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n>  \tint ret = 0;\n> +\tptrdiff_t off = xdf1->dstart;\n> +\tptrdiff_t len1 = xdf1->dend - off + 1;\n> +\tptrdiff_t len2 = xdf2->dend - off + 1;\n>  \n>  \t/*\n>  \t * Create temporary arrays that will help us decide if\n>  \t * changed[i] should remain false, or become true.\n>  \t */\n> -\tif (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {\n> +\tif (!XDL_CALLOC_ARRAY(action1, len1)) {\n>  \t\tret = -1;\n>  \t\tgoto cleanup;\n>  \t}\n> -\tif (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {\n> +\tif (!XDL_CALLOC_ARRAY(action2, len2)) {\n>  \t\tret = -1;\n>  \t\tgoto cleanup;\n>  \t}\n\nOK, so we used to allocate for the whole thing, but now we only\nallocate for lines starting at dstart.  \"off\" is the difference\nbetween [i], the index into these action arrays, and the true line\nnumbers.\n\n> @@ -299,8 +302,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \t/*\n>  \t * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.\n>  \t */\n> -\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n> -\t\tsize_t mph1 = xdf1->recs[i].minimal_perfect_hash;\n> +\tfor (i = 0; i < len1; i++) {\n> +\t\tsize_t mph1 = xdf1->recs[i + off].minimal_perfect_hash;\n\nAnd we iterate as many times as we have entries in the action array,\nbut we need to offset the [i] with off when looking at the record.\n\n>  \t\trcrec = cf->rcrecs[mph1];\n>  \t\tnm = rcrec ? rcrec->len2 : 0;\n>  \t\tif (nm == 0)\n> @@ -311,8 +314,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \t\t\taction1[i] = INVESTIGATE;\n>  \t}\n>  \n> -\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n> -\t\tsize_t mph2 = xdf2->recs[i].minimal_perfect_hash;\n> +\tfor (i = 0; i < len2; i++) {\n> +\t\tsize_t mph2 = xdf2->recs[i + off].minimal_perfect_hash;\n\nLikewise.\n\n> @@ -328,37 +331,37 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \t * false, or become true.\n>  \t */\n>  \txdf1->nreff = 0;\n> -\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n> +\tfor (i = 0; i < len1; i++) {\n>  \t\tif (action1[i] == INVESTIGATE) {\n> -\t\t\tif (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))\n> +\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n\nLet me think aloud to see if I can follow the logic here.  Looking\nat the implementation of the xdl_clean_mmatch() function, it takes\nan action array, an offset 'i' into it (starting from dstart), the\nbeginning 'dstart' and the end 'dend' offsets.  The idea is that an\nindex derived from 'i' is used to index the action array and the\nbeginning and the end offsets are used to limit how much far the\naccess can deviate from 'i'.\n\nNow we stripped the first xdf1->dstart elements from action1[]\narray, 'i' in this loop runs from 0 (i.e. one beyond the initial\ncommon section) and len1 (i.e. one before the tail end of the common\nsection), i.e., everything is consistently shifted down by xdf1->dstart\nin this call.  So xdl_clean_mmatch() does not even need to know that\nit is fed a shortened action[] array.\n\n\n>  \t\t\t\taction1[i] = KEEP;\n>  \t\t\telse\n>  \t\t\t\taction1[i] = DISCARD;\n>  \t\t}\n>  \n>  \t\tif (action1[i] == KEEP) {\n> -\t\t\txdf1->reference_index[xdf1->nreff++] = i;\n> +\t\t\txdf1->reference_index[xdf1->nreff++] = i + off;\n>  \t\t\t/* changed[i] remains false */\n>  \t\t} else if (action1[i] == DISCARD)\n> -\t\t\txdf1->changed[i] = true;\n> +\t\t\txdf1->changed[i + off] = true;\n\nBut these two arrays are not shrunk, so we need to compensate by the 'off'\noffset.\n\nAnd the remainder is similar but for xdf2 instead of xdf1 above.\n\n>  \t\telse\n>  \t\t\tBUG(\"Illegal state for action1[i]\");\n>  \t}\n>  \n>  \txdf2->nreff = 0;\n> -\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n> +\tfor (i = 0; i < len2; i++) {\n>  \t\tif (action2[i] == INVESTIGATE) {\n> -\t\t\tif (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))\n> +\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n>  \t\t\t\taction2[i] = KEEP;\n>  \t\t\telse\n>  \t\t\t\taction2[i] = DISCARD;\n>  \t\t}\n>  \n>  \t\tif (action2[i] == KEEP) {\n> -\t\t\txdf2->reference_index[xdf2->nreff++] = i;\n> +\t\t\txdf2->reference_index[xdf2->nreff++] = i + off;\n>  \t\t\t/* changed[i] remains false */\n>  \t\t} else if (action2[i] == DISCARD)\n> -\t\t\txdf2->changed[i] = true;\n> +\t\t\txdf2->changed[i + off] = true;\n>  \t\telse\n>  \t\t\tBUG(\"Illegal state for action2[i]\");\n>  \t}\n"},{"id":"540788","messageId":"xmqqtsttp3tl.fsf@gitster.g","threadId":"65415","inReplyTo":"78e9313fd44c7cd9f820109edb103a680aa73ad3.1775141855.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 2/4] xdiff: cleanup xdl_clean_mmatch()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-04-02T19:20:06Z","receivedAt":"2026-04-02T19:20:08Z","isPatch":true,"body":"Phillip Wood <phillip.wood123@gmail.com> writes:\n\n> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>\n> Remove the \"s\" parameter as, since the last commit, this function\n> is always called with s == 0. Also change parameter \"e\" to expect a\n> length, rather than the index of the last line to simplify the caller.\n>\n> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n> ---\n>  xdiff/xprepare.c | 7 ++++---\n>  1 file changed, 4 insertions(+), 3 deletions(-)\n\nVery logical consequence, given what the previous step did.  Makes sense.\n\n>\n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index 4bb3a8ef41c..f8e6a6d74d5 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -197,8 +197,9 @@ void xdl_free_env(xdfenv_t *xe) {\n>  }\n>  \n>  \n> -static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t s, ptrdiff_t e) {\n> +static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t len) {\n>  \tptrdiff_t r, rdis0, rpdis0, rdis1, rpdis1;\n> +\tptrdiff_t s = 0, e = len - 1;\n>  \n>  \t/*\n>  \t * Limits the window that is examined during the similar-lines\n> @@ -333,7 +334,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \txdf1->nreff = 0;\n>  \tfor (i = 0; i < len1; i++) {\n>  \t\tif (action1[i] == INVESTIGATE) {\n> -\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n> +\t\t\tif (!xdl_clean_mmatch(action1, i, len1))\n>  \t\t\t\taction1[i] = KEEP;\n>  \t\t\telse\n>  \t\t\t\taction1[i] = DISCARD;\n> @@ -351,7 +352,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \txdf2->nreff = 0;\n>  \tfor (i = 0; i < len2; i++) {\n>  \t\tif (action2[i] == INVESTIGATE) {\n> -\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n> +\t\t\tif (!xdl_clean_mmatch(action2, i, len2))\n>  \t\t\t\taction2[i] = KEEP;\n>  \t\t\telse\n>  \t\t\t\taction2[i] = DISCARD;\n"},{"id":"540789","messageId":"xmqqpl4hp3m6.fsf@gitster.g","threadId":"65415","inReplyTo":"cdcad99edc403a9e0d1d21592fa295477282421c.1775141855.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 3/4] xprepare: simplify error handling","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-04-02T19:24:33Z","receivedAt":"2026-04-02T19:24:35Z","isPatch":true,"body":"Phillip Wood <phillip.wood123@gmail.com> writes:\n\n> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>\n> If either of the two allocations fail we want to take the same action\n> so use a single if statement. This saves a few lines and makes it\n> easier for the next commit to add a couple more allocations.\n>\n> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n> ---\n>  xdiff/xprepare.c | 7 ++-----\n>  1 file changed, 2 insertions(+), 5 deletions(-)\n>\n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index f8e6a6d74d5..cf4ac34f047 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -282,11 +282,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \t * Create temporary arrays that will help us decide if\n>  \t * changed[i] should remain false, or become true.\n>  \t */\n> -\tif (!XDL_CALLOC_ARRAY(action1, len1)) {\n> -\t\tret = -1;\n> -\t\tgoto cleanup;\n> -\t}\n> -\tif (!XDL_CALLOC_ARRAY(action2, len2)) {\n> +\tif (!XDL_CALLOC_ARRAY(action1, len1) ||\n> +\t    !XDL_CALLOC_ARRAY(action2, len2)) {\n>  \t\tret = -1;\n>  \t\tgoto cleanup;\n>  \t}\n\nIf the original were \"after successfully allocating action1[], if\nallocation of action2[] fails, then release action1[] before\nreturning -1\", written in place, it would have been a different\nstory, but the \"cleanup:\" label is left to free each and every\nresources the code obtains in this function, so this consolidation\ndoes make sense.\n\n"},{"id":"540790","messageId":"xmqqldf5p2on.fsf@gitster.g","threadId":"65415","inReplyTo":"a3438dc09335ce46c0141c80d18d71cefcb96a4f.1775141855.git.phillip.wood@dunelm.org.uk","subject":"Re: [PATCH 4/4] xdiff: reduce the size of array","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-04-02T19:44:40Z","receivedAt":"2026-04-02T19:44:43Z","isPatch":true,"body":"Phillip Wood <phillip.wood123@gmail.com> writes:\n\n> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>\n> When the myers algorithm is selected the input files are pre-processed\n> to remove any common prefix and suffix and any lines that appear\n> in only one file. This requires a map to be created between the\n> lines that are processed by the myers algorithm and the lines in\n> the original file. That map does not include the common lines at the\n> beginning and end of the files but the array is allocated to be the\n> size of the whole file. Move the allocation into xdl_cleanup_records()\n> where the map is populated and we know how big it needs to be.\n>\n> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n> ---\n>  xdiff/xprepare.c | 11 ++++-------\n>  1 file changed, 4 insertions(+), 7 deletions(-)\n>\n> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\n> index cf4ac34f047..c5a3c9cde76 100644\n> --- a/xdiff/xprepare.c\n> +++ b/xdiff/xprepare.c\n> @@ -171,12 +171,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n>  \tif (!XDL_CALLOC_ARRAY(xdf->changed, xdf->nrec + 2))\n>  \t\tgoto abort;\n>  \n> -\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&\n> -\t    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {\n> -\t\tif (!XDL_ALLOC_ARRAY(xdf->reference_index, xdf->nrec + 1))\n> -\t\t\tgoto abort;\n> -\t}\n> -\n>  \txdf->changed += 1;\n>  \txdf->nreff = 0;\n>  \txdf->dstart = 0;\n> @@ -283,7 +277,10 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n>  \t * changed[i] should remain false, or become true.\n>  \t */\n>  \tif (!XDL_CALLOC_ARRAY(action1, len1) ||\n> -\t    !XDL_CALLOC_ARRAY(action2, len2)) {\n> +\t    !XDL_CALLOC_ARRAY(action2, len2) ||\n> +\t    !XDL_ALLOC_ARRAY(xdf1->reference_index, len1) ||\n> +\t    !XDL_ALLOC_ARRAY(xdf2->reference_index, len2))\n> +\t{\n>  \t\tret = -1;\n>  \t\tgoto cleanup;\n>  \t}\n\nOK.  In xdl_cleanup_records(), accesses toxdf{1,2}->reference_index[] \nalready runs from index 0 (i.e., array element at [0] corresponds to\nthe xdf1->dstart) even without the previous three patches.  So we\nwere only wasting the elements near the end in these two arrays.\nAnd the loop that uses the array runs only for len1 times, and the\narray may acquire at most one new element per iteration, so len1 is\nthe reasonable allocation size for xdf1->reference_index[].\n\nLooking good.\n"},{"id":"542670","messageId":"cover.1777903579.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1775141855.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 0/4] xdiff: reduce the size of a couple of arrays","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-05-04T14:06:17Z","receivedAt":"2026-05-04T14:06:37Z","isPatch":true,"body":"When the myers algorithm is selected the input files are pre-processed\nto remove any common prefix and suffix. There are a couple of places\nwhere we allocate arrays large enough to hold the whole file when\nthey only need to be big enough to hold the remaining lines after the\ncommon prefix and suffix have been removed. This series adjusts those\nallocations to avoid allocating space for the common lines.\n\nThese patches are based on 'en/xdiff-cleanup-3'\n\nChanges since V1:\n - rebased onto updated upstream\n\nBase-Commit: f87808b7014cf06db4a7e19b193cf9aa7e965ebc\nPublished-As: https://github.com/phillipwood/git/releases/tag/pw%2Fxdiff-reduce-array-sizes%2Fv2\nView-Changes-At: https://github.com/phillipwood/git/compare/f87808b70...d7cb49a7c\nFetch-It-Via: git fetch https://github.com/phillipwood/git pw/xdiff-reduce-array-sizes/v2\n\n\nPhillip Wood (4):\n  xdiff: reduce size of action arrays\n  xdiff: cleanup xdl_clean_mmatch()\n  xprepare: simplify error handling\n  xdiff: reduce the size of array\n\n xdiff/xprepare.c | 46 ++++++++++++++++++++++------------------------\n 1 file changed, 22 insertions(+), 24 deletions(-)\n\nRange-diff against v1:\n1:  447b8c0af17 ! 1:  ec692cabfec xdiff: reduce size of action arrays\n    @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *\n      \t\tgoto cleanup;\n      \t}\n     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n    - \t/*\n    - \t * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.\n    - \t */\n    + \t\tif (mlim1 > XDL_MAX_EQLIMIT)\n    + \t\t\tmlim1 = XDL_MAX_EQLIMIT;\n    + \t}\n     -\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n     -\t\tsize_t mph1 = xdf1->recs[i].minimal_perfect_hash;\n     +\tfor (i = 0; i < len1; i++) {\n    @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *\n      \t\tnm = rcrec ? rcrec->len2 : 0;\n      \t\tif (nm == 0)\n     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n    - \t\t\taction1[i] = INVESTIGATE;\n    + \t\tif (mlim2 > XDL_MAX_EQLIMIT)\n    + \t\t\tmlim2 = XDL_MAX_EQLIMIT;\n      \t}\n    - \n     -\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n     -\t\tsize_t mph2 = xdf2->recs[i].minimal_perfect_hash;\n     +\tfor (i = 0; i < len2; i++) {\n    @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *\n      \txdf1->nreff = 0;\n     -\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n     +\tfor (i = 0; i < len1; i++) {\n    - \t\tif (action1[i] == INVESTIGATE) {\n    + \t\tuint8_t action = action1[i];\n    + \n    + \t\tif (action == INVESTIGATE) {\n     -\t\t\tif (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))\n     +\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n    - \t\t\t\taction1[i] = KEEP;\n    + \t\t\t\taction = KEEP;\n      \t\t\telse\n    - \t\t\t\taction1[i] = DISCARD;\n    + \t\t\t\taction = DISCARD;\n      \t\t}\n      \n    - \t\tif (action1[i] == KEEP) {\n    + \t\tif (action == KEEP) {\n     -\t\t\txdf1->reference_index[xdf1->nreff++] = i;\n     +\t\t\txdf1->reference_index[xdf1->nreff++] = i + off;\n      \t\t\t/* changed[i] remains false */\n    - \t\t} else if (action1[i] == DISCARD)\n    + \t\t} else if (action == DISCARD) {\n     -\t\t\txdf1->changed[i] = true;\n     +\t\t\txdf1->changed[i + off] = true;\n    - \t\telse\n    - \t\t\tBUG(\"Illegal state for action1[i]\");\n    + \t\t} else {\n    + \t\t\tBUG(\"Illegal state for action\");\n    + \t\t}\n      \t}\n      \n      \txdf2->nreff = 0;\n     -\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n     +\tfor (i = 0; i < len2; i++) {\n    - \t\tif (action2[i] == INVESTIGATE) {\n    + \t\tuint8_t action = action2[i];\n    + \n    + \t\tif (action == INVESTIGATE) {\n     -\t\t\tif (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))\n     +\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n    - \t\t\t\taction2[i] = KEEP;\n    + \t\t\t\taction = KEEP;\n      \t\t\telse\n    - \t\t\t\taction2[i] = DISCARD;\n    + \t\t\t\taction = DISCARD;\n      \t\t}\n      \n    - \t\tif (action2[i] == KEEP) {\n    + \t\tif (action == KEEP) {\n     -\t\t\txdf2->reference_index[xdf2->nreff++] = i;\n     +\t\t\txdf2->reference_index[xdf2->nreff++] = i + off;\n      \t\t\t/* changed[i] remains false */\n    - \t\t} else if (action2[i] == DISCARD)\n    + \t\t} else if (action == DISCARD) {\n     -\t\t\txdf2->changed[i] = true;\n     +\t\t\txdf2->changed[i + off] = true;\n    - \t\telse\n    - \t\t\tBUG(\"Illegal state for action2[i]\");\n    - \t}\n    + \t\t} else {\n    + \t\t\tBUG(\"Illegal state for action\");\n    + \t\t}\n2:  78e9313fd44 ! 2:  977f4577521 xdiff: cleanup xdl_clean_mmatch()\n    @@ xdiff/xprepare.c: void xdl_free_env(xdfenv_t *xe) {\n      \t/*\n      \t * Limits the window that is examined during the similar-lines\n     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n    - \txdf1->nreff = 0;\n    - \tfor (i = 0; i < len1; i++) {\n    - \t\tif (action1[i] == INVESTIGATE) {\n    + \t\tuint8_t action = action1[i];\n    + \n    + \t\tif (action == INVESTIGATE) {\n     -\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n     +\t\t\tif (!xdl_clean_mmatch(action1, i, len1))\n    - \t\t\t\taction1[i] = KEEP;\n    + \t\t\t\taction = KEEP;\n      \t\t\telse\n    - \t\t\t\taction1[i] = DISCARD;\n    + \t\t\t\taction = DISCARD;\n     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n    - \txdf2->nreff = 0;\n    - \tfor (i = 0; i < len2; i++) {\n    - \t\tif (action2[i] == INVESTIGATE) {\n    + \t\tuint8_t action = action2[i];\n    + \n    + \t\tif (action == INVESTIGATE) {\n     -\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n     +\t\t\tif (!xdl_clean_mmatch(action2, i, len2))\n    - \t\t\t\taction2[i] = KEEP;\n    + \t\t\t\taction = KEEP;\n      \t\t\telse\n    - \t\t\t\taction2[i] = DISCARD;\n    + \t\t\t\taction = DISCARD;\n3:  cdcad99edc4 = 3:  24e65d42b72 xprepare: simplify error handling\n4:  a3438dc0933 = 4:  d7cb49a7c99 xdiff: reduce the size of array\n-- \n2.54.0.rc1.174.gd833f386ac5.dirty\n\n"},{"id":"542671","messageId":"ec692cabfec0cb463ddc9efcbb89f43cf1f3ef02.1777903579.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1777903579.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 1/4] xdiff: reduce size of action arrays","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-05-04T14:06:18Z","receivedAt":"2026-05-04T14:06:38Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nWhen the myers algorithm is selected the input files are pre-processed\nto remove any common prefix and suffix. Then any lines that appear\nonly in one side of the diff are marked as changed and frequently\noccurring lines are marked as changed if they are adjacent to a\nchanged line. This step requires a couple of temporary arrays. As as\nthe common prefix and suffix have already been removed, the arrays\nonly need to be big enough to hold the lines between them, not the\nwhole file. Reduce the size of the arrays and adjust the loops that\nuse them accordingly while taking care to keep indexing the arrays\nin xdfile_t with absolute line numbers.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 31 +++++++++++++++++--------------\n 1 file changed, 17 insertions(+), 14 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex beef711067b..3b6bae0d158 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -273,16 +273,19 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \tuint8_t *action1 = NULL, *action2 = NULL;\n \tbool need_min = !!(cf->flags & XDF_NEED_MINIMAL);\n \tint ret = 0;\n+\tptrdiff_t off = xdf1->dstart;\n+\tptrdiff_t len1 = xdf1->dend - off + 1;\n+\tptrdiff_t len2 = xdf2->dend - off + 1;\n \n \t/*\n \t * Create temporary arrays that will help us decide if\n \t * changed[i] should remain false, or become true.\n \t */\n-\tif (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {\n+\tif (!XDL_CALLOC_ARRAY(action1, len1)) {\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n-\tif (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {\n+\tif (!XDL_CALLOC_ARRAY(action2, len2)) {\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n@@ -298,8 +301,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t\tif (mlim1 > XDL_MAX_EQLIMIT)\n \t\t\tmlim1 = XDL_MAX_EQLIMIT;\n \t}\n-\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n-\t\tsize_t mph1 = xdf1->recs[i].minimal_perfect_hash;\n+\tfor (i = 0; i < len1; i++) {\n+\t\tsize_t mph1 = xdf1->recs[i + off].minimal_perfect_hash;\n \t\trcrec = cf->rcrecs[mph1];\n \t\tnm = rcrec ? rcrec->len2 : 0;\n \t\tif (nm == 0)\n@@ -318,8 +321,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t\tif (mlim2 > XDL_MAX_EQLIMIT)\n \t\t\tmlim2 = XDL_MAX_EQLIMIT;\n \t}\n-\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n-\t\tsize_t mph2 = xdf2->recs[i].minimal_perfect_hash;\n+\tfor (i = 0; i < len2; i++) {\n+\t\tsize_t mph2 = xdf2->recs[i + off].minimal_perfect_hash;\n \t\trcrec = cf->rcrecs[mph2];\n \t\tnm = rcrec ? rcrec->len1 : 0;\n \t\tif (nm == 0)\n@@ -335,42 +338,42 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t * false, or become true.\n \t */\n \txdf1->nreff = 0;\n-\tfor (i = xdf1->dstart; i <= xdf1->dend; i++) {\n+\tfor (i = 0; i < len1; i++) {\n \t\tuint8_t action = action1[i];\n \n \t\tif (action == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))\n+\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n \t\t\t\taction = KEEP;\n \t\t\telse\n \t\t\t\taction = DISCARD;\n \t\t}\n \n \t\tif (action == KEEP) {\n-\t\t\txdf1->reference_index[xdf1->nreff++] = i;\n+\t\t\txdf1->reference_index[xdf1->nreff++] = i + off;\n \t\t\t/* changed[i] remains false */\n \t\t} else if (action == DISCARD) {\n-\t\t\txdf1->changed[i] = true;\n+\t\t\txdf1->changed[i + off] = true;\n \t\t} else {\n \t\t\tBUG(\"Illegal state for action\");\n \t\t}\n \t}\n \n \txdf2->nreff = 0;\n-\tfor (i = xdf2->dstart; i <= xdf2->dend; i++) {\n+\tfor (i = 0; i < len2; i++) {\n \t\tuint8_t action = action2[i];\n \n \t\tif (action == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))\n+\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n \t\t\t\taction = KEEP;\n \t\t\telse\n \t\t\t\taction = DISCARD;\n \t\t}\n \n \t\tif (action == KEEP) {\n-\t\t\txdf2->reference_index[xdf2->nreff++] = i;\n+\t\t\txdf2->reference_index[xdf2->nreff++] = i + off;\n \t\t\t/* changed[i] remains false */\n \t\t} else if (action == DISCARD) {\n-\t\t\txdf2->changed[i] = true;\n+\t\t\txdf2->changed[i + off] = true;\n \t\t} else {\n \t\t\tBUG(\"Illegal state for action\");\n \t\t}\n-- \n2.54.0.rc1.174.gd833f386ac5.dirty\n\n"},{"id":"542672","messageId":"977f457752111437f7d6c15a214b2233566cab63.1777903579.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1777903579.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 2/4] xdiff: cleanup xdl_clean_mmatch()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-05-04T14:06:19Z","receivedAt":"2026-05-04T14:06:39Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nRemove the \"s\" parameter as, since the last commit, this function\nis always called with s == 0. Also change parameter \"e\" to expect a\nlength, rather than the index of the last line to simplify the caller.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 7 ++++---\n 1 file changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 3b6bae0d158..81de412875a 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -197,8 +197,9 @@ void xdl_free_env(xdfenv_t *xe) {\n }\n \n \n-static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t s, ptrdiff_t e) {\n+static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t len) {\n \tptrdiff_t r, rdis0, rpdis0, rdis1, rpdis1;\n+\tptrdiff_t s = 0, e = len - 1;\n \n \t/*\n \t * Limits the window that is examined during the similar-lines\n@@ -342,7 +343,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t\tuint8_t action = action1[i];\n \n \t\tif (action == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action1, i, 0, len1 - 1))\n+\t\t\tif (!xdl_clean_mmatch(action1, i, len1))\n \t\t\t\taction = KEEP;\n \t\t\telse\n \t\t\t\taction = DISCARD;\n@@ -363,7 +364,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t\tuint8_t action = action2[i];\n \n \t\tif (action == INVESTIGATE) {\n-\t\t\tif (!xdl_clean_mmatch(action2, i, 0, len2 - 1))\n+\t\t\tif (!xdl_clean_mmatch(action2, i, len2))\n \t\t\t\taction = KEEP;\n \t\t\telse\n \t\t\t\taction = DISCARD;\n-- \n2.54.0.rc1.174.gd833f386ac5.dirty\n\n"},{"id":"542673","messageId":"24e65d42b72a4e302bdb16125ce75f24659cd8a5.1777903579.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1777903579.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 3/4] xprepare: simplify error handling","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-05-04T14:06:20Z","receivedAt":"2026-05-04T14:06:40Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nIf either of the two allocations fail we want to take the same action\nso use a single if statement. This saves a few lines and makes it\neasier for the next commit to add a couple more allocations.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 7 ++-----\n 1 file changed, 2 insertions(+), 5 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 81de412875a..7a29e5fc474 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -282,11 +282,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t * Create temporary arrays that will help us decide if\n \t * changed[i] should remain false, or become true.\n \t */\n-\tif (!XDL_CALLOC_ARRAY(action1, len1)) {\n-\t\tret = -1;\n-\t\tgoto cleanup;\n-\t}\n-\tif (!XDL_CALLOC_ARRAY(action2, len2)) {\n+\tif (!XDL_CALLOC_ARRAY(action1, len1) ||\n+\t    !XDL_CALLOC_ARRAY(action2, len2)) {\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n-- \n2.54.0.rc1.174.gd833f386ac5.dirty\n\n"},{"id":"542674","messageId":"d7cb49a7c9987ea5526226ce45d8351b7fec5d31.1777903579.git.phillip.wood@dunelm.org.uk","threadId":"65415","inReplyTo":"cover.1777903579.git.phillip.wood@dunelm.org.uk","subject":"[PATCH v2 4/4] xdiff: reduce the size of array","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2026-05-04T14:06:21Z","receivedAt":"2026-05-04T14:06:41Z","isPatch":true,"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nWhen the myers algorithm is selected the input files are pre-processed\nto remove any common prefix and suffix and any lines that appear\nin only one file. This requires a map to be created between the\nlines that are processed by the myers algorithm and the lines in\nthe original file. That map does not include the common lines at the\nbeginning and end of the files but the array is allocated to be the\nsize of the whole file. Move the allocation into xdl_cleanup_records()\nwhere the map is populated and we know how big it needs to be.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 11 ++++-------\n 1 file changed, 4 insertions(+), 7 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 7a29e5fc474..11bada2608a 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -170,12 +170,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n \n \tif (!XDL_CALLOC_ARRAY(xdf->changed, xdf->nrec + 2))\n \t\tgoto abort;\n-\n-\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&\n-\t    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {\n-\t\tif (!XDL_ALLOC_ARRAY(xdf->reference_index, xdf->nrec + 1))\n-\t\t\tgoto abort;\n-\t}\n \n \txdf->changed += 1;\n \txdf->nreff = 0;\n@@ -283,7 +277,10 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd\n \t * changed[i] should remain false, or become true.\n \t */\n \tif (!XDL_CALLOC_ARRAY(action1, len1) ||\n-\t    !XDL_CALLOC_ARRAY(action2, len2)) {\n+\t    !XDL_CALLOC_ARRAY(action2, len2) ||\n+\t    !XDL_ALLOC_ARRAY(xdf1->reference_index, len1) ||\n+\t    !XDL_ALLOC_ARRAY(xdf2->reference_index, len2))\n+\t{\n \t\tret = -1;\n \t\tgoto cleanup;\n \t}\n-- \n2.54.0.rc1.174.gd833f386ac5.dirty\n\n"}]}