[Toybox] histogram diff

[Rob Landley]

On 1/31/25 11:18, Ray Gardner wrote:
> On Fri, Jan 31, 2025 at 7:19 AM Rob Landley <rob at landley.net> wrote:
>>
>> On 1/30/25 17:59, Ray Gardner wrote:
>>>> [patience diff] may have predated the "histogram" algorithm which is
>>>> surprisingly hard to google for...
>>>> ...
>>>> I was really hoping I could implement just ONE algorithm and call it good.
>>>> Right now it looks like "histogram" would be that one (it's an improvement
>> I just started work on my diff branch again after
>> https://github.com/landley/toybox/issues/489#issuecomment-2588079658
>> with the goal of replacing code I don't understand with code I do
>> understand.
>> ...
>> If I throw what I've done and replace the code I understand with code I
>> don't understand, it will go behind "man.c" on the todo list.
> 
> As I quoted, you indicated you wanted a histogram diff.

I did. For many years. Heck, view source on 
https://landley.net/notes-2008.html and the commented out todo list at 
the top has an entry about it. (I was following his livejournal when he 
posted it, that's how I found out about it.)

But I also wanted a simple streaming diff that worked like the opposite 
of "patch", doing one pass scanning along two files and zipping them 
together without having to load both simultaneously into memory or 
requiring lseek().

When I sat down to try to implement patience from the old livejournal 
entry... it was very much not that. And what it did do was 
computationally expensive in multiple ways, and needed a fallback 
algorithm anyway.

All these diff algorithms have pathological edge cases, and when 
fiddling with them I get distracted by what the failure modes would be 
and what inputs would trigger them. Max memory use, max cpu time, hunks 
being way bigger than they need to be, hunks being unreadable salad when 
the actual change isn't...

Back when I was shoveling through this the first time I was wondering if 
there's some sort of diff test corpus out there to compare algorithms 
against, but "implementing diff in multiple ways" doesn't seem to be a 
large enough community for such a thing. (I'd really hoped Bram Cohen 
had test inputs showing conventional diff vs his new algorithm, but when 
I went to look I couldn't find them. Maybe there were some in 2007 and 
they fell off the net?)

I was never worried about producing something that works on a simple 
test input, I was worried about figuring out what inputs would break 
what I'd written, in what ways. Where "break" isn't always "wrong 
answer", but "expensive to compute" or "results are unnecessarily hard 
for a human to read".

> I put a pretty
> detailed explanation at the end of my submission (can see it in the
> patch) and more, including pseudocode, in my blog post
> https://raygard.net/2025/01/28/how-histogram-diff-works/ .

Ooh, very's nice. I have the tab open and have read through the first 
quarter of it and need more caffeine and a nap before tackling this.

> It's (I hope)
> easier to understand than Hunt-McIlroy or Myers, as it's not based on
> any CS theory but on an empirical method that just works pretty well.
> Well enough that Torvalds prefers it for patch submissions
> (https://lkml.org/lkml/2023/5/7/206).
> 
>> What is "hunky-dory code" in this context?
> 
> Just a reference to your function names hunky() and dory() and their
> friends in your hunk detection (etc.) code.

Ah, ok. Not a bad name for it, I just hadn't connected the dots. (I have 
terrible naming hygiene during development, especially while sleep 
deprived. I went through later to remove everything named after Roger 
Zelazny's "nine princes in amber" series from patch.c and all the 
beatles references in ps.c, but that's a cleanup pass at the end.)

The core of that algorithm is finding the end of the next hunk, either 
the next X matching lines or EOF on either input. The rest of it boils 
down to counting consecutive pairs of matching lines (cheap) or figuring 
out what to emit once you've delineated a hunk (tricksy but not expensive).

The brute force way of finding the next matching line pair is N^2 
computationally expensive in the size of the current hunk: just read a 
line from one of the inputs and scan back over the previously seen lines 
of the other to see if it matches. If so, can I read MORE lines from 
that input source to get X consecutive matches at that point in the 
other input source? (At which point I've ended the hunk, and generally 
one of the inputs has read ahead and has some buffered lines.) Alternate 
which input you're reading a new line from because we dunno which one 
did an insert and which one did a deletion.

That said, individual hunks larger than a couple hundred lines are 
uncommon. There IS pathological input that would make this slow and use 
a lot of memory (basically diff -u <(seq 1 1000000) <(seq 1000000 -1 1) 
) but it's still only N^2 on number of input lines slow (not any sort of 
X^N shenanigans, it should finish even given a gigabyte of differing 
input on each end, just not conveniently). And its pathological memory 
use case is the base memory use of the other algorithms. And I COULD 
apply hashing to speed the search up (modulo -i and -b and -I would have 
to apply to the hash too in order to be of any benefit, don't ask me how 
-I regex is supposed to hash, "cut out the match and replace it with an 
empty string" isn't actually what the man page describes -I as 
doing...). But I have yet to find a real world input that would actually 
benefit from it rather than net lose from the overhead, and NOT doing it 
is simplier.

The positive tradeoff is it doesn't care about the size of the _file_ 
because the matching parts are almost free. Comparing two matching lines 
and discarding them when not currently in a differing hunk is O(1) 
("yup, they still match up, keep going"), and everything before the 
current hunk has already been output/discarded so makes no difference to 
processing the current hunk. And that's SHOULD be optimizing for the 
common case, I think?

Note that X to end current hunk is actually 2x+1 the usual start/end 
context because if your hunks have 3 context lines but your files have 
"change, 5 same lines, another change" then that's one hunk with 5 
consecutive unchanged in the middle. No really:

$ diff -u <(printf '%s\n' a b c d e f g h i j) <(printf '%s\n' a j c d e 
f g h k j)
--- /dev/fd/63	2025-01-31 13:13:37.357744367 -0600
+++ /dev/fd/62	2025-01-31 13:13:37.357744367 -0600
@@ -1,10 +1,10 @@
  a
-b
+j
  c
  d
  e
  f
  g
  h
-i
+k
  j
landley at driftwood:~/toybox/clean2$ diff -u <(printf '%s\n' a b c d e f g 
h i i j) <(printf '%s\n' a j c d e f g h i k j)
--- /dev/fd/63	2025-01-31 13:13:54.946009279 -0600
+++ /dev/fd/62	2025-01-31 13:13:54.950009339 -0600
@@ -1,5 +1,5 @@
  a
-b
+j
  c
  d
  e
@@ -7,5 +7,5 @@
  g
  h
  i
-i
+k
  j

This is for two reasons: 1) ending a hunk and starting a new hunk is a 
longer output than just letting it run, 2) patch doesn't reprocess its 
output and thus can't apply overlapping hunks. (It also needs hunks to 
occur in order. Strangely that's not just a limitation of MY patch, 
other patch programs consider hunks out of order within the same file 
illegal. Concatenating patches works because they close and re-open the 
file, which starts over at the beginning. That's part of the reason I 
did mine my way, because as long as that limitation's there anyway...)

