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

From: Paul Eggert <[email-masked]>
Date: Mon, 24 Aug 2020 16:35:32 -0700

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
>From 08a6d14e4116c74284c12dd1319780afbcbbfd1d Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 24 Aug 2020 13:12:51 -0700
Subject: [PATCH 1/2] Fix replace-region-contents performance bug

* src/editfns.c (rbc_quitcounter): Remove; the quitcounter
is now part of the context.
(EXTRA_CONTEXT_FIELDS): Remove unused member early_abort_tests.
Add jmp, quitcounter.
(Freplace_buffer_contents): Use setjmp/longjmp to recover from
a compareseq that runs too long.  Omit unnecessary rarely_quit
call.
(buffer_chars_equal): Occasionally check for early abort and
longjmp out if so (Bug#43016).
---
 src/editfns.c | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)

diff --git a/src/editfns.c b/src/editfns.c
index 949f3825a3..a5368c59da 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -1877,9 +1877,6 @@ DEFUN ("compare-buffer-substrings", Fcompare_buffer_substrings, Scompare_buffer_
 #undef EQUAL
 #define USE_HEURISTIC
 
-/* Counter used to rarely_quit in replace-buffer-contents.  */
-static unsigned short rbc_quitcounter;
-
 #define XVECREF_YVECREF_EQUAL(ctx, xoff, yoff)  \
   buffer_chars_equal ((ctx), (xoff), (yoff))
 
@@ -1900,7 +1897,8 @@ #define EXTRA_CONTEXT_FIELDS                    \
   unsigned char *deletions;                     \
   unsigned char *insertions;			\
   struct timespec time_limit;			\
-  unsigned int early_abort_tests;
+  sys_jmp_buf jmp;				\
+  unsigned short quitcounter;
 
 #define NOTE_DELETE(ctx, xoff) set_bit ((ctx)->deletions, (xoff))
 #define NOTE_INSERT(ctx, yoff) set_bit ((ctx)->insertions, (yoff))
@@ -2029,14 +2027,17 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
     .heuristic = true,
     .too_expensive = XFIXNUM (max_costs),
     .time_limit = time_limit,
-    .early_abort_tests = 0
   };
   memclear (ctx.deletions, del_bytes);
   memclear (ctx.insertions, ins_bytes);
 
   /* compareseq requires indices to be zero-based.  We add BEGV back
      later.  */
-  bool early_abort = compareseq (0, size_a, 0, size_b, false, &ctx);
+  bool early_abort;
+  if (! sys_setjmp (ctx.jmp))
+    early_abort = compareseq (0, size_a, 0, size_b, false, &ctx);
+  else
+    early_abort = true;
 
   if (early_abort)
     {
@@ -2046,8 +2047,6 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
       return Qnil;
     }
 
-  rbc_quitcounter = 0;
-
   Fundo_boundary ();
   bool modification_hooks_inhibited = false;
   record_unwind_protect_excursion ();
@@ -2071,8 +2070,7 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
      walk backwards, we don’t have to keep the positions in sync.  */
   while (i >= 0 || j >= 0)
     {
-      /* Allow the user to quit if this gets too slow.  */
-      rarely_quit (++rbc_quitcounter);
+      rarely_quit (++ctx.quitcounter);
 
       /* Check whether there is a change (insertion or deletion)
          before the current position.  */
@@ -2087,8 +2085,6 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
 	  while (j > 0 && bit_is_set (ctx.insertions, j - 1))
             --j;
 
-	  rarely_quit (rbc_quitcounter++);
-
           ptrdiff_t beg_a = min_a + i;
           ptrdiff_t beg_b = min_b + j;
           eassert (beg_a <= end_a);
@@ -2108,7 +2104,6 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
     }
 
   SAFE_FREE_UNBIND_TO (count, Qnil);
