unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
@ 2020-12-23  6:01 styang
  2021-01-08 16:47 ` Sheng Yang
  0 siblings, 1 reply; 16+ messages in thread
From: styang @ 2020-12-23  6:01 UTC (permalink / raw)
  To: 45379

`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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2020-12-23  6:01 bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings styang
@ 2021-01-08 16:47 ` Sheng Yang
  2021-01-08 17:00   ` Stefan Kangas
  2021-01-08 17:08   ` Stefan Kangas
  0 siblings, 2 replies; 16+ messages in thread
From: Sheng Yang @ 2021-01-08 16:47 UTC (permalink / raw)
  To: Juri Linkov; +Cc: Stephen Berman, Stefan Kangas, Stefan Monnier, 45379

[-- 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 --]

^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-01-08 16:47 ` Sheng Yang
@ 2021-01-08 17:00   ` Stefan Kangas
  2021-01-08 17:08   ` Stefan Kangas
  1 sibling, 0 replies; 16+ messages in thread
From: Stefan Kangas @ 2021-01-08 17:00 UTC (permalink / raw)
  To: Sheng Yang, Juri Linkov; +Cc: 45379, Stefan Monnier, Stephen Berman

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-01-08 16:47 ` Sheng Yang
  2021-01-08 17:00   ` Stefan Kangas
@ 2021-01-08 17:08   ` Stefan Kangas
  2021-02-04 15:43     ` Sheng Yang
  2021-03-06  4:44     ` Stefan Kangas
  1 sibling, 2 replies; 16+ messages in thread
From: Stefan Kangas @ 2021-01-08 17:08 UTC (permalink / raw)
  To: Sheng Yang, Juri Linkov; +Cc: 45379, Stefan Monnier, Stephen Berman

"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!





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-01-08 17:08   ` Stefan Kangas
@ 2021-02-04 15:43     ` Sheng Yang
  2021-03-06  4:44     ` Stefan Kangas
  1 sibling, 0 replies; 16+ messages in thread
From: Sheng Yang @ 2021-02-04 15:43 UTC (permalink / raw)
  To: Stefan Kangas, Juri Linkov; +Cc: 45379, Stefan Monnier, Stephen Berman

[-- 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 --]

^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-01-08 17:08   ` Stefan Kangas
  2021-02-04 15:43     ` Sheng Yang
@ 2021-03-06  4:44     ` Stefan Kangas
  2021-03-06  8:15       ` Eli Zaretskii
  2021-05-04 23:31       ` Stefan Kangas
  1 sibling, 2 replies; 16+ messages in thread
From: Stefan Kangas @ 2021-03-06  4:44 UTC (permalink / raw)
  To: Sheng Yang; +Cc: Stephen Berman, Juri Linkov, Stefan Monnier, 45379

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


^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-06  4:44     ` Stefan Kangas
@ 2021-03-06  8:15       ` Eli Zaretskii
  2021-03-07  1:42         ` handa
  2021-03-07  8:12         ` Stefan Kangas
  2021-05-04 23:31       ` Stefan Kangas
  1 sibling, 2 replies; 16+ messages in thread
From: Eli Zaretskii @ 2021-03-06  8:15 UTC (permalink / raw)
  To: Stefan Kangas, Kenichi Handa; +Cc: juri, styang, stephen.berman, monnier, 45379

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-06  8:15       ` Eli Zaretskii
@ 2021-03-07  1:42         ` handa
  2021-03-07  6:15           ` Eli Zaretskii
  2021-03-07  8:12         ` Stefan Kangas
  1 sibling, 1 reply; 16+ messages in thread
From: handa @ 2021-03-07  1:42 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: stephen.berman, 45379, stefan, juri, handa, monnier, styang

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-07  1:42         ` handa
@ 2021-03-07  6:15           ` Eli Zaretskii
  2021-03-30  7:01             ` Eli Zaretskii
  0 siblings, 1 reply; 16+ messages in thread
From: Eli Zaretskii @ 2021-03-07  6:15 UTC (permalink / raw)
  To: handa; +Cc: stephen.berman, 45379, stefan, juri, handa, monnier, styang

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-06  8:15       ` Eli Zaretskii
  2021-03-07  1:42         ` handa
@ 2021-03-07  8:12         ` Stefan Kangas
  2021-03-07  8:38           ` Eli Zaretskii
  1 sibling, 1 reply; 16+ messages in thread
From: Stefan Kangas @ 2021-03-07  8:12 UTC (permalink / raw)
  To: Eli Zaretskii, Kenichi Handa; +Cc: juri, styang, stephen.berman, monnier, 45379

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-07  8:12         ` Stefan Kangas
@ 2021-03-07  8:38           ` Eli Zaretskii
  0 siblings, 0 replies; 16+ messages in thread
From: Eli Zaretskii @ 2021-03-07  8:38 UTC (permalink / raw)
  To: Stefan Kangas; +Cc: stephen.berman, 45379, juri, handa, monnier, styang

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-07  6:15           ` Eli Zaretskii
@ 2021-03-30  7:01             ` Eli Zaretskii
  2021-04-01 15:06               ` handa
  0 siblings, 1 reply; 16+ messages in thread
