bug#56682: Fix the long lines font locking related slowdowns

[Eli Zaretskii <eliz@gnu.org>]

> Date: Thu, 4 Aug 2022 04:08:20 +0300
> Cc: 56682@debbugs.gnu.org, gregory@heytings.org, monnier@iro.umontreal.ca
> From: Dmitry Gutov <dgutov@yandex.ru>
> 
> > Yes, but when thrashing causes delays of dozens of seconds, the result
> > is not just a rare delay, the result is simply unacceptable.
> 
> What is unacceptable is the behavior I see from the narrowing solution. 
> See the screenshots I attached in this thread.

So that behavior is unacceptable, but declaring we are unable to allow
editing of such files is acceptable?  If that is your position, we
will have to agree to disagree.  We have decided that we want a more
graceful degradation in these cases, and in particular to sacrifice
some accuracy of font-lock to allow reasonable editing of such files.
If you consider that unacceptable, you can still have the lockups you
prefer by setting long-line-threshold to nil.  But we disagree with
having nil be the default value of that variable.

> > We want every basic operation in such buffers to perform reasonably
> > well.  That's the goal of this activity.  Because partial solutions
> > that sometimes work we already have: there's so-long-mode, there's
> > longlines.el, and a couple of other trick up our sleeve.
> 
> We cannot perform every basic operation in fixed time for any 
> arbitrarily sized file. There are limits of what we can possibly do.

I said "reasonably well", not "in fixed time".  Some slowdown is
acceptable.  But when a simple editing operation takes several
minutes, we cannot in good faith claim that Emacs is still usable.  If
you prefer to have that to some degradation in font-lock, then we
disagree.

> If we narrow willy-nilly, we step on the toes of syntax parsing and get 
> other weird behaviors as a result.
> 
> Which means we got another partial solution.

The experience till now seems to indicate that the degradation caused
by this solution is much milder and rarer than any other solution, and
allows users to edit files with much longer lines.  It certainly
sounds like a better solution than completely disabling font-lock in
such buffers (but that is still an option, if someone prefers it).
Reporting specific problems with that solution will allow us to solve
at least some of them, with the goal of making the degradation even
more graceful -- this is what this bug report is for.

But if you want to claim that it is better to have Emacs lock up for
minutes in these cases, you will have to do that in your local
customization, because we disagree with having Emacs behave like that
when it can be avoided.

> so-long-mode, longlines, etc, were all targeted as buffers with long 
> lines. I'd really like it if we could scope this discussion to solving 
> that particular problem. Not the speed of operations in large files in 
> general.

The "long lines problem" is directly related to the speed of
operations.  We didn't yet make any changes that affect large files in
general, only files with long lines.  In those cases, the speed of
operations becomes unacceptably slow beyond some threshold, and we
want Emacs to remain usable beyond that threshold, even if that makes
fontifications sometimes inaccurate.

> The long lines problem is caused by pathologic complexity of some 
> operations (like O(N^2) of line length, I guess).

That assumption is incorrect, at least according to my analysis of the
relevant bottlenecks.  The slowdown is mostly linear in the number of
buffer positions redisplay and its subroutines need to traverse.

> syntax-ppss's performance is nothing like that: it's O(N) for
> initial full scan, and O(1) for most operations afterward.
> 
> You can't really get better than that. Maye get a better multiplier with 
> tree-sitter or a more optimized version of parse-partial-sexp, but take 
> a 10x bigger file (or 100x bigger, or 1000x bigger) - and voila, the 
> delay can be observed again.

No one denies that beyond some threshold the performance will be too
slow again.  We just want to make that threshold much farther.

In addition, the idea of using narrowing is a good one precisely
because it is unaffected by the buffer size.  So its effect doesn't
deteriorate when the buffer or the line length becomes larger.