bug#43016: replace-region-contents takes a lot of time when called from json-pretty-print-buffer

[Paul Eggert]

On 8/24/20 10:14 AM, Tassilo Horn wrote:
> The actual problem here is that for the specific test file, there are
> (only) 321 compareseq_early_abort tests performed and it seems that the
> first 320 are executed almost immediately (before MAX-SECS are over),
> then no test is performed for minutes, and then a last test is performed
> leading to an early_abort of compareseq followed by delete + insert.

This is due to the lineage of diffseq; if memory serves, its EARLY_ABORT macro 
was introduced for approximate string comparison in GNU gettext, where 
NOTE_INSERT and NOTE_DELETE are associated with doing something that can cause 
the comparison to fail. (It's not clear to me why EARLY_ABORT was broken out of 
NOTE_INSERT and NOTE_DELETE.)

Emacs uses diffseq differently, on much-larger vectors; and it can be CPU-bound 
within diag, which never calls EARLY_ABORT. Although we could add some 
EARLY_ABORT calls to diag Emacs doesn't need that, as it can check for CPU time 
exhaustion in XREF_YREF_EQUAL and longjmp out if there's a problem. I did that 
by installing the first attached patch into Emacs master, which fixes the 
problem (at least for me). I installed the second attached patch into Emacs 
master to fix some other minor issues I noticed while in the neighborhood.

I suppose the first attached patch might be a candidate for backporting into 
Emacs 27 if this bug is considered to be serious enough.

I plan to follow up on the diffseq stack-overflow issue in Bug#42931 in a 
separate email.

I am cc'ing this email to Bruno Haible to give him a heads-up, as he did the 
diffseq engineering for gettext. Bruno, the bug report thread is here:

https://bugs.gnu.org/43016

0001-Fix-replace-region-contents-performance-bug.patch
Description: Text Data

0002-replace-buffer-contents-cleanups.patch
Description: Text Data