From: Eli Zaretskii @ 2021-03-30  7:01 UTC (permalink / raw)
  To: Kenichi Handa; +Cc: styang, 45379, stefan, juri, handa, monnier, stephen.berman

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.





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-30  7:01             ` Eli Zaretskii
@ 2021-04-01 15:06               ` handa
  2021-04-14  3:06                 ` Sheng Yang
  0 siblings, 1 reply; 16+ messages in thread
From: handa @ 2021-04-01 15:06 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: stephen.berman, stefan, juri, styang, monnier, 45379

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-04-01 15:06               ` handa
@ 2021-04-14  3:06                 ` Sheng Yang
  0 siblings, 0 replies; 16+ messages in thread
From: Sheng Yang @ 2021-04-14  3:06 UTC (permalink / raw)
  To: handa, Eli Zaretskii
  Cc: Juri Linkov, 45379, Stefan Kangas, Stefan Monnier, Stephen Berman

[-- 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 --]

^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-03-06  4:44     ` Stefan Kangas
  2021-03-06  8:15       ` Eli Zaretskii
@ 2021-05-04 23:31       ` Stefan Kangas
  2021-05-06 10:11         ` Eli Zaretskii
  1 sibling, 1 reply; 16+ messages in thread
From: Stefan Kangas @ 2021-05-04 23:31 UTC (permalink / raw)
  To: Sheng Yang
  Cc: 45379, Juri Linkov, Kenichi Handa, Stefan Monnier, Stephen Berman

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!





^ permalink raw reply	[flat|nested] 16+ messages in thread

* bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings
  2021-05-04 23:31       ` Stefan Kangas
@ 2021-05-06 10:11         ` Eli Zaretskii
  0 siblings, 0 replies; 16+ messages in thread
From: Eli Zaretskii @ 2021-05-06 10:11 UTC (permalink / raw)
  To: Stefan Kangas; +Cc: stephen.berman, 45379, juri, handa, monnier, styang

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





^ permalink raw reply	[flat|nested] 16+ messages in thread

end of thread, other threads:[~2021-05-06 10:11 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-12-23  6:01 bug#45379: 28.0.50; Degraded Performance of describe-buffer-bindings styang
2021-01-08 16:47 ` Sheng Yang
2021-01-08 17:00   ` Stefan Kangas
2021-01-08 17:08   ` Stefan Kangas
2021-02-04 15:43     ` Sheng Yang
2021-03-06  4:44     ` Stefan Kangas
2021-03-06  8:15       ` Eli Zaretskii
2021-03-07  1:42         ` handa
2021-03-07  6:15           ` Eli Zaretskii
2021-03-30  7:01             ` Eli Zaretskii
2021-04-01 15:06               ` handa
2021-04-14  3:06                 ` Sheng Yang
2021-03-07  8:12         ` Stefan Kangas
2021-03-07  8:38           ` Eli Zaretskii
2021-05-04 23:31       ` Stefan Kangas
2021-05-06 10:11         ` Eli Zaretskii

unofficial mirror of bug-gnu-emacs@gnu.org 

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://yhetil.org/emacs-bugs/0 emacs-bugs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 emacs-bugs emacs-bugs/ https://yhetil.org/emacs-bugs \
		bug-gnu-emacs@gnu.org
	public-inbox-index emacs-bugs

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.yhetil.org/yhetil.emacs.bugs
	nntp://news.gmane.io/gmane.emacs.bugs


code repositories for project(s) associated with this inbox:

	https://git.savannah.gnu.org/cgit/emacs.git

AGPL code for this site: git clone http://ou63pmih66umazou.onion/public-inbox.git