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

[Eli Zaretskii <eliz@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.