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

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

[styang]

`describe-buffer-bindings` has become significantly slower since the
following commit

a649034336 * bad Don't show key ranges if shadowed by different commands

This also makes `describe-bindings` and anything depending on it hardly
usable. For me, it takes about 2 seconds on vanilla Emacs in an org-mode
buffer, and a few minutes on my Emacs configuration (was almost instant
before the offending commit).

-- 
Sheng Yang(杨圣), PhD student
Computer Science Department
University of Maryland, College Park
E-mail: styang@fastmail.com
E-mail(old): yangsheng6810@gmail.com

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

[Sheng Yang]

[-- Attachment #1: Type: text/plain, Size: 1086 bytes --]

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. Since I have received no reply after bug#45379 was reported (more than 2 weeks), I guess it's better to contact you and cc every participants of bug#5423. I am including the description of the bug report here for your convenience.

> `describe-buffer-bindings` has become significantly slower since the
following commit

a649034336 * bad Don't show key ranges if shadowed by different commands

This also makes `describe-bindings` and anything depending on it hardly
usable. For me, it takes about 2 seconds on vanilla Emacs in an org-mode
buffer, and a few minutes on my Emacs configuration (was almost instant
before the offending commit).
> 

Sheng Yang(杨圣), PhD candidate
Computer Science Department
University of Maryland, College Park
E-mail: styang@fastmail.com
E-mail (old but still used): yangsheng6810@gmail.com


[-- Attachment #2: Type: text/html, Size: 1677 bytes --]

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

[Stefan Kangas]

"Sheng Yang" <styang@fastmail.com> writes:

> Since I have received no reply after bug#45379 was reported (more than
> 2 weeks), I guess it's better to contact you and cc every participants
> of bug#5423.

Thanks for the ping.  I am working on a fix that I'm hoping to find the
time to finish up soon, possibly already this weekend.

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

[Stefan Kangas]

"Sheng Yang" <styang@fastmail.com> 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 <stefan@marxist.se>
    Date:   Fri Nov 13 15:28:29 2020 +0100

        Don't show key ranges if shadowed by different commands

Thanks for the bug report!

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

[Sheng Yang]

[-- Attachment #1: Type: text/plain, Size: 945 bytes --]

Any update on this bug? 

On Fri, Jan 8, 2021, at 11:08, Stefan Kangas wrote:
> "Sheng Yang" <styang@fastmail.com> 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 <stefan@marxist.se>
>     Date:   Fri Nov 13 15:28:29 2020 +0100
> 
>         Don't show key ranges if shadowed by different commands
> 
> Thanks for the bug report!
> 

Sheng Yang(杨圣), PhD candidate
Computer Science Department
University of Maryland, College Park
E-mail: styang@fastmail.com
E-mail (old but still used): yangsheng6810@gmail.com


[-- Attachment #2: Type: text/html, Size: 1918 bytes --]

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

[Stefan Kangas]

[-- Attachment #1: Type: text/plain, Size: 1168 bytes --]

tags 45379 + patch
thanks

Stefan Kangas <stefan@marxist.se> writes:

> "Sheng Yang" <styang@fastmail.com> 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 <stefan@marxist.se>
>     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.

[-- Attachment #2: 0001-Fix-describe-buffer-bindings-performance-regression.patch --]
[-- Type: text/x-diff, Size: 3876 bytes --]

From f95c75f1112c1aae0bd06a6753b60ce8a591d6e2 Mon Sep 17 00:00:00 2001
From: Stefan Kangas <stefan@marxist.se>
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

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

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Fri, 5 Mar 2021 20:44:33 -0800
> Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> 	Stephen Berman <stephen.berman@gmx.net>
> 
> 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 not sure I understand the reasons for each of the changes here.
char-tables are a tricky data structure, so I'd like to make sure this
change doesn't make our code subtly incorrect.

So could you please walk us through the proposed changes, adding
explanations for each part as you go?

(And what do char-tables have to do with describing key bindings,
btw?)

> 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.

AFAICT, you didn't CC Kenichi; I have now added him to the discussion.

Thanks.

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

[handa]

In article <83v9a4wve3.fsf@gnu.org>, Eli Zaretskii <eliz@gnu.org> writes:

> > From: Stefan Kangas <stefan@marxist.se>
> > Date: Fri, 5 Mar 2021 20:44:33 -0800
> > Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> > 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> > 	Stephen Berman <stephen.berman@gmx.net>
> > 
> > It turns out that we were doing unnecessary looping due to the above
> > mentioned commit.

Could you show me what is "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.

Is the patch for the above improvement the one included in the file
0001-Fix-describe-buffer-bindings-performance-regression.patch?

> > 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.

> AFAICT, you didn't CC Kenichi; I have now added him to the discussion.

It was more than 10 years ago that I last read keymap.c, and since then,
the code has been changed a lot.  It will take some time to understand
the latest code.

---
K. Handa
handa@gnu.org

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

[Eli Zaretskii]

> From: handa <handa@gnu.org>
> Cc: stefan@marxist.se, styang@fastmail.com, juri@linkov.net, rudalics@gmx.at,
> 	45379@debbugs.gnu.org, monnier@iro.umontreal.ca,
> 	stephen.berman@gmx.net, handa@gnu.org
> Date: Sun, 07 Mar 2021 10:42:39 +0900
> 
> In article <83v9a4wve3.fsf@gnu.org>, Eli Zaretskii <eliz@gnu.org> writes:
> 
> > > From: Stefan Kangas <stefan@marxist.se>
> > > Date: Fri, 5 Mar 2021 20:44:33 -0800
> > > Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> > > 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> > > 	Stephen Berman <stephen.berman@gmx.net>
> > > 
> > > It turns out that we were doing unnecessary looping due to the above
> > > mentioned commit.
> 
> Could you show me what is "the above mentioned commit"?

This one, I guess:

> commit a6490343366f2b2331a91dcb693effb3a9dd78f5
> Author:     Stefan Kangas <stefan@marxist.se>
> AuthorDate: Fri Nov 13 15:28:29 2020 +0100
> Commit:     Stefan Kangas <stefan@marxist.se>
> CommitDate: Sun Nov 22 02:45:03 2020 +0100
> 
>     Don't show key ranges if shadowed by different commands
> 
>     * src/keymap.c (describe_vector): Make sure found consecutive keys
>     are either not shadowed or, if they are, that they are shadowed by
>     the same command.  (Bug#9293)
>     * test/src/keymap-tests.el
>     (help--describe-vector/bug-9293-one-shadowed-in-range): New test.

> > >  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.
> 
> Is the patch for the above improvement the one included in the file
> 0001-Fix-describe-buffer-bindings-performance-regression.patch?

Yes, it is.

> > > 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.
> 
> > AFAICT, you didn't CC Kenichi; I have now added him to the discussion.
> 
> It was more than 10 years ago that I last read keymap.c, and since then,
> the code has been changed a lot.  It will take some time to understand
> the latest code.

Thanks in advance.

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

[Stefan Kangas]

Eli Zaretskii <eliz@gnu.org> writes:

>> 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 not sure I understand the reasons for each of the changes here.
> char-tables are a tricky data structure, so I'd like to make sure this
> change doesn't make our code subtly incorrect.

Thanks.

I have been struggling to come up with good unit tests, so any ideas
about that would also be very welcome.

> So could you please walk us through the proposed changes, adding
> explanations for each part as you go?

Yes.  Please allow for at least a couple of days to write this up.

> (And what do char-tables have to do with describing key bindings,
> btw?)

Full keymaps are char-tables, while sparse keymaps are just lists.

The call stack looks like this:

Fdescribe_buffer_bindings [keymap.c]
-> describe-map-tree      [help.el]
-> describe-map
-> Fhelp__describe_vector [keymap.c]
-> describe_vector

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

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Sun, 7 Mar 2021 03:12:17 -0500
> Cc: styang@fastmail.com, juri@linkov.net, rudalics@gmx.at, 
> 	45379@debbugs.gnu.org, monnier@iro.umontreal.ca, stephen.berman@gmx.net
> 
> > So could you please walk us through the proposed changes, adding
> > explanations for each part as you go?
> 
> Yes.  Please allow for at least a couple of days to write this up.

Sure.  There's no rush, please take your time.

> > (And what do char-tables have to do with describing key bindings,
> > btw?)
> 
> Full keymaps are char-tables, while sparse keymaps are just lists.
> 
> The call stack looks like this:
> 
> Fdescribe_buffer_bindings [keymap.c]
> -> describe-map-tree      [help.el]
> -> describe-map
> -> Fhelp__describe_vector [keymap.c]
> -> describe_vector

Got it, thanks.

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

[Eli Zaretskii]

Ping!  Kenichi, could you please help us with this issue?

> Date: Sun, 07 Mar 2021 08:15:10 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: stephen.berman@gmx.net, 45379@debbugs.gnu.org, stefan@marxist.se,
>  juri@linkov.net, handa@gnu.org, monnier@iro.umontreal.ca, styang@fastmail.com
> 
> > From: handa <handa@gnu.org>
> > Cc: stefan@marxist.se, styang@fastmail.com, juri@linkov.net, rudalics@gmx.at,
> > 	45379@debbugs.gnu.org, monnier@iro.umontreal.ca,
> > 	stephen.berman@gmx.net, handa@gnu.org
> > Date: Sun, 07 Mar 2021 10:42:39 +0900
> > 
> > In article <83v9a4wve3.fsf@gnu.org>, Eli Zaretskii <eliz@gnu.org> writes:
> > 
> > > > From: Stefan Kangas <stefan@marxist.se>
> > > > Date: Fri, 5 Mar 2021 20:44:33 -0800
> > > > Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> > > > 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> > > > 	Stephen Berman <stephen.berman@gmx.net>
> > > > 
> > > > It turns out that we were doing unnecessary looping due to the above
> > > > mentioned commit.
> > 
> > Could you show me what is "the above mentioned commit"?
> 
> This one, I guess:
> 
> > commit a6490343366f2b2331a91dcb693effb3a9dd78f5
> > Author:     Stefan Kangas <stefan@marxist.se>
> > AuthorDate: Fri Nov 13 15:28:29 2020 +0100
> > Commit:     Stefan Kangas <stefan@marxist.se>
> > CommitDate: Sun Nov 22 02:45:03 2020 +0100
> > 
> >     Don't show key ranges if shadowed by different commands
> > 
> >     * src/keymap.c (describe_vector): Make sure found consecutive keys
> >     are either not shadowed or, if they are, that they are shadowed by
> >     the same command.  (Bug#9293)
> >     * test/src/keymap-tests.el
> >     (help--describe-vector/bug-9293-one-shadowed-in-range): New test.
> 
> > > >  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.
> > 
> > Is the patch for the above improvement the one included in the file
> > 0001-Fix-describe-buffer-bindings-performance-regression.patch?
> 
> Yes, it is.
> 
> > > > 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.
> > 
> > > AFAICT, you didn't CC Kenichi; I have now added him to the discussion.
> > 
> > It was more than 10 years ago that I last read keymap.c, and since then,
> > the code has been changed a lot.  It will take some time to understand
> > the latest code.
> 
> Thanks in advance.

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

[handa]

In article <838s65ktvk.fsf@gnu.org>, Eli Zaretskii <eliz@gnu.org> writes:

> > > Is the patch for the above improvement the one included in the file
> > > 0001-Fix-describe-buffer-bindings-performance-regression.patch?
> > 
> > Yes, it is.

It seems that the main intention of that patch is to avoid unnecessary
call of char_table_ref_and_range introduced by the commit below:

> >     Don't show key ranges if shadowed by different commands
> > 
> >     * src/keymap.c (describe_vector): Make sure found consecutive keys
> >     are either not shadowed or, if they are, that they are shadowed by
> >     the same command.  (Bug#9293)

In describe_vector, if VECTOR is a char-table, char_table_ref_and_range
is already called at the fairly beginning of the main loop.  So, we do
not have to call it again, and thus, I think the patch is doing the
correct thing.

But, I don't know whether the following part in the patch is correct or
not.

+	  /* Ignore `self-insert-command' for performance.  */
+	  && !EQ (definition, Qself_insert_command))

---
K. Handa
handa@gnu.org

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

[Sheng Yang]

[-- Attachment #1: Type: text/plain, Size: 1565 bytes --]

Any update on this? Having been using the patch for a few weeks now, seems fine for me.

On Thu, Apr 1, 2021, at 10:06, handa wrote:
> In article <838s65ktvk.fsf@gnu.org <mailto:838s65ktvk.fsf%40gnu.org>>, Eli Zaretskii <eliz@gnu.org <mailto:eliz%40gnu.org>> writes:
> 
> > > > Is the patch for the above improvement the one included in the file
> > > > 0001-Fix-describe-buffer-bindings-performance-regression.patch?
> > > 
> > > Yes, it is.
> 
> It seems that the main intention of that patch is to avoid unnecessary
> call of char_table_ref_and_range introduced by the commit below:
> 
> > >     Don't show key ranges if shadowed by different commands
> > > 
> > >     * src/keymap.c (describe_vector): Make sure found consecutive keys
> > >     are either not shadowed or, if they are, that they are shadowed by
> > >     the same command.  (Bug#9293)
> 
> In describe_vector, if VECTOR is a char-table, char_table_ref_and_range
> is already called at the fairly beginning of the main loop.  So, we do
> not have to call it again, and thus, I think the patch is doing the
> correct thing.
> 
> But, I don't know whether the following part in the patch is correct or
> not.
> 
> +   /* Ignore `self-insert-command' for performance.  */
> +   && !EQ (definition, Qself_insert_command))
> 
> ---
> K. Handa
> handa@gnu.org <mailto:handa%40gnu.org>
> 

Sheng Yang(杨圣), PhD
Computer Science Department
University of Maryland, College Park
E-mail: styang@fastmail.com
E-mail (old but still used): yangsheng6810@gmail.com


[-- Attachment #2: Type: text/html, Size: 2694 bytes --]

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

[Stefan Kangas]

I finally had time/energy to look into this again!  Sorry for taking
more time than expected.

handa <handa@gnu.org> writes:

> In article <838s65ktvk.fsf@gnu.org>, Eli Zaretskii <eliz@gnu.org> writes:
>
>> > > Is the patch for the above improvement the one included in the file
>> > > 0001-Fix-describe-buffer-bindings-performance-regression.patch?
>> >
>> > Yes, it is.
>
> It seems that the main intention of that patch is to avoid unnecessary
> call of char_table_ref_and_range introduced by the commit below:
>
>> >     Don't show key ranges if shadowed by different commands
>> >
>> >     * src/keymap.c (describe_vector): Make sure found consecutive keys
>> >     are either not shadowed or, if they are, that they are shadowed by
>> >     the same command.  (Bug#9293)
>
> In describe_vector, if VECTOR is a char-table, char_table_ref_and_range
> is already called at the fairly beginning of the main loop.  So, we do
> not have to call it again, and thus, I think the patch is doing the
> correct thing.

Yes, this is all correct.

> But, I don't know whether the following part in the patch is correct or
> not.
>
> +	  /* Ignore `self-insert-command' for performance.  */
> +	  && !EQ (definition, Qself_insert_command))

(This is explained below.)

Eli Zaretskii <eliz@gnu.org> writes:

> I'm not sure I understand the reasons for each of the changes here.
> char-tables are a tricky data structure, so I'd like to make sure this
> change doesn't make our code subtly incorrect.
>
> So could you please walk us through the proposed changes, adding
> explanations for each part as you go?

This code is a bit complicated, so please bare with me if I am going
into too much detail.  BTW, note that I have also carried out a lot of
testing to see that my change does the same thing as before, only faster
(unfortunately it has been harder to come up with useful automated tests
beyond the ones we already have).

First, it might help to think of this as consisting of two parts:

1. A cleanup of the boundary condition check.  It is simply to make this
   code a bit more clear and easier to follow.

2. The actual bug fix for the performance bug.

I put a divider in between these two parts to make things hopefully a
bit more clear.

Stefan Kangas <stefan@marxist.se> writes:

> From f95c75f1112c1aae0bd06a6753b60ce8a591d6e2 Mon Sep 17 00:00:00 2001
> From: Stefan Kangas <stefan@marxist.se>
> 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;

The "from" variable is initialized to 0 below and is redundant.  So it
is replaced with the constant 0, which I think makes the intention of
this code more clear.  IOW, this is just a cleanup.

> +  /* 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);

The above puts a "boundary" that we need to handle below by stopping
(skipping to the next range) when we reach "stop".

We must end the loop altogether only when we reach "to".

Note that for char tables stop != to, otherwise stop == to

>
> -  for (int i = from; ; i++)
> +  for (int i = 0; i < to; i++)
>      {

Here we stop when we reach "to", which is what we intend.

The "from" mentioned above is also here replaced with constant 0.

>        bool this_shadowed = false;
>        Lisp_Object shadowed_by = Qnil;
> -      int range_beg, range_end;
> +      int range_beg;

[range_end is now unused and so removed.]

>        Lisp_Object val, tem2;
>
>        maybe_quit ();
>
> -      if (i == stop)
> -	{
> -	  if (i == to)
> -	    break;

This is a bit complicated to follow, so I have cleaned it up.

What happens here is that we exit the loop if "i == to".

The rest is to handle the above "boundary".  We have two cases:

1. If this is not a char table:

    i == stop  implies that  i == to

   (The loop will always end here.)

2. If this is a char table:

   i == stop   does not imply that   i == to

  a) The loop will end if

   i == stop  ∧  i == to

   (This can never be the case the first time we reach this, see above.
   We must first have reached the 2b) immediately below in a previous
   iteration.)

> -	  stop = to;
> -	}
> -

  b) Otherwise, if "i == stop ∧ i != to", we set "stop = to"

   (Again, only when this has happened can we reach 2a.)

But this is all removed, so the 2b) action is moved here:

>        int starting_i = i;
>
>        if (CHAR_TABLE_P (vector))
>  	{
> +	  /* Take care of the boundary.  */
> +	  if (i == stop)
> +	    stop = to;

IOW, here "i != to", but "i == stop" so we set "stop = to".  Just as
before.

Thus, the boundary condition is handled.

————————————– End part 1, performance bug fix follows:

> +	  /* 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);
                ^^^^^^^^^^^^^^^^^^^^^^^^

First call to "char_table_ref_and_range".

This puts the correct values in the "range_beg" variables and "i", where
"range_beg" is the start of the range and "i" is the last item in the
range that has the same value.

This is followed by:

>	}
>      else
>	val = AREF (vector, i);
>      Lisp_Object definition = get_keyelt (val, 0);
>
>      if (NILP (definition)) continue;

IOW, we skip it if it is not defined.

This is important to see why we can remove the next part.

> @@ -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),
                         ^^^^^^^^^^^^^^^^^^^^^^^^

This second call simply tries to call up a *second* range within the
same iteration.  This is to "put a boundary" (commit bed6185fecbb), but
it is crucial to note this is _already handled_ above.

This is therefore superfluous, as we can see from what happens next:

> -		   tem2 = get_keyelt (val, 0),
> -		   !NILP (tem2))
> -		 && !NILP (Fequal (tem2, definition)))
> -	    i = range_end;

This is all just to continue advancing down the char table until we find
something.  Again, note that above we already do exactly the same thing,
so doing it here as well is superfluous.

I.e. compare these statements to the lines above, specifically:

    Lisp_Object definition = get_keyelt (val, 0);
    if (NILP (definition)) continue;

Pay particular attention to the variables i, range_beg, and range_end.

> -	}
> -      else
> +	 definition.  */
> +      if (!CHAR_TABLE_P (vector))
>  	while (i + 1 < stop
>  	       && (tem2 = get_keyelt (AREF (vector, i + 1), 0),
>  		   !NILP (tem2))

(Note that there is no change if this is not a char-table.)

> @@ -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))
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

To see if the shadowing is the same for an entire range, we need to run
shadow_lookup() for *once for each character* in that range to see if
they are shadowed.  This is expensive.

One observation is that we often have *very long* ranges of characters
where the value is "self-insert-command", as in:

    (lookup-key global-map "文")

This is because a char-table will cover the range of all valid character
codes.  [Note again that we use a char-table only if the keymap is
defined with `make-keymap' (as opposed to `make-sparse-keymap', which is
just a list)]

Let's just assume that it is unlikely that there is any shadowing going
on for all of these self-inserting keys.  If there is shadowing going
on, we are probably not looking at a keymap where we have the default
value is set to self-insert-command.

So we basically say here: let's just not care about
`self-insert-command' and skip the check.  Yes, we will in theory not
get a perfect result, as there will be some cases where we miss the
shadowing.  OTOH, we are sure to have something that is not very slow.
(And in any case, I don't know of any examples where this will fail, and
if they exist we will in any case already be doing better than Emacs 27,
as this entire check is new in Emacs 28.)

>  	{
>  	  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++)
                       ^^^^^^^^^^

("range_beg" is the start of the actual range here, previously it was
starting_i due to the second call to char_table_ref_and_range.)

>  	    {
>  	      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

Phew!

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

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Tue, 4 May 2021 18:31:10 -0500
> Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> 	Stephen Berman <stephen.berman@gmx.net>, Kenichi Handa <handa@gnu.org>
> 
> I finally had time/energy to look into this again!  Sorry for taking
> more time than expected.

Thanks for your time and efforts.  I will review this as soon as I
have enough time to do so.

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

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Tue, 4 May 2021 18:31:10 -0500
> Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> 	Stephen Berman <stephen.berman@gmx.net>, Kenichi Handa <handa@gnu.org>
> 
> I finally had time/energy to look into this again!  Sorry for taking
> more time than expected.

Thanks.  And I have finally found enough free time to review this.  A
couple of comments below, and then I'm okay with installing these
changes.

> > But, I don't know whether the following part in the patch is correct or
> > not.
> >
> > +	  /* Ignore `self-insert-command' for performance.  */
> > +	  && !EQ (definition, Qself_insert_command))
> 
> (This is explained below.)

And I have a comment for that explanation.

> >        Lisp_Object val, tem2;
> >
> >        maybe_quit ();
> >
> > -      if (i == stop)
> > -	{
> > -	  if (i == to)
> > -	    break;
> 
> This is a bit complicated to follow, so I have cleaned it up.

I don't see the modified code regarding this to/stop issue as more
clear than the original one.  In both cases there's a special test
which then sets stop = to.  I needed to read the new code several
times to convince myself we perform the same amount of run-time tests
inside the loop.  So I'd prefer to leave this nit alone, as it was in
the original code.  If you find that somewhat unclear, how about
adding a comment there explaining whatever it was unclear to you when
you first read that?

> > @@ -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))
>               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> To see if the shadowing is the same for an entire range, we need to run
> shadow_lookup() for *once for each character* in that range to see if
> they are shadowed.  This is expensive.
> 
> One observation is that we often have *very long* ranges of characters
> where the value is "self-insert-command", as in:
> 
>     (lookup-key global-map "文")
> 
> This is because a char-table will cover the range of all valid character
> codes.  [Note again that we use a char-table only if the keymap is
> defined with `make-keymap' (as opposed to `make-sparse-keymap', which is
> just a list)]
> 
> Let's just assume that it is unlikely that there is any shadowing going
> on for all of these self-inserting keys.  If there is shadowing going
> on, we are probably not looking at a keymap where we have the default
> value is set to self-insert-command.
> 
> So we basically say here: let's just not care about
> `self-insert-command' and skip the check.  Yes, we will in theory not
> get a perfect result, as there will be some cases where we miss the
> shadowing.  OTOH, we are sure to have something that is not very slow.
> (And in any case, I don't know of any examples where this will fail, and
> if they exist we will in any case already be doing better than Emacs 27,
> as this entire check is new in Emacs 28.)

To tell the truth, I'm a bit worried by this "assumption", and so was
Handa-san.  This part of the change looks to me like simply ignoring a
legitimate situation which we previously supported, and now will not,
for the sole reason that the test is slow.  Who can tell us what this
could cause in some code somewhere in the community?  "Don't know any
examples where it will fail" is not very assuring, IMO.

Is this part of the change what speeds up describe-buffer-bindings?
Or is this just part of the speedup?  In the latter case, how much
faster will describe-buffer-bindings become without this
"optimization"?  And in the former case, I'd prefer to have this
"optimization" controllable by some variable, which we could then use
in the future as a "fire escape" if someone comes up with a use case
where the code you want to remove is indeed needed.

Alternatively, how about making the "Don't show key ranges if shadowed
by different commands" feature, which triggered this regression,
optional, by default off?  Then people who want it could be warned
that it might slow down describe-buffer-bindings, and will have to
decide whether they care enough about the speed to have the feature
turned on.

In any case, at least some of this explanation should be in comments
to the code, no matter whether we leave it alone or bypass it
conditionally.  If we introduce a variable to control this, some of
this should be in the doc string of that variable.

Thanks again for working on this, and sorry it took me so long to get
to review it.

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

[Sheng Yang]

[-- Attachment #1: Type: text/plain, Size: 288 bytes --]

A month has passed, any update on this? I see someone also reported this issue on the mailing list today.


Sheng Yang(杨圣), PhD
Computer Science Department
University of Maryland, College Park
E-mail: styang@fastmail.com
E-mail (old but still used): yangsheng6810@gmail.com


[-- Attachment #2: Type: text/html, Size: 816 bytes --]

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

[Eli Zaretskii]

> Date: Sat, 26 Jun 2021 16:51:19 -0500
> From: "Sheng Yang" <styang@fastmail.com>
> Cc: "Juri Linkov" <juri@linkov.net>, "martin rudalics" <rudalics@gmx.at>,
>  45379@debbugs.gnu.org, "Stefan Monnier" <monnier@iro.umontreal.ca>,
>  "Stephen Berman" <stephen.berman@gmx.net>, handa <handa@gnu.org>
> 
> A month has passed, any update on this? I see someone also reported this issue on the mailing list today.

Not yet, sorry.  I guess Stefan has other things on his plate.

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

[Eli Zaretskii]

Ping!  Stefan, can we please resolve this issue?  I think we cannot
release Emacs 28 without fixing this regression.

TIA

> Date: Thu, 13 May 2021 13:10:38 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: juri@linkov.net, styang@fastmail.com, handa@gnu.org, stephen.berman@gmx.net,
>  rudalics@gmx.at, monnier@iro.umontreal.ca, 45379@debbugs.gnu.org
> 
> > From: Stefan Kangas <stefan@marxist.se>
> > Date: Tue, 4 May 2021 18:31:10 -0500
> > Cc: Juri Linkov <juri@linkov.net>, martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>, 
> > 	45379@debbugs.gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, 
> > 	Stephen Berman <stephen.berman@gmx.net>, Kenichi Handa <handa@gnu.org>
> > 
> > I finally had time/energy to look into this again!  Sorry for taking
> > more time than expected.
> 
> Thanks.  And I have finally found enough free time to review this.  A
> couple of comments below, and then I'm okay with installing these
> changes.
> 
> > > But, I don't know whether the following part in the patch is correct or
> > > not.
> > >
> > > +	  /* Ignore `self-insert-command' for performance.  */
> > > +	  && !EQ (definition, Qself_insert_command))
> > 
> > (This is explained below.)
> 
> And I have a comment for that explanation.
> 
> > >        Lisp_Object val, tem2;
> > >
> > >        maybe_quit ();
> > >
> > > -      if (i == stop)
> > > -	{
> > > -	  if (i == to)
> > > -	    break;
> > 
> > This is a bit complicated to follow, so I have cleaned it up.
> 
> I don't see the modified code regarding this to/stop issue as more
> clear than the original one.  In both cases there's a special test
> which then sets stop = to.  I needed to read the new code several
> times to convince myself we perform the same amount of run-time tests
> inside the loop.  So I'd prefer to leave this nit alone, as it was in
> the original code.  If you find that somewhat unclear, how about
> adding a comment there explaining whatever it was unclear to you when
> you first read that?
> 
> > > @@ -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))
> >               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > To see if the shadowing is the same for an entire range, we need to run
> > shadow_lookup() for *once for each character* in that range to see if
> > they are shadowed.  This is expensive.
> > 
> > One observation is that we often have *very long* ranges of characters
> > where the value is "self-insert-command", as in:
> > 
> >     (lookup-key global-map "文")
> > 
> > This is because a char-table will cover the range of all valid character
> > codes.  [Note again that we use a char-table only if the keymap is
> > defined with `make-keymap' (as opposed to `make-sparse-keymap', which is
> > just a list)]
> > 
> > Let's just assume that it is unlikely that there is any shadowing going
> > on for all of these self-inserting keys.  If there is shadowing going
> > on, we are probably not looking at a keymap where we have the default
> > value is set to self-insert-command.
> > 
> > So we basically say here: let's just not care about
> > `self-insert-command' and skip the check.  Yes, we will in theory not
> > get a perfect result, as there will be some cases where we miss the
> > shadowing.  OTOH, we are sure to have something that is not very slow.
> > (And in any case, I don't know of any examples where this will fail, and
> > if they exist we will in any case already be doing better than Emacs 27,
> > as this entire check is new in Emacs 28.)
> 
> To tell the truth, I'm a bit worried by this "assumption", and so was
> Handa-san.  This part of the change looks to me like simply ignoring a
> legitimate situation which we previously supported, and now will not,
> for the sole reason that the test is slow.  Who can tell us what this
> could cause in some code somewhere in the community?  "Don't know any
> examples where it will fail" is not very assuring, IMO.
> 
> Is this part of the change what speeds up describe-buffer-bindings?
> Or is this just part of the speedup?  In the latter case, how much
> faster will describe-buffer-bindings become without this
> "optimization"?  And in the former case, I'd prefer to have this
> "optimization" controllable by some variable, which we could then use
> in the future as a "fire escape" if someone comes up with a use case
> where the code you want to remove is indeed needed.
> 
> Alternatively, how about making the "Don't show key ranges if shadowed
> by different commands" feature, which triggered this regression,
> optional, by default off?  Then people who want it could be warned
> that it might slow down describe-buffer-bindings, and will have to
> decide whether they care enough about the speed to have the feature
> turned on.
> 
> In any case, at least some of this explanation should be in comments
> to the code, no matter whether we leave it alone or bypass it
> conditionally.  If we introduce a variable to control this, some of
> this should be in the doc string of that variable.
> 
> Thanks again for working on this, and sorry it took me so long to get
> to review it.
> 
> 
> 
> 

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

[Eli Zaretskii]

> Date: Tue, 07 Sep 2021 21:53:16 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: stephen.berman@gmx.net, handa@gnu.org, juri@linkov.net, styang@fastmail.com,
>  monnier@iro.umontreal.ca, 45379@debbugs.gnu.org
> 
> Ping!  Stefan, can we please resolve this issue?  I think we cannot
> release Emacs 28 without fixing this regression.

Since we are close to cutting the emacs-28 release branch, and this
bug didn't see any loving care for a long time, I went ahead and fixed
this performance degradation myself, based on patches by Stefan Kangas
and their discussions in this bug report.

The feature whereby we check whether shadowing of consecutive keys is
by the same command, which AFAIU is what caused the regression, is now
optional, by default off.  There's a new variable,
'describe-bindings-check-shadowing-in-ranges', which can be used to
turn it on, and an optional value of that variable,
'ignore-self-insert', which provides some partial testing of shadowing
in these cases by trading accuracy for performance.  I also left alone
parts of the code where Stefan proposed changes of stylistic
character.

And I have a question about this whole "shadowing detection" feature.
If I repeat the recipe of bug#9293, which started all this, i.e.

  emacs -Q
  C-x C-f some-tarball-file.tar.gz RET
  M-x view-mode RET
  C-h m

then the *Help* buffer shows this at its start:

  key             binding
  ---             -------

  0 .. 9	digit-argument
  e		tar-extract  (currently shadowed by ‘View-exit’)
  f		tar-extract

  C-d		tar-flag-deleted
  RET		tar-extract
    (this binding is currently shadowed)
  C-n		tar-next-line
  C-p		tar-previous-line
  SPC		tar-next-line
    (this binding is currently shadowed)
  C		tar-copy
    (this binding is currently shadowed)

Note how the shadowing of 'e' is described with the command that
shadows it, but the shadowing of RET, SPC, and 'C' isn't.  Why is
that?  Is that a separate bug?  (This display was there even before my
changes, so I don't think the latest changes were the culprit; but for
some reason bug#9293 discussed only a small part of the *Help* display
and never looked beyond that.)

Thanks.

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

[Stefan Kangas]

Eli Zaretskii <eliz@gnu.org> writes:

>> Date: Tue, 07 Sep 2021 21:53:16 +0300
>> From: Eli Zaretskii <eliz@gnu.org>
>> Cc: stephen.berman@gmx.net, handa@gnu.org, juri@linkov.net, styang@fastmail.com,
>>  monnier@iro.umontreal.ca, 45379@debbugs.gnu.org
>>
>> Ping!  Stefan, can we please resolve this issue?  I think we cannot
>> release Emacs 28 without fixing this regression.
>
> Since we are close to cutting the emacs-28 release branch, and this
> bug didn't see any loving care for a long time, I went ahead and fixed
> this performance degradation myself, based on patches by Stefan Kangas
> and their discussions in this bug report.

Thanks, I appreciate the help.

[I had intended to get to it this weekend based on your recent ping; for
 me this stuff (as opposed to ELisp shenanigans) requires a decent chunk
 of time to sit down and properly focus.]

> The feature whereby we check whether shadowing of consecutive keys is
> by the same command, which AFAIU is what caused the regression, is now
> optional, by default off.  There's a new variable,
> 'describe-bindings-check-shadowing-in-ranges', which can be used to
> turn it on, and an optional value of that variable,
> 'ignore-self-insert', which provides some partial testing of shadowing
> in these cases by trading accuracy for performance.

OK.  The bug doesn't directly affect me, but now people who are affected
can enable the bug fix.

> And I have a question about this whole "shadowing detection" feature.
> If I repeat the recipe of bug#9293, which started all this, i.e.
>
>   emacs -Q
>   C-x C-f some-tarball-file.tar.gz RET
>   M-x view-mode RET
>   C-h m
>
> then the *Help* buffer shows this at its start:
>
>   key             binding
>   ---             -------
>
>   0 .. 9	digit-argument
>   e		tar-extract  (currently shadowed by ‘View-exit’)
>   f		tar-extract
>
>   C-d		tar-flag-deleted
>   RET		tar-extract
>     (this binding is currently shadowed)
>   C-n		tar-next-line
>   C-p		tar-previous-line
>   SPC		tar-next-line
>     (this binding is currently shadowed)
>   C		tar-copy
>     (this binding is currently shadowed)
>
> Note how the shadowing of 'e' is described with the command that
> shadows it, but the shadowing of RET, SPC, and 'C' isn't.  Why is
> that?  Is that a separate bug?

It is a separate bug, I think.  The "currently shadowed part" is new in
commit fb9326b45c76, but it was never fixed for the second case.

Which of the two messages is shown has to do with whether or not this is
a regular keymap or a sparse keymap.  They were always handled slightly
differently, but now we have the changed message for one of them that
makes this visible.

> for some reason bug#9293 discussed only a small part of the *Help*
> display and never looked beyond that.

I overlooked the case you mention, indeed.

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

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Sat, 18 Sep 2021 05:34:08 -0700
> Cc: stephen.berman@gmx.net, handa@gnu.org, juri@linkov.net, 
> 	styang@fastmail.com, monnier@iro.umontreal.ca, 45379@debbugs.gnu.org, 
> 	Lars Ingebrigtsen <larsi@gnus.org>
> 
> >   key             binding
> >   ---             -------
> >
> >   0 .. 9	digit-argument
> >   e		tar-extract  (currently shadowed by ‘View-exit’)
> >   f		tar-extract
> >
> >   C-d		tar-flag-deleted
> >   RET		tar-extract
> >     (this binding is currently shadowed)
> >   C-n		tar-next-line
> >   C-p		tar-previous-line
> >   SPC		tar-next-line
> >     (this binding is currently shadowed)
> >   C		tar-copy
> >     (this binding is currently shadowed)
> >
> > Note how the shadowing of 'e' is described with the command that
> > shadows it, but the shadowing of RET, SPC, and 'C' isn't.  Why is
> > that?  Is that a separate bug?
> 
> It is a separate bug, I think.  The "currently shadowed part" is new in
> commit fb9326b45c76, but it was never fixed for the second case.

Then I guess we can close this bug?

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

[Stefan Kangas]

tags 45379 + fixed
close 45379 28.1
thanks

Eli Zaretskii <eliz@gnu.org> writes:

> Then I guess we can close this bug?

I think so, yes, so I'm doing that now.

If anyone is still seeing any issues related to this feel free to either
reply back or just open a new bug.