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

[Eli Zaretskii <eliz@gnu.org>]

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