Subject: Re: bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings

From: Stefan Kangas <[email-masked]>
Date: Fri, 5 Mar 2021 20:44:33 -0800

tags 45379 + patch
thanks

Stefan Kangas <[email-masked]> writes:

> "Sheng Yang" <[email-masked]> writes:
>
>> Hi Juri,
>>
>> I recently came across a regression of performance in Emacs for
>> describe bindings, which I have reported as bug#45379. After
>> bisection, the offending seems to be a commit a649034336 you pushed in
>> November 2020, to fix bug#5423. [...]
>>
>> a649034336 * bad Don't show key ranges if shadowed by different commands
>
> BTW, the offending commit is not Juri's.  It is mine:
>
>     Author: Stefan Kangas <[email-masked]>
>     Date:   Fri Nov 13 15:28:29 2020 +0100
>
>         Don't show key ranges if shadowed by different commands

Please try the attached patch and see that it fixes this performance
regression.

It turns out that we were doing unnecessary looping due to the above
mentioned commit.  While working on this, I also found that we can get
rid of an unnecessary call to char_table_ref_and_range, which should
make this function run even faster.

I'm also copying in Kenichi Handa, who was the last to touch this code.
Handa-san, please let us know if you have any comments on this patch.
Thanks in advance.
From f95c75f1112c1aae0bd06a6753b60ce8a591d6e2 Mon Sep 17 00:00:00 2001
From: Stefan Kangas <[email-masked]>
Date: Sat, 6 Mar 2021 05:32:32 +0100
Subject: [PATCH] Fix describe-buffer-bindings performance regression

* src/keymap.c (describe_vector): Improve char-table performance by
removing an unnecessary loop.  (Bug#45379)
(syms_of_keymap) <Qself_insert_command>: New DEFSYM.
---
 src/keymap.c | 47 +++++++++++++++++++----------------------------
 1 file changed, 19 insertions(+), 28 deletions(-)

diff --git a/src/keymap.c b/src/keymap.c
index 782931fadf..c70df98a6e 100644
--- a/src/keymap.c
+++ b/src/keymap.c
@@ -2920,7 +2920,7 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
   Lisp_Object suppress = Qnil;
   bool first = true;
   /* Range of elements to be handled.  */
-  int from, to, stop;
+  int to, stop;
 
   if (!keymap_p)
     {
@@ -2940,32 +2940,33 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
   if (partial)
     suppress = intern ("suppress-keymap");
 
-  from = 0;
+  /* If VECTOR is a char-table, we had better put a boundary
+     between normal characters (-#x3FFF7F) and 8-bit characters
+     (#x3FFF80-).  */
   if (CHAR_TABLE_P (vector))
     stop = MAX_5_BYTE_CHAR + 1, to = MAX_CHAR + 1;
   else
     stop = to = ASIZE (vector);
 
-  for (int i = from; ; i++)
+  for (int i = 0; i < to; i++)
     {
       bool this_shadowed = false;
       Lisp_Object shadowed_by = Qnil;
-      int range_beg, range_end;
+      int range_beg;
       Lisp_Object val, tem2;
 
       maybe_quit ();
 
-      if (i == stop)
-	{
-	  if (i == to)
-	    break;
-	  stop = to;
-	}
-
       int starting_i = i;
 
       if (CHAR_TABLE_P (vector))
 	{
+	  /* Take care of the boundary.  */
+	  if (i == stop)
+	    stop = to;
+
+	  /* Find the first element between i and stop - 1.  Put its
+	     index in i.  */
 	  range_beg = i;
 	  i = stop - 1;
 	  val = char_table_ref_and_range (vector, range_beg, &range_beg, &i);
@@ -3024,21 +3025,8 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
       insert1 (Fkey_description (kludge, prefix));
 
       /* Find all consecutive characters or rows that have the same
-	 definition.  But, if VECTOR is a char-table, we had better
-	 put a boundary between normal characters (-#x3FFF7F) and
-	 8-bit characters (#x3FFF80-).  */
-      if (CHAR_TABLE_P (vector))
-	{
-	  while (i + 1 < stop
-		 && (range_beg = i + 1, range_end = stop - 1,
-		   val = char_table_ref_and_range (vector, range_beg,
-						   &range_beg, &range_end),
-		   tem2 = get_keyelt (val, 0),
-		   !NILP (tem2))
-		 && !NILP (Fequal (tem2, definition)))
-	    i = range_end;
-	}
-      else
+	 definition.  */
+      if (!CHAR_TABLE_P (vector))
 	while (i + 1 < stop
 	       && (tem2 = get_keyelt (AREF (vector, i + 1), 0),
 		   !NILP (tem2))
@@ -3047,10 +3035,12 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
 
       /* Make sure found consecutive keys are either not shadowed or,
 	 if they are, that they are shadowed by the same command.  */
-      if (CHAR_TABLE_P (vector) && i != starting_i)
+      if (CHAR_TABLE_P (vector) && i != starting_i
+	  /* Ignore `self-insert-command' for performance.  */
+	  && !EQ (definition, Qself_insert_command))
 	{
 	  Lisp_Object key = make_nil_vector (1);
-	  for (int j = starting_i + 1; j <= i; j++)
+	  for (int j = range_beg + 1; j <= i; j++)
 	    {
 	      ASET (key, 0, make_fixnum (j));
 	      Lisp_Object tem = shadow_lookup (shadow, key, Qt, 0);
@@ -3109,6 +3099,7 @@ syms_of_keymap (void)
   DEFSYM (Qdescribe_map_tree, "describe-map-tree");
 
   DEFSYM (Qkeymap_canonicalize, "keymap-canonicalize");
+  DEFSYM (Qself_insert_command, "self-insert-command");
 
   /* Now we are ready to set up this property, so we can
      create char tables.  */
-- 
2.30.1