Subject: Re: [PATCH v6 0/6] Xdiff cleanup part 3

From: Phillip Wood <[email-masked]>
Date: Thu, 30 Apr 2026 14:35:49 +0100

Hi Ezekiel

On 29/04/2026 23:08, Ezekiel Newren via GitGitGadget wrote:
> Changes in v6:
> 
>   * implement suggestions by Phillip Wood [1,2]
> 
> Phillip's second "if" in [1] differs from his first one. In my changes I
> made both of them structurally the same.

I was in two minds about whether to do that or not, all the changes here 
look good to me.

Juino - are you happy to rebase pw/xdiff-shrink-memory-consumption, or 
do you want be to send a re-roll?

> Something I'm confused by is the range-diff of patch 5. I'm confused why
> range-diff states that this is different at all. I don't think this is a
> problem, I just don't like not being able to explain a difference pointed
> out by range-diff.

The context line below the insertion of "action1[i] = INVESTIGATE;" has 
changed do to the changes to patch 4. It would be nice if there was a 
way to tell range-diff to ignore hunks where only the context lines have 
changed but nobody has implemented that yet.

Thanks

Phillip

> 5: 88c68fa89a ! 5: 099b08c33f xdiff/xdl_cleanup_records: make setting action easier to follow
 > @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t 
cf, xdfile_t *
 >  +			action1[i] = > INVESTIGATE;
 >   	}>
