From: Yee Cheng Chin Date: Thu, 29 Jan 2026 16:53:04 GMT Subject: Re: [PATCH] xdiff: re-diff shifted change groups when using histogram algorithm Message-ID: In-Reply-To: Thanks for the review and sorry for being a little late in replying. Aggregating all my inline replies in one email if that's ok. On Wed, Jan 21, 2026 at 12:51 PM Junio C Hamano wrote: > So the idea is to remember the original values in g and go (the > location of the group in the file and the other file) and if > shifting up and down changed any one of the four ends from the > original locations, we always take the fall-back route (if we are > doing histogram)? > > By the way, this appears after the if/else if/ cascade that has: > > if (g.end == earliest_end) { > ... do nothing case (case #1) > } else if (end_matching_other != -1) { > ... do the slide-up thing (case #2) > } else if (flags & XDF_INDENT_HEIRISTIC) { > ... do the indent heuristic thing (case #3) > } > > Am I reading the code correctly that, even though this new block > appears as if it is a post-clean-up phase that is independent from > which one of the three choices are taken in the previous if/elseif > cascade, it only is relevant to the second case? I am wondering if > it would make it easier to follow if the new code were made into a > small helper function that is called from the (case #2) arm of the > existing if/else if cascade. That's correct. This condition happens only in the 2nd case. The problematic scenario here only happens when the opposite side is non-empty. If the opposite is empty (case #3, where we run the indent heuristic algorithm), there's simply no need to re-diff anything because diff'ing against an empty hunk is pointless. You made a good point about placing it in the if block itself. The existing code was a little confusing and took me re-reading the code before I remember the condition. I'll fix it in v2. On Sat, Jan 24, 2026 at 2:54 AM Phillip Wood wrote: > I'm a bit confused why we need to check both groups. I think they're > supposed to move together (if we move "g" by n context lines we also > move "go" by n context lines) so I can't see how we can have > > g.start == g_orig.start && g.end == g_orig.end > > when > > go.start != go.orig.start || go.end != go_orig.end > You are right. It was an over-specification. Looking through the code we should be able to just use "g" and there is no need to test for "g_orig". Will fix in v2. > >> + xpparam_t xpp; > >> + xdfenv_t xe; > >> + > >> + memset(&xpp, 0, sizeof(xpp)); > >> + xpp.flags = flags & ~XDF_DIFF_ALGORITHM_MASK; > >> + > >> + memcpy(&xe.xdf1, xdf, sizeof(xdfile_t)); > >> + memcpy(&xe.xdf2, xdfo, sizeof(xdfile_t)); > > These would be safer as "xe.xdf1 = *xdf" so we don't have to worry about > getting the size correct (sizeof(*xdf) would also be safer but there is > no need for memcpy() here). Will fix in v2. > I also wondered if we need to do a diff or if we can just mark the > common prefix and suffix as unchanged but I suspect that wont will work > for more complicated examples. Common prefix/suffix would not work for more complicated examples. Here's an example (imagine each character to be its own line): File 1: A AAyz AAA File 2: A xAA AAA The current Git histogram diff generates the following: A [-AAyz -]{+xAA +}AAA After the fix, we have: A {+x+}AA[-yz-] AA Note that there is no common prefix here, and we need a real diff algorithm if we want to solve this issue in a generic fashion. As I mentioned in the cover letter, I thought about implementing a "bespoke linear-time algorithm" but decided against it. What I meant was we could implement a simple diff algorithm that finds the common lines in both hunks that would run faster than Myer's, but isn't guaranteed to be a optimal minimal diff. I decided that it is unnecessary to overcomplicate things given that we can just call the fallback diff. On Mon, Jan 26, 2026 at 1:37 AM Phillip Wood wrote: > > On 25/01/2026 17:34, Junio C Hamano wrote: > > Also, after reading the first paragraph of the big comment again, it > > makes me wonder if it is saying the same thing as "When histogram is > > being used, we shouldn't bother shifting up and down to join groups, > > as the result will always worse than the fallback", but is it that > > bad? > > Looking at the example in the commit message the result of shifting up > and down and then calling the fallback is better than either the > unshifted diff or shifting without the fallback, so I don't think just > disabling shifting improves things. It would also stop us coalescing > changed lines, for example > > -A A > A -> -A > -B -B > I agree with you, but I think it is actually a nuanced decision. The histogram diff algorithm explicitly chose the specific alignment/anchor points to align both files due to the frequency of the lines. When we do the sliding / compaction step, we are essentially ignoring and overriding the algorithmic decision made by histogram, for the sake of other metrics that we value (compaction values fewer diff hunks, and indent heuristics values aligning by semantics approximated by indentation). I think those metrics do help which is why we added them, but there's a bit of design tension between the underlying algorithm and the cleanup step. > To me the problem is that the histogram diff does not always generate > particularly good diffs (maybe I'm biased - whenever I've tried > switching the default to "histogram" I've always switched back > "patience" fairly quickly after being presented with a diff that I found > hard to comprehend) FWIW I personally feel that way as well. I think the documentation and narrative that histogram diff is a "more advanced/extended version" of patience diff is sometimes problematic, as both algorithms are fairly different and have their own weaknesses. The Longest Common Subsequence (LCS) used for alignment in patience diff is global for the file and allows gaps, whereas the LCS in histogram diff requires consecutive lines. This means even if the diff has unique lines across both files the diff results could be quite different between histogram and patience. This consecutive requirement for a subsequence is why histogram diff runs faster than patience diff most of the time, but it does mean the patience algorithm is better at discovering a global "spine" across a file.