git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 1/4] xdiff: reduce size of action arrays

From
PWPhillip Wood <phillip.wood123@gmail.com>
Date
May 4, 2026, 14:06 UTC
Message-ID
<ec692cabfec0cb463ddc9efcbb89f43cf1f3ef02.1777903579.git.phillip.wood@dunelm.org.uk>
In-Reply-To
<cover.1777903579.git.phillip.wood@dunelm.org.uk>
From: Phillip Wood <phillip.wood@dunelm.org.uk>

When the myers algorithm is selected the input files are pre-processed to remove any common prefix and suffix. Then any lines that appear only in one side of the diff are marked as changed and frequently occurring lines are marked as changed if they are adjacent to a changed line. This step requires a couple of temporary arrays. As as the common prefix and suffix have already been removed, the arrays only need to be big enough to hold the lines between them, not the whole file. Reduce the size of the arrays and adjust the loops that use them accordingly while taking care to keep indexing the arrays in xdfile_t with absolute line numbers.

Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 xdiff/xprepare.c | 31 +++++++++++++++++--------------
 1 file changed, 17 insertions(+), 14 deletions(-)
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index beef711067b..3b6bae0d158 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -273,16 +273,19 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
 	uint8_t *action1 = NULL, *action2 = NULL;
 	bool need_min = !!(cf->flags & XDF_NEED_MINIMAL);
 	int ret = 0;
+	ptrdiff_t off = xdf1->dstart;
+	ptrdiff_t len1 = xdf1->dend - off + 1;
+	ptrdiff_t len2 = xdf2->dend - off + 1;
 
 	/*
 	 * Create temporary arrays that will help us decide if
 	 * changed[i] should remain false, or become true.
 	 */
-	if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {
+	if (!XDL_CALLOC_ARRAY(action1, len1)) {
 		ret = -1;
 		goto cleanup;
 	}
-	if (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {
+	if (!XDL_CALLOC_ARRAY(action2, len2)) {
 		ret = -1;
 		goto cleanup;
 	}
@@ -298,8 +301,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
 		if (mlim1 > XDL_MAX_EQLIMIT)
 			mlim1 = XDL_MAX_EQLIMIT;
 	}
-	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
-		size_t mph1 = xdf1->recs[i].minimal_perfect_hash;
+	for (i = 0; i < len1; i++) {
+		size_t mph1 = xdf1->recs[i + off].minimal_perfect_hash;
 		rcrec = cf->rcrecs[mph1];
 		nm = rcrec ? rcrec->len2 : 0;
 		if (nm == 0)
@@ -318,8 +321,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
 		if (mlim2 > XDL_MAX_EQLIMIT)
 			mlim2 = XDL_MAX_EQLIMIT;
 	}
-	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
-		size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
+	for (i = 0; i < len2; i++) {
+		size_t mph2 = xdf2->recs[i + off].minimal_perfect_hash;
 		rcrec = cf->rcrecs[mph2];
 		nm = rcrec ? rcrec->len1 : 0;
 		if (nm == 0)
@@ -335,42 +338,42 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
 	 * false, or become true.
 	 */
 	xdf1->nreff = 0;
-	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
+	for (i = 0; i < len1; i++) {
 		uint8_t action = action1[i];
 
 		if (action == INVESTIGATE) {
-			if (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))
+			if (!xdl_clean_mmatch(action1, i, 0, len1 - 1))
 				action = KEEP;
 			else
 				action = DISCARD;
 		}
 
 		if (action == KEEP) {
-			xdf1->reference_index[xdf1->nreff++] = i;
+			xdf1->reference_index[xdf1->nreff++] = i + off;
 			/* changed[i] remains false */
 		} else if (action == DISCARD) {
-			xdf1->changed[i] = true;
+			xdf1->changed[i + off] = true;
 		} else {
 			BUG("Illegal state for action");
 		}
 	}
 
 	xdf2->nreff = 0;
-	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
+	for (i = 0; i < len2; i++) {
 		uint8_t action = action2[i];
 
 		if (action == INVESTIGATE) {
-			if (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))
+			if (!xdl_clean_mmatch(action2, i, 0, len2 - 1))
 				action = KEEP;
 			else
 				action = DISCARD;
 		}
 
 		if (action == KEEP) {
-			xdf2->reference_index[xdf2->nreff++] = i;
+			xdf2->reference_index[xdf2->nreff++] = i + off;
 			/* changed[i] remains false */
 		} else if (action == DISCARD) {
-			xdf2->changed[i] = true;
+			xdf2->changed[i + off] = true;
 		} else {
 			BUG("Illegal state for action");
 		}
-- 
2.54.0.rc1.174.gd833f386ac5.dirty
Previous: Phillip WoodNext: Phillip Wood
Message 11 of 14 in “xdiff: reduce the size of a couple of arrays”
  1. 0/4 xdiff: reduce the size of a couple of arraysPhillip Wood, Apr 2, 2026
  2. 1/4 xdiff: reduce size of action arraysPhillip Wood, Apr 2, 2026
  3. Junio C HamanoApr 2, 2026
  4. 2/4 xdiff: cleanup xdl_clean_mmatch()Phillip Wood, Apr 2, 2026
  5. Junio C HamanoApr 2, 2026
  6. 3/4 xprepare: simplify error handlingPhillip Wood, Apr 2, 2026
  7. Junio C HamanoApr 2, 2026
  8. 4/4 xdiff: reduce the size of arrayPhillip Wood, Apr 2, 2026
  9. Junio C HamanoApr 2, 2026
  10. 0/4 xdiff: reduce the size of a couple of arraysPhillip Wood, May 4, 2026
  11. 1/4 xdiff: reduce size of action arraysPhillip Wood, May 4, 2026
  12. 2/4 xdiff: cleanup xdl_clean_mmatch()Phillip Wood, May 4, 2026
  13. 3/4 xprepare: simplify error handlingPhillip Wood, May 4, 2026
  14. 4/4 xdiff: reduce the size of arrayPhillip Wood, May 4, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.