> - 	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
> + 	if (need_min) {
> +@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>              size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
>              rcrec = cf->rcrecs[mph2];
>              nm = rcrec ? rcrec->len1 : 0;
> 
> 
> [1] limits
> https://lore.kernel.org/git/[email-masked]/
> [2] action execution
> https://lore.kernel.org/git/[email-masked]/
> 
> Changes in v5:
> 
>   * drop commit "xdiff/xdl_cleanup_records: simplify INVESTIGATE handling for
>     clarity".
>   * add braces around the else clause
> 
> I didn't see a better way to rewrite how action is used so I reverted to
> what it used to be.
> 
> Changes in v4:
> 
>   * Change SIZE_MAX to PTRDIFF_MAX.
> 
> Changes in v3:
> 
>   * run make DEVELOPER=1 on each commit and fix all compiler issues
> 
> v2 is a radical departure from v1 Changes in v2:
> 
>   * make the flow of xdl_cleanup_records() easier to follow
> 
> There is no performance or behavioral change introduced in this patch
> series.
> 
> === original cover letter bellow ===
> 
> Patch series summary:
> 
>   * patch 1: Introduce the ivec type
>   * patch 2: Create the function xdl_do_classic_diff()
>   * patches 3-4: generic cleanup
>   * patches 5-8: convert from dstart/dend (in xdfile_t) to
>     delta_start/delta_end (in xdfenv_t)
>   * patches 9-10: move xdl_cleanup_records(), and related, from xprepare.c to
>     xdiffi.c
> 
> Things that will be addressed in future patch series:
> 
>   * Make xdl_cleanup_records() easier to read
>   * convert recs/nrec into an ivec
>   * convert changed to an ivec
>   * remove reference_index/nreff from xdfile_t and turn it into an ivec
>   * splitting minimal_perfect_hash out as its own ivec
>   * improve the performance of the classifier and parsing/hashing lines
> 
> === before this patch series typedef struct s_xdfile { xrecord_t *recs;
> size_t nrec; ptrdiff_t dstart, dend; bool *changed; size_t *reference_index;
> size_t nreff; } xdfile_t;
> 
> typedef struct s_xdfenv { xdfile_t xdf1, xdf2; } xdfenv_t;
> 
> === after this patch series typedef struct s_xdfile { xrecord_t *recs;
> size_t nrec; bool *changed; size_t *reference_index; size_t nreff; }
> xdfile_t;
> 
> typedef struct s_xdfenv { xdfile_t xdf1, xdf2; size_t delta_start,
> delta_end; size_t mph_size; } xdfenv_t;
> 
> Ezekiel Newren (6):
>    xdiff/xdl_cleanup_records: delete local recs pointer
>    xdiff: use unambiguous types in xdl_bogo_sqrt()
>    xdiff/xdl_cleanup_records: use unambiguous types
>    xdiff/xdl_cleanup_records: make limits more clear
>    xdiff/xdl_cleanup_records: make setting action easier to follow
>    xdiff/xdl_cleanup_records: make execution of action easier to follow
> 
>   xdiff/xdiffi.c   |  2 +-
>   xdiff/xprepare.c | 97 ++++++++++++++++++++++++++++++++++--------------
>   xdiff/xutils.c   |  4 +-
>   xdiff/xutils.h   |  2 +-
>   4 files changed, 73 insertions(+), 32 deletions(-)
> 
> 
> base-commit: ca1db8a0f7dc0dbea892e99f5b37c5fe5861be71
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2156%2Fezekielnewren%2Fxdiff-cleanup-3-v6
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2156/ezekielnewren/xdiff-cleanup-3-v6
> Pull-Request: https://github.com/git/git/pull/2156
> 
> Range-diff vs v5:
> 
>   1:  b31924a949 = 1:  b31924a949 xdiff/xdl_cleanup_records: delete local recs pointer
>   2:  1822166fef = 2:  1822166fef xdiff: use unambiguous types in xdl_bogo_sqrt()
>   3:  85aa0da90c = 3:  85aa0da90c xdiff/xdl_cleanup_records: use unambiguous types
>   4:  fec2b0f38a ! 4:  51c62ed454 xdiff/xdl_cleanup_records: make limits more clear
>       @@ Commit message
>              * The additional condition `!need_min` is redudant now, remove it.
>            Best viewed with --color-words.
>        
>       +    Helped-by: Phillip Wood
>            Signed-off-by: Ezekiel Newren <[email-masked]>
>        
>         ## xdiff/xprepare.c ##
>       @@ xdiff/xprepare.c: static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t
>         	uint8_t *action1 = NULL, *action2 = NULL;
>         	bool need_min = !!(cf->flags & XDF_NEED_MINIMAL);
>        @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>       - 		goto cleanup;
>       - 	}
>       -
>       -+	if (need_min) {
>       -+		/* i.e. infinity */
>       -+		mlim1 = PTRDIFF_MAX;
>       -+		mlim2 = PTRDIFF_MAX;
>       -+	} else {
>       -+		mlim1 = XDL_MIN(xdl_bogosqrt(xdf1->nrec), XDL_MAX_EQLIMIT);
>       -+		mlim2 = XDL_MIN(xdl_bogosqrt(xdf2->nrec), XDL_MAX_EQLIMIT);
>       -+	}
>       -+
>         	/*
>         	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
>         	 */
>        -	if ((mlim = (long)xdl_bogosqrt((uint64_t)xdf1->nrec)) > XDL_MAX_EQLIMIT)
>        -		mlim = XDL_MAX_EQLIMIT;
>       ++	if (need_min) {
>       ++		/* i.e. infinity */
>       ++		mlim1 = PTRDIFF_MAX;
>       ++	} else {
>       ++		mlim1 = xdl_bogosqrt((uint64_t)xdf1->nrec);
>       ++		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;
>         		rcrec = cf->rcrecs[mph1];
>       @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
>         
>        -	if ((mlim = (long)xdl_bogosqrt((uint64_t)xdf2->nrec)) > XDL_MAX_EQLIMIT)
>        -		mlim = XDL_MAX_EQLIMIT;
>       ++	if (need_min) {
>       ++		/* i.e. infinity */
>       ++		mlim2 = PTRDIFF_MAX;
>       ++	} else {
>       ++		mlim2 = xdl_bogosqrt((uint64_t)xdf2->nrec);
>       ++		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;
>         		rcrec = cf->rcrecs[mph2];
>   5:  88c68fa89a ! 5:  45ad2ae62d xdiff/xdl_cleanup_records: make setting action easier to follow
>       @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
>        +			action1[i] = INVESTIGATE;
>         	}
>         
>       - 	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
>       + 	if (need_min) {
>       +@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>         		size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
>         		rcrec = cf->rcrecs[mph2];
>         		nm = rcrec ? rcrec->len1 : 0;
>   6:  699e198fa9 ! 6:  a5174802f4 xdiff/xdl_cleanup_records: put braces around the else clause
>       @@ Metadata
>        Author: Ezekiel Newren <[email-masked]>
>        
>         ## Commit message ##
>       -    xdiff/xdl_cleanup_records: put braces around the else clause
>       +    xdiff/xdl_cleanup_records: make execution of action easier to follow
>        
>       +    Helped-by: Phillip Wood
>            Signed-off-by: Ezekiel Newren <[email-masked]>
>        
>         ## xdiff/xprepare.c ##
>        @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>       - 		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
>       + 	 */
>       + 	xdf1->nreff = 0;
>       + 	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
>       +-		if (action1[i] == KEEP ||
>       +-		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
>       ++		uint8_t action = action1[i];
>       ++
>       ++		if (action == INVESTIGATE) {
>       ++			if (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))
>       ++				action = KEEP;
>       ++			else
>       ++				action = DISCARD;
>       ++		}
>       ++
>       ++		if (action == KEEP) {
>         			xdf1->reference_index[xdf1->nreff++] = i;
>       - 			/* changed[i] remains false, i.e. keep */
>       +-			/* changed[i] remains false, i.e. keep */
>        -		} else
>       -+		} else {
>       ++			/* changed[i] remains false */
>       ++		} else if (action == DISCARD) {
>         			xdf1->changed[i] = true;
>       - 			/* i.e. discard */
>       +-			/* i.e. discard */
>       ++		} else {
>       ++			BUG("Illegal state for action");
>        +		}
>         	}
>         
>         	xdf2->nreff = 0;
>       -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>       - 		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
>       + 	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
>       +-		if (action2[i] == KEEP ||
>       +-		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
>       ++		uint8_t action = action2[i];
>       ++
>       ++		if (action == INVESTIGATE) {
>       ++			if (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))
>       ++				action = KEEP;
>       ++			else
>       ++				action = DISCARD;
>       ++		}
>       ++
>       ++		if (action == KEEP) {
>         			xdf2->reference_index[xdf2->nreff++] = i;
>       - 			/* changed[i] remains false, i.e. keep */
>       +-			/* changed[i] remains false, i.e. keep */
>        -		} else
>       -+		} else {
>       ++			/* changed[i] remains false */
>       ++		} else if (action == DISCARD) {
>         			xdf2->changed[i] = true;
>       - 			/* i.e. discard */
>       +-			/* i.e. discard */
>       ++		} else {
>       ++			BUG("Illegal state for action");
>        +		}
>         	}
>         
>