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

[PATCH v2 0/4] xdiff: reduce the size of a couple of arrays

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

When the myers algorithm is selected the input files are pre-processed to remove any common prefix and suffix. There are a couple of places where we allocate arrays large enough to hold the whole file when they only need to be big enough to hold the remaining lines after the common prefix and suffix have been removed. This series adjusts those allocations to avoid allocating space for the common lines.

These patches are based on 'en/xdiff-cleanup-3'
Changes since V1:
 - rebased onto updated upstream
Base-Commit: f87808b7014cf06db4a7e19b193cf9aa7e965ebc
Published-As: https://github.com/phillipwood/git/releases/tag/pw%2Fxdiff-reduce-array-sizes%2Fv2
View-Changes-At: https://github.com/phillipwood/git/compare/f87808b70...d7cb49a7c
Fetch-It-Via: git fetch https://github.com/phillipwood/git pw/xdiff-reduce-array-sizes/v2
Phillip Wood (4):
  xdiff: reduce size of action arrays
  xdiff: cleanup xdl_clean_mmatch()
  xprepare: simplify error handling
  xdiff: reduce the size of array
 xdiff/xprepare.c | 46 ++++++++++++++++++++++------------------------
 1 file changed, 22 insertions(+), 24 deletions(-)
Range-diff against v1:
1:  447b8c0af17 ! 1:  ec692cabfec xdiff: reduce size of action arrays
    @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
      		goto cleanup;
      	}
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
    - 	/*
    - 	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
    - 	 */
    + 		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++) {
    @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
      		nm = rcrec ? rcrec->len2 : 0;
      		if (nm == 0)
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
    - 			action1[i] = INVESTIGATE;
    + 		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++) {
    @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
      	xdf1->nreff = 0;
     -	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
     +	for (i = 0; i < len1; i++) {
    - 		if (action1[i] == INVESTIGATE) {
    + 		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))
    - 				action1[i] = KEEP;
    + 				action = KEEP;
      			else
    - 				action1[i] = DISCARD;
    + 				action = DISCARD;
      		}
      
    - 		if (action1[i] == KEEP) {
    + 		if (action == KEEP) {
     -			xdf1->reference_index[xdf1->nreff++] = i;
     +			xdf1->reference_index[xdf1->nreff++] = i + off;
      			/* changed[i] remains false */
    - 		} else if (action1[i] == DISCARD)
    + 		} else if (action == DISCARD) {
     -			xdf1->changed[i] = true;
     +			xdf1->changed[i + off] = true;
    - 		else
    - 			BUG("Illegal state for action1[i]");
    + 		} else {
    + 			BUG("Illegal state for action");
    + 		}
      	}
      
      	xdf2->nreff = 0;
     -	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
     +	for (i = 0; i < len2; i++) {
    - 		if (action2[i] == INVESTIGATE) {
    + 		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))
    - 				action2[i] = KEEP;
    + 				action = KEEP;
      			else
    - 				action2[i] = DISCARD;
    + 				action = DISCARD;
      		}
      
    - 		if (action2[i] == KEEP) {
    + 		if (action == KEEP) {
     -			xdf2->reference_index[xdf2->nreff++] = i;
     +			xdf2->reference_index[xdf2->nreff++] = i + off;
      			/* changed[i] remains false */
    - 		} else if (action2[i] == DISCARD)
    + 		} else if (action == DISCARD) {
     -			xdf2->changed[i] = true;
     +			xdf2->changed[i + off] = true;
    - 		else
    - 			BUG("Illegal state for action2[i]");
    - 	}
    + 		} else {
    + 			BUG("Illegal state for action");
    + 		}
2:  78e9313fd44 ! 2:  977f4577521 xdiff: cleanup xdl_clean_mmatch()
    @@ xdiff/xprepare.c: void xdl_free_env(xdfenv_t *xe) {
      	/*
      	 * Limits the window that is examined during the similar-lines
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
    - 	xdf1->nreff = 0;
    - 	for (i = 0; i < len1; i++) {
    - 		if (action1[i] == INVESTIGATE) {
    + 		uint8_t action = action1[i];
    + 
    + 		if (action == INVESTIGATE) {
     -			if (!xdl_clean_mmatch(action1, i, 0, len1 - 1))
     +			if (!xdl_clean_mmatch(action1, i, len1))
    - 				action1[i] = KEEP;
    + 				action = KEEP;
      			else
    - 				action1[i] = DISCARD;
    + 				action = DISCARD;
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
    - 	xdf2->nreff = 0;
    - 	for (i = 0; i < len2; i++) {
    - 		if (action2[i] == INVESTIGATE) {
    + 		uint8_t action = action2[i];
    + 
    + 		if (action == INVESTIGATE) {
     -			if (!xdl_clean_mmatch(action2, i, 0, len2 - 1))
     +			if (!xdl_clean_mmatch(action2, i, len2))
    - 				action2[i] = KEEP;
    + 				action = KEEP;
      			else
    - 				action2[i] = DISCARD;
    + 				action = DISCARD;
3:  cdcad99edc4 = 3:  24e65d42b72 xprepare: simplify error handling
4:  a3438dc0933 = 4:  d7cb49a7c99 xdiff: reduce the size of array
-- 
2.54.0.rc1.174.gd833f386ac5.dirty
Previous: Junio C HamanoNext: Phillip Wood
Message 10 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.