Yes, the 2x case being treated as contiguous is a weird edge case, I 
would have thought 2x was where it would break (the point where patch 
doesn't have to reprocess output of a previous hunk to apply the next 
patch), but it's 2x+1 (because that's where output size is equivalent 
with the @@ resync line) which means a hunk can't be considered "done" 
until we've seen 2x+1 matching trailing lines (or EOF on at least one 
input).

Once you've loaded and terminated a hunk, you know how many leading and 
trailing common lines the resulting hunk should output (leading common 
lines naturally match up, but I mentioned needing to treat TRAILING 
common lines specially because they don't automatically zip back 
together all the time, although I have yet to to find my test case of 
where they didn't) and if they don't it sends the wrong signal to patch 
(which COUNTS leading/trailing match lines to detect "must match SOF/EOF").

That was the pending bug I needed to fix back when I mothballed this 
because I got too many "why are you ignoring code that works to go off 
and putter with something irrelevant, shame on you wasting our time" 
pokes and walked away for a while. The challenging part wasn't fixing 
the bug, the problem was delineating the edge cases and coming up with 
all the tests for them. Because you can mix SOF and EOF into there too, 
and it should handle them all right, and the hard part isn't handling 
them right it's making sure you've tested each one so you can PROVE it's 
handling them right. I suspect I blogged about this at the time...)

And then you have a pile of lines in between that need to be output with 
+, space, and -. That's the part where I thought patience/histogram 
might come in (and potentially the constraint of operating WITHIN a 
known hunk might cancel out the computational expense), but doing 
patience _within_ already delineated hunks turned out not to be what it 
was designed for at all.

Note that one thing this algorithm (fairly fundamentally) cannot do is 
detect REORDERED hunks. (I miss the OS/2 tool that did that in 1996. It 
was really nice to use. Color coded output, drew little diagonal lines 
between the left side and right side versions when it detected 
reorders... Alas, IBM propritetary. Part of my formative "don't get 
addicted to proprietary crap, this too shall pass and then you'll have 
withdrawl symptoms when it's gone extinct", LONG before its logical 
continuation "cloud is bad, do not cloud".)

