Improve performance for diffs with very large hunks

[mookid]

See https://scripter.co/git-diff-minified-js-and-css/

On the repository https://github.com/gohugoio/hugoDocs, git log -p -- themes/gohugoioTheme/static/dist/app.bundle.js | diffr takes ~9min on my machine.

One problematic commit: 0960c5fb36e9abcf3b492a523943268e89066543

Explore possible workarounds:

• stop LCS when the middle snake is good enough?
• delect long lines?

[mlncn]

I'm hitting diffs where git add -p can take hours, and it took a while to realize diffr was the cause— i had gotten used to beautiful, useful diffs and forgotten i was not on git standard.

One thing i do not understand is why it has seemingly suddenly gotten much worse for me. As in, in just the last week, went from never thinking about it (effectively instant) to being completely unusable, across multiple projects of the kind i always work with. Some underlying tool that might have gotten an update?

Anyhow strong vote for some way to detect and bail on long lines. Maybe something configurable, and to not try to diff lines longer than 500 characters by default.

[mookid]

sorry about the bad experience.
of course, if you have a reproduction case, I would be very happy to have a look.

An relatively easy way to proceed would be to periodically check for maximal processing time for a given hunk, and bail if necessary (and fallback to the default diff processing)

I will most likely no do the coding myself (my company is not very supportive of open source at all) but I can provide some guidance if anyone would want try to tackle it

[Hi-Angel]

Part of a reason for the slowness might be a massive amount of generating excess escape sequences. See, e.g. this two lines change looks like this with the escape sequences:

Clearly, most of them are unneeded.

[mookid]

I think that the slow cases are bad cases of the Myers algo, which is quadratic in number of tokens if the before/after are very different. I don't think that the added control chars are enough to make it slower by itself.

[CervEdin]

I experience the issue with VERY large diffs. 500 lines was fine but 1k+ it becomes a problem.

Here's a script to reproduce the issue

tr -dc a-z1-4 </dev/urandom |
  tr 1-2 ' \n' |
  awk 'length==0 || length>50' |
  tr 3-4 ' ' |
  sed 's/^ *//' |
  cat -s |
  sed 's/ / /g' |
  fmt |
  head -n 2000 > /tmp/random-1.txt &&
  tr -dc a-z1-4 </dev/urandom |
  tr 1-2 ' \n' |
  awk 'length==0 || length>50' |
  tr 3-4 ' ' |
  sed 's/^ *//' |
  cat -s |
  sed 's/ / /g' |
  fmt |
  head -n 2000 > /tmp/random-2.txt  &&
  git diff --no-index /tmp/random-1.txt /tmp/random-2.txt |
  diffr

[mookid]

hi @CervEdin

thanks for the report! I have a patch for that, which is very simple. unfortunately, my company does not really allow open source work, so this is stuck there for a while.

[CervEdin]

Hi @mookid

That's great! However, I'm a bit perplexed. Aren't you the maintainer?

[mookid]

I am. I can provide some help to someone motivated to write the code, but can't submit it myself.

The Myers algorithm is incremental: if find the shortest path of length D for each D increasing; my patch just stops after D large-ish (if D is large, the diff will have poor readability annyway) and just falls back to "remove everything, add everything".

[CervEdin]

Fair enough. Maybe I take a look at some point. For now I just switched back the pager of things like git log to diff-highlight

…

On Thu, Apr 20, 2023, 4:17 AM Nathan Moreau ***@***.***> wrote: I am. I can provide some help to someone motivated to write the code, but can't submit it myself. The Myers algorithm is incremental: if find the shortest path of length D for each D increasing; my patch just stops after D large-ish (if D is large, the diff will have poor readability annyway) and just falls back to "remove everything, add everything". — Reply to this email directly, view it on GitHub <#14 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAXL5ESXXHC5NYXPZZO7DE3XCCMCLANCNFSM4IFNDB6Q> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[mookid]

@CervEdin #96 should help with your problem, probably (your script does not work on my system for some reason, I get tr: Illegal byte sequence when running it)