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

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Sheng Yang
`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: [hidden email]
E-mail(old): [hidden email]



Reply | Threaded
Open this post in threaded view
|

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

Sheng Yang
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 (old but still used): [hidden email]


Reply | Threaded
Open this post in threaded view
|

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

Stefan Kangas
"Sheng Yang" <[hidden email]> 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.



Reply | Threaded
Open this post in threaded view
|

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

Stefan Kangas
In reply to this post by Sheng Yang
"Sheng Yang" <[hidden email]> 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 <[hidden email]>
    Date:   Fri Nov 13 15:28:29 2020 +0100

        Don't show key ranges if shadowed by different commands

Thanks for the bug report!



Reply | Threaded
Open this post in threaded view
|

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

Sheng Yang
Any update on this bug?

On Fri, Jan 8, 2021, at 11:08, Stefan Kangas wrote:
"Sheng Yang" <[hidden email]> 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 <[hidden email]>
    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 (old but still used): [hidden email]


Reply | Threaded
Open this post in threaded view
|

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

Stefan Kangas
In reply to this post by Stefan Kangas
tags 45379 + patch
thanks

Stefan Kangas <[hidden email]> writes:

> "Sheng Yang" <[hidden email]> 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 <[hidden email]>
>     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.

0001-Fix-describe-buffer-bindings-performance-regression.patch (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Eli Zaretskii
> From: Stefan Kangas <[hidden email]>
> Date: Fri, 5 Mar 2021 20:44:33 -0800
> Cc: Juri Linkov <[hidden email]>, martin rudalics <[hidden email]>, Eli Zaretskii <[hidden email]>,
> [hidden email], Stefan Monnier <[hidden email]>,
> Stephen Berman <[hidden email]>
>
> 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.



Reply | Threaded
Open this post in threaded view
|

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

handa
In article <[hidden email]>, Eli Zaretskii <[hidden email]> writes:

> > From: Stefan Kangas <[hidden email]>
> > Date: Fri, 5 Mar 2021 20:44:33 -0800
> > Cc: Juri Linkov <[hidden email]>, martin rudalics <[hidden email]>, Eli Zaretskii <[hidden email]>,
> > [hidden email], Stefan Monnier <[hidden email]>,
> > Stephen Berman <[hidden email]>
> >
> > 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
[hidden email]



Reply | Threaded
Open this post in threaded view
|

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

Stefan Kangas
In reply to this post by Eli Zaretskii
Eli Zaretskii <[hidden email]> 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



Reply | Threaded
Open this post in threaded view
|

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

Eli Zaretskii
> From: Stefan Kangas <[hidden email]>
> Date: Sun, 7 Mar 2021 03:12:17 -0500
> Cc: [hidden email], [hidden email], [hidden email],
> [hidden email], [hidden email], [hidden email]
>
> > 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.



Reply | Threaded
Open this post in threaded view
|

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

Eli Zaretskii
In reply to this post by handa
Ping!  Kenichi, could you please help us with this issue?

> Date: Sun, 07 Mar 2021 08:15:10 +0200
> From: Eli Zaretskii <[hidden email]>
> Cc: [hidden email], [hidden email], [hidden email],
>  [hidden email], [hidden email], [hidden email], [hidden email]
>
> > From: handa <[hidden email]>
> > Cc: [hidden email], [hidden email], [hidden email], [hidden email],
> > [hidden email], [hidden email],
> > [hidden email], [hidden email]
> > Date: Sun, 07 Mar 2021 10:42:39 +0900
> >
> > In article <[hidden email]>, Eli Zaretskii <[hidden email]> writes:
> >
> > > > From: Stefan Kangas <[hidden email]>
> > > > Date: Fri, 5 Mar 2021 20:44:33 -0800
> > > > Cc: Juri Linkov <[hidden email]>, martin rudalics <[hidden email]>, Eli Zaretskii <[hidden email]>,
> > > > [hidden email], Stefan Monnier <[hidden email]>,
> > > > Stephen Berman <[hidden email]>
> > > >
> > > > 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 <[hidden email]>
> > AuthorDate: Fri Nov 13 15:28:29 2020 +0100
> > Commit:     Stefan Kangas <[hidden email]>
> > 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.



Reply | Threaded
Open this post in threaded view
|

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

handa
In article <[hidden email]>, Eli Zaretskii <[hidden email]> 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
[hidden email]



Reply | Threaded
Open this post in threaded view
|

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

Sheng Yang
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 <[hidden email]>, Eli Zaretskii <[hidden email]> 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


Sheng Yang(杨圣), PhD
Computer Science Department
University of Maryland, College Park
E-mail (old but still used): [hidden email]