But diff doesn't have a syntax for specially marking reordered hunks 
(not unified diff, anyway), it treats it as a deletion and an insertion. 
And patch couldn't handle it either because of the 
not-reprocessing-output limitation. (Git added some file level move 
indications, but even they don't have a syntax to move text within a file.)

So if what you're looking for is "here's the set of transforms to turn A 
into B", this should reliably give you a workable answer. (Modulo 
fixable bugs.) Will it produce the most human-readable possible answer? 
Not sure. When the next hunk starts and ends seems to have fairly 
deterministic right answers, it's the + and - decisions within a hunk 
that vary. (I think.) And "what were you thinking" should be easy for a 
human to work through with this algorithm. If somebody comes to me with 
a good "This was just X, you got confused" test input maybe I can tweak 
the +/- output emitter to understand what the human saw that the 
algorithm didn't, but I need the tests first.

(Don't ask me how diff3 works into any of this, I've never used it but I 
know git does under the covers so will have to care at some point. And I 
have yet to open the can of worms of marking changes WITHIN lines either.)

> I might not have bothered if I'd known you were into diff again, after
> your posts about how you were sick of it.

Sorry. I _was_ sick of it (not the code, the "stop what you're doing and 
listen to me tell what you should be doing instead"), but somebody needs 
a new feature because kernel, and shortest path to that was beating the 
behavior out of the codebase I theoretically understand.

> I thought you were focused on sh.c.

I am (well, ok, the top of stack is currently kexec for jcore and some 
boot rom rewrites and SOC documentation, but top of stack for TOYBOX is 
sh.c), but real world users coming to me with use cases is always a 
priority boost.

"I need X and can't figure out how to make your tool do it" is the 
highest feedback there is. That's the part I _can't_ know already. Even 
when the answer's just documentation, that's still something that was 
missing.

> Anyway, my code and blog is there if you decide you want to try
> it, see how it works and find out what histogram diff really does.
> I don't expect you will.

I'm definitely reading the blog entry. Thanks for writing it.

> BTW you're concerned that the current pending diff.c may have
> plagiarized code from toybox.

busybox.

(I should have called the new one dorodango. I should have called mkroot 
dorodango. If I actually get an automated LFS bootstrapping project 
working on the level of what aboriginal linux used to do I probably WILL 
call it dorodango. Keep polishing the ball of mud until it shines...)

> I looked at them a bit, and I didn't see a
> lot in common, but the read_tok() function you called out in your issue
> comment, and a related nameless enum of flags or states, bear a strong
> resemblance to read_token() and an enum in busybox diff.c.

Eh, it's not a strong objection, I just got a bit gun-shy after catching 
a source very obviously (obvious to me, the ex-busybox maintainer) doing 
that a few years back.

This was not a straight copy, my cleanups tend to be significant 
rewrites anyway (I'm not entirely sure of the provenance ala ifconfig in 
cleanup.html), and I would LOVE to give Bradley a PR black eye if he 
tried to use busybox to sue toybox. (The new SCO.) But I'm not gonna 
invite it either. Basic hygiene.

Mostly, the problem was cleaning up the old code was several times more 
work (for me) than just writing a new one, and when I broke the old code 
I didn't understand WHY it was broken so everything was endless 
debugging of code I was trying to reverse engineer how to replace it.

> Ray

Rob

P.S. Sorry if I'm reading "stop what you're doing, do this instead, I 
command it" into things that DO NOT MEAN THAT. My motivation has 
recovered a LOT recently but is still sadly fragile, and that's a me 
problem. I spent far too much of last year curled up in a ball waiting 
for the meteor to hit, but now that the worst has basically happened and 
we're back in The Time Of The Circular Firing Squad, I've gotten on with 
it again. (The "loss aversion" part is over: we're fscked. Moving on...)

(Selling a house, moving cross country, my wife graduating and getting a 
full time job so I'm househusbanding now, the industry I'm usually 
employed in having the same kind of layoffs the dot-com crash and 
mortgage crisis caused while smiling and claiming everything's fine (I'm 
ok for now but not all my friends are), getting covid AGAIN, and seeing 
america's version of brexit coming 6 months ahead of time and REALLY 
HOPING I WAS WRONG... all that stacked poorly. Not your fault, not 
Oliver's fault, I feel terrible about being unable to properly harness 
your enthusiasm.)