Subject: bug#77942: 31.0.50; replace-region-contents gets stuck

From: Stefan Monnier <[email-masked]>
Date: Mon, 21 Apr 2025 17:11:57 -0400

> If N is the buffer size and D is the diff size, and both are large, good
> luck with that. And indeed, reducing the buffer size by 2 orders of
> magnitude makes things acceptable for my use case.

And the fun thing is that in your test case, the "inner function"
`buffer_chars_equal` which compares two chars (which is the part where
the diff code hands us back control so we can check the time against
MAX_SECS, and that's also the place where we probably spend too much
time doing charpos->bytepos conversion) is called only 74 times, at the
very beginning, afterwards there's just a very long processing inside
the diff code itself without looking at the buffer contents (or the
replacement string for that matter).

I actually haven't checked the way the algorithm works, but I get the
impression that this is a case that can be optimized further.  🙂
Paul, IIUC you've played with this algorithm.  Would you be tempted to
try and improve that situation where the replacement text is *much*
smaller the text it replaces?

Gerd, IIUC you're trying to use this to benchmark the charpos->bytepos
code, in which case you should be better served by a call where the text
and its replacement are of fairly similar size.

        Stefan