Re: [PATCH 00/10] Xdiff cleanup part 3

[Phillip Wood <phillip.wood123@gmail.com>]

The discussion of this series has got rather spread out so I thought it 
might be helpful to write a summary of my thoughts here.

On 02/01/2026 18:52, Ezekiel Newren via GitGitGadget wrote:
> Patch series summary:
> 
>   * patch 1: Introduce the ivec type

I agree this is a good idea to allow rust and C code to operate on the 
some data structure. The implementation needs a bit of work to avoid 
undefined behavior.

>   * patch 2: Create the function xdl_do_classic_diff()

This is sensible

>   * patches 3-4: generic cleanup

Patch 3 claims to "stop wasting time" but it introduces an extra pass 
over the input records without any explanation of why that is more 
efficient.

Patch 4 removes the common lines from the beginning and end of the input 
files before passing them on to the patience or histogram algorithms. 
That should speed things up (though we should measure by how much). It 
changes the output because excluding the common lines at beginning and 
end of the file changes the longest sequence of unique context lines in 
the lines that remain. If the different output is easier to read then 
that's clearly a good thing but you would need to do some analysis to 
show that.

>   * patches 5-8: convert from dstart/dend (in xdfile_t) to
>     delta_start/delta_end (in xdfenv_t)

dstart a dend in xdfile_t are the index of the first and last line after 
removing any common lines from the beginning and end. The proposal is to 
store the offset from the beginning and end instead in xdfenv_t. Looking 
at where dstart and dend are used I think storing the indices is more 
convenient - if we store offsets we end up calculating the indices from 
them which is a pain and introduces an opportunity to make an error.

>   * patches 9-10: move xdl_cleanup_records(), and related, from xprepare.c to
>     xdiffi.c

Here we finally get to use the ivec data structre introduced in patch 1. 
However it is just replacing a fixed size array and so does not 
demonstrate the more interesting parts of the API which concern growing 
the array as we push more elements to it. I'm also not convinced by the 
claim that this change saves time as it introduces an extra pass over 
the input records.

Overall I struggled to see how the cleanups proposed here linked to the 
introduction of the ivec data structure.

Thanks

Phillip

> 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 (10):
>    ivec: introduce the C side of ivec
>    xdiff: make classic diff explicit by creating xdl_do_classic_diff()
>    xdiff: don't waste time guessing the number of lines
>    xdiff: let patience and histogram benefit from xdl_trim_ends()
>    xdiff: use xdfenv_t in xdl_trim_ends() and xdl_cleanup_records()
>    xdiff: cleanup xdl_trim_ends()
>    xdiff: replace xdfile_t.dstart with xdfenv_t.delta_start
>    xdiff: replace xdfile_t.dend with xdfenv_t.delta_end
>    xdiff: remove dependence on xdlclassifier from xdl_cleanup_records()
>    xdiff: move xdl_cleanup_records() from xprepare.c to xdiffi.c
> 
>   Makefile           |   1 +
>   compat/ivec.c      | 113 ++++++++++++++++++
>   compat/ivec.h      |  52 +++++++++
>   meson.build        |   1 +
>   xdiff/xdiffi.c     | 221 +++++++++++++++++++++++++++++++++---
>   xdiff/xdiffi.h     |   1 +
>   xdiff/xhistogram.c |   7 +-
>   xdiff/xpatience.c  |   7 +-
>   xdiff/xprepare.c   | 277 ++++++++-------------------------------------
>   xdiff/xtypes.h     |   3 +-
>   xdiff/xutils.c     |  20 ----
>   xdiff/xutils.h     |   1 -
>   12 files changed, 432 insertions(+), 272 deletions(-)
>   create mode 100644 compat/ivec.c
>   create mode 100644 compat/ivec.h
> 
> 
> base-commit: 66ce5f8e8872f0183bb137911c52b07f1f242d13
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2156%2Fezekielnewren%2Fxdiff-cleanup-3-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2156/ezekielnewren/xdiff-cleanup-3-v1
> Pull-Request: https://github.com/git/git/pull/2156