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

[Dmitry Gutov]

On 02.08.2022 18:46, Eli Zaretskii wrote:
> > Date: Tue, 2 Aug 2022 17:10:53 +0300
> > Cc: 56682@debbugs.gnu.org, gregory@heytings.org, monnier@iro.umontreal.ca
> > From: Dmitry Gutov <dgutov@yandex.ru>
> >
> > On 02.08.2022 05:27, Eli Zaretskii wrote:
> > > > syntax-ppss cache is a list of checkpoints spread along the buffer.
> > > >
> > > > After a modification, only the checkpoints below it are invalidated (to
> > > > be recomputed on-demand later).
> > > So a suitably-concocted replace command will still invalidate a lot of
> > > that cache, right?
> >
> > For any cache, one can invent an operation that would result in
> > thrashing it repeatedly.
>
> 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.

> > A regular search-replace should work well enough, though. Because when
> > the buffer is long, the user is likely, on average, to spend a lot more
> > time examining the occurrences and deciding whether to replace each one.
> > And since the operation goes from top to bottom, this will likely
> > invalidate the list of caches once, and then rebuild it from the
> > beginning (or from wherever the first replacement was).
>
> 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.

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.

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 caused by pathologic complexity of some 
operations (like O(N^2) of line length, I guess). 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.