user/sven/git.git/xdiff, branch origin/maint

Merge branch 'yc/xdiff-patience-optim'

2025-12-08T22:54:55Z

The way patience diff finds LCS has been optimized. * yc/xdiff-patience-optim: xdiff: optimize patience diff's LCS search

Merge branch 'en/xdiff-cleanup-2'

2025-12-05T05:49:56Z

Code clean-up. * en/xdiff-cleanup-2: xdiff: rename rindex -> reference_index xdiff: change rindex from long to size_t in xdfile_t xdiff: make xdfile_t.nreff a size_t instead of long xdiff: make xdfile_t.nrec a size_t instead of long xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash xdiff: use unambiguous types in xdl_hash_record() xdiff: use size_t for xrecord_t.size xdiff: make xrecord_t.ptr a uint8_t instead of char xdiff: use ptrdiff_t for dstart/dend doc: define unambiguous type mappings across C and Rust

xdiff: optimize patience diff's LCS search

2025-11-28T03:11:41Z

The find_longest_common_sequence() function in patience diff is inefficient as it calls binary_search() for every unique line it encounters when deciding where to put it in the sequence. From instrumentation (using xctrace) on popular repositories, binary_search() takes up 50-60% of the run time within patience_diff() when performing a diff. To optimize this, add a boundary condition check before binary_search() is called to see if the encountered unique line is located after the entire currently tracked longest subsequence. If so, skip the unnecessary binary search and simply append the entry to the end of sequence. Given that most files compared in a diff are usually quite similar to each other, this condition is very common, and should be hit much more frequently than the binary search. Below are some end-to-end performance results by timing `git log --shortstat --oneline -500 --patience` on different repositories with the old and new code. Generally speaking this seems to give at least 8-10% speed up. The "binary search hit %" column describes how often the algorithm enters the binary search path instead of the new faster path. Even in the WebKit case we can see that it's quite rare (1.46%). | Repo | Speed difference | binary search hit % | |----------|------------------|---------------------| | vim | 1.27x | 0.01% | | pytorch | 1.16x | 0.02% | | cpython | 1.14x | 0.06% | | ripgrep | 1.14x | 0.03% | | git | 1.13x | 0.12% | | vscode | 1.09x | 0.10% | | WebKit | 1.08x | 1.46% | The benchmarks were done using hyperfine, on an Apple M1 Max laptop, with git compiled with `-O3 -flto`. Signed-off-by: Yee Cheng Chin Signed-off-by: Junio C Hamano

xdiff: rename rindex -> reference_index

2025-11-18T22:53:11Z

The classic diff adds only the lines that it's going to consider, during the diff, to an array. A mapping between the compacted array, and the lines of the file that they reference, is facilitated by this array. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: change rindex from long to size_t in xdfile_t

2025-11-18T22:53:11Z

The field rindex describes an index offset for other arrays. Change it to size_t. Changing the type of rindex from long to size_t has no cascading refactor impact because it is only ever used to directly index other arrays. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: make xdfile_t.nreff a size_t instead of long

2025-11-18T22:53:11Z

size_t is used because nreff describes the number of elements in memory for rindex. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: make xdfile_t.nrec a size_t instead of long

2025-11-18T22:53:10Z

size_t is used because nrec describes the number of elements for both recs, and for 'changed' + 2. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash

2025-11-18T22:53:10Z

The ha field is serving two different purposes, which makes the code harder to read. At first glance, it looks like many places assume there could never be hash collisions between lines of the two input files. In reality, line_hash is used together with xdl_recmatch() to ensure correct comparisons of lines, even when collisions occur. To make this clearer, the old ha field has been split: * line_hash: a straightforward hash of a line, independent of any external context. Its type is uint64_t, as it comes from a fixed width hash function. * minimal_perfect_hash: Not a new concept, but now a separate field. It comes from the classifier's general-purpose hash table, which assigns each line a unique and minimal hash across the two files. A size_t is used here because it's meant to be used to index an array. This also avoids ` as usize` casts on the Rust side when using it to index a slice. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: use unambiguous types in xdl_hash_record()

2025-11-18T22:53:10Z

Convert the function signature and body to use unambiguous types. char is changed to uint8_t because this function processes bytes in memory. unsigned long to uint64_t so that the hash output is consistent across platforms. `flags` was changed from long to uint64_t to ensure the high order bits are not dropped on platforms that treat long as 32 bits. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano

xdiff: use size_t for xrecord_t.size

2025-11-18T22:53:10Z

size_t is the appropriate type because size is describing the number of elements, bytes in this case, in memory. Signed-off-by: Ezekiel Newren Signed-off-by: Junio C Hamano