-  rbc_quitcounter = 0;
 
   if (modification_hooks_inhibited)
     {
@@ -2155,12 +2150,16 @@ bit_is_set (const unsigned char *a, ptrdiff_t i)
 buffer_chars_equal (struct context *ctx,
                     ptrdiff_t pos_a, ptrdiff_t pos_b)
 {
+  if (!++ctx->quitcounter)
+    {
+      maybe_quit ();
+      if (compareseq_early_abort (ctx))
+	sys_longjmp (ctx->jmp, 1);
+    }
+
   pos_a += ctx->beg_a;
   pos_b += ctx->beg_b;
 
-  /* Allow the user to escape out of a slow compareseq call.  */
-  rarely_quit (++rbc_quitcounter);
-
   ptrdiff_t bpos_a =
     ctx->a_unibyte ? pos_a : buf_charpos_to_bytepos (ctx->buffer_a, pos_a);
   ptrdiff_t bpos_b =
-- 
2.17.1

>From e0345b4e86154f42f47a9f7bbbf458a72bf5c06d Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 24 Aug 2020 13:12:51 -0700
Subject: [PATCH 2/2] replace-buffer-contents cleanups

* src/editfns.c (NOTE_DELETE, NOTE_INSERT): Avoid unnecessary parens.
(Freplace_buffer_contents): Check args before returning results.
Avoid integer overflow when computing too_expensive, and work even
if MAX-COSTS is bignum.  Call alloca and/or malloc just once, not
three times.
(set_bit, bit_is_set): Simplify micro-optimization by using eassume.
---
 src/editfns.c | 90 ++++++++++++++++++++++++++-------------------------
 1 file changed, 46 insertions(+), 44 deletions(-)

diff --git a/src/editfns.c b/src/editfns.c
index a5368c59da..7e1e24ef16 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -1900,8 +1900,8 @@ #define EXTRA_CONTEXT_FIELDS                    \
   sys_jmp_buf jmp;				\
   unsigned short quitcounter;
 
-#define NOTE_DELETE(ctx, xoff) set_bit ((ctx)->deletions, (xoff))
-#define NOTE_INSERT(ctx, yoff) set_bit ((ctx)->insertions, (yoff))
+#define NOTE_DELETE(ctx, xoff) set_bit ((ctx)->deletions, xoff)
+#define NOTE_INSERT(ctx, yoff) set_bit ((ctx)->insertions, yoff)
 #define EARLY_ABORT(ctx) compareseq_early_abort (ctx)
 
 struct context;
@@ -1954,6 +1954,28 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
   if (a == b)
     error ("Cannot replace a buffer with itself");
 
+  ptrdiff_t too_expensive;
+  if (NILP (max_costs))
+    too_expensive = 1000000;
+  else if (FIXNUMP (max_costs))
+    too_expensive = clip_to_bounds (0, XFIXNUM (max_costs), PTRDIFF_MAX);
+  else
+    {
+      CHECK_INTEGER (max_costs);
+      too_expensive = NILP (Fnatnump (max_costs)) ? 0 : PTRDIFF_MAX;
+    }
+
+  struct timespec time_limit = make_timespec (0, -1);
+  if (!NILP (max_secs))
+    {
+      struct timespec
+	tlim = timespec_add (current_timespec (),
+			     lisp_time_argument (max_secs)),
+	tmax = make_timespec (TYPE_MAXIMUM (time_t), TIMESPEC_HZ - 1);
+      if (timespec_cmp (tlim, tmax) < 0)
+	time_limit = tlim;
+    }
+
   ptrdiff_t min_a = BEGV;
   ptrdiff_t min_b = BUF_BEGV (b);
   ptrdiff_t size_a = ZV - min_a;
@@ -1983,36 +2005,24 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
 
   ptrdiff_t count = SPECPDL_INDEX ();
 
-  /* FIXME: It is not documented how to initialize the contents of the
-     context structure.  This code cargo-cults from the existing
-     caller in src/analyze.c of GNU Diffutils, which appears to
-     work.  */
 
   ptrdiff_t diags = size_a + size_b + 3;
+  ptrdiff_t del_bytes = size_a / CHAR_BIT + 1;
+  ptrdiff_t ins_bytes = size_b / CHAR_BIT + 1;
   ptrdiff_t *buffer;
+  ptrdiff_t bytes_needed;
+  if (INT_MULTIPLY_WRAPV (diags, 2 * sizeof *buffer, &bytes_needed)
+      || INT_ADD_WRAPV (del_bytes + ins_bytes, bytes_needed, &bytes_needed))
+    memory_full (SIZE_MAX);
   USE_SAFE_ALLOCA;
-  SAFE_NALLOCA (buffer, 2, diags);
+  buffer = SAFE_ALLOCA (bytes_needed);
+  unsigned char *deletions_insertions = memset (buffer + 2 * diags, 0,
+						del_bytes + ins_bytes);
 
-  if (NILP (max_costs))
-    XSETFASTINT (max_costs, 1000000);
-  else
-    CHECK_FIXNUM (max_costs);
-
-  struct timespec time_limit = make_timespec (0, -1);
-  if (!NILP (max_secs))
-    {
-      struct timespec
-	tlim = timespec_add (current_timespec (),
-			     lisp_time_argument (max_secs)),
-	tmax = make_timespec (TYPE_MAXIMUM (time_t), TIMESPEC_HZ - 1);
-      if (timespec_cmp (tlim, tmax) < 0)
-	time_limit = tlim;
-    }
-
-  /* Micro-optimization: Casting to size_t generates much better
-     code.  */
-  ptrdiff_t del_bytes = (size_t) size_a / CHAR_BIT + 1;
-  ptrdiff_t ins_bytes = (size_t) size_b / CHAR_BIT + 1;
+  /* FIXME: It is not documented how to initialize the contents of the
+     context structure.  This code cargo-cults from the existing
+     caller in src/analyze.c of GNU Diffutils, which appears to
+     work.  */
   struct context ctx = {
     .buffer_a = a,
     .buffer_b = b,
@@ -2020,16 +2030,14 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
     .beg_b = min_b,
     .a_unibyte = BUF_ZV (a) == BUF_ZV_BYTE (a),
     .b_unibyte = BUF_ZV (b) == BUF_ZV_BYTE (b),
-    .deletions = SAFE_ALLOCA (del_bytes),
-    .insertions = SAFE_ALLOCA (ins_bytes),
+    .deletions = deletions_insertions,
+    .insertions = deletions_insertions + del_bytes,
     .fdiag = buffer + size_b + 1,
     .bdiag = buffer + diags + size_b + 1,
     .heuristic = true,
-    .too_expensive = XFIXNUM (max_costs),
+    .too_expensive = too_expensive,
     .time_limit = time_limit,
   };
-  memclear (ctx.deletions, del_bytes);
-  memclear (ctx.insertions, ins_bytes);
 
   /* compareseq requires indices to be zero-based.  We add BEGV back
      later.  */
@@ -2074,8 +2082,8 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
 
       /* Check whether there is a change (insertion or deletion)
          before the current position.  */
-      if ((i > 0 && bit_is_set (ctx.deletions, i - 1)) ||
-          (j > 0 && bit_is_set (ctx.insertions, j - 1)))
+      if ((i > 0 && bit_is_set (ctx.deletions, i - 1))
+	  || (j > 0 && bit_is_set (ctx.insertions, j - 1)))
 	{
           ptrdiff_t end_a = min_a + i;
           ptrdiff_t end_b = min_b + j;
@@ -2117,21 +2125,15 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
 static void
 set_bit (unsigned char *a, ptrdiff_t i)
 {
-  eassert (i >= 0);
-  /* Micro-optimization: Casting to size_t generates much better
-     code.  */
-  size_t j = i;
-  a[j / CHAR_BIT] |= (1 << (j % CHAR_BIT));
+  eassume (0 <= i);
+  a[i / CHAR_BIT] |= (1 << (i % CHAR_BIT));
 }
 
 static bool
 bit_is_set (const unsigned char *a, ptrdiff_t i)
 {
-  eassert (i >= 0);
-  /* Micro-optimization: Casting to size_t generates much better
-     code.  */
-  size_t j = i;
-  return a[j / CHAR_BIT] & (1 << (j % CHAR_BIT));
+  eassume (0 <= i);
+  return a[i / CHAR_BIT] & (1 << (i % CHAR_BIT));
 }
 
 /* Return true if the characters at position POS_A of buffer
-- 
2.17.1