A possible way for CC Mode to resolve its sluggishness

A possible way for CC Mode to resolve its sluggishness

[Alan Mackenzie]

Hello Emacs, CC Mode.

In the last few years there's been a continual stream of posts
complaining (always good naturedly) about the sluggishness of CC Mode
during extended buffer change operations, and sometimes even with single
operations (such as typing into a C++ raw string).

Recently, Zhang Haijun, noted that iedit-mode (a mode that performs
simultaneous edits on, say, all occurrences of a variable name
throughout a buffer) didn't work well in C++ Mode, because of the time
taken by its after-change-functions.

The problem is that CC Mode's before/after-change-functions are very
general, and scan the buffer looking for situations which only arise
sporadically.  Things like an open string getting closed, or a > being
inserted which needs to be checked for a template delimiter.  However,
these expensive checks are performed for _every_ buffer change.  Even
doing something like inserting a letter or a digit causes the full range
of tests to be performed.  This is not good.

To improve this, I propose that at a buffer change, simple fast
plausibility checks be performed before the change-functions get run,
and only where something complicated is afoot should (selected)
change-functions be run.  For example, inserting a letter or digit will
only rarely be complicated, inserting a brace or semicolon will usually
be so.

Now to the detailed proposal:
(i) A CC Mode buffer will be partitioned into @dfn{syntactic cells}.
These will be things like a section of code, a comment, a string, a raw
string, a CPP construct ....  Possibly even comment delimiters would
have their own cells.

(ii) Syntactic cells will be implemented by a text property, c-syntax,
whose value will indicate the type of the cell, and possibly an
identifier for it.  Neighbouring cells will always have distinct
c-syntax values.

(iii) On a buffer change which removes characters, we check for things
like:
  o - (beg end) straddling or touching cell borders;
  o - "structural" characters in (beg end) (say a brace or semicolon);
  o - "boundary" characters in (beg end) (say a comment or string
  delimiter);
  o - things happening with backslashes, etc.
If any of these things is true, we run the before-change-functions (or a
subset of them).  This will only happen every now and then.  When it
does, we will likely adjust the syntactic cells.

(iv) When a buffer change inserts characters, we check basically the
same things as in (iii) and if needed, run (a subset of) the
after-change-functions.  This also will only happen now and then, and
will like necessitate adjustment of the syntactic cells.

It will probably be possible to eliminate one or more existing CC Mode
structural caches - the speed of text property search (compared with
parse-partial-sexp from a cached "safe" position) will make this
possible.

Thoughts?

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: A possible way for CC Mode to resolve its sluggishness

[Eli Zaretskii]

> Date: Fri, 26 Apr 2019 19:30:56 +0000
> From: Alan Mackenzie <acm@muc.de>
> 
> (i) A CC Mode buffer will be partitioned into @dfn{syntactic cells}.
> These will be things like a section of code, a comment, a string, a raw
> string, a CPP construct ....  Possibly even comment delimiters would
> have their own cells.
> 
> (ii) Syntactic cells will be implemented by a text property, c-syntax,
> whose value will indicate the type of the cell, and possibly an
> identifier for it.  Neighbouring cells will always have distinct
> c-syntax values.

Can a syntactic cell have other syntactic cells embedded in it?
Because if it can, you cannot use text properties for that, since text
properties cannot overlap.

> Thoughts?

Why do you think this proposal will make CC Mode faster?  Wouldn't
computing and updating the cells in itself be expensive?

Re: A possible way for CC Mode to resolve its sluggishness

[Alan Mackenzie]

Hello, Eli.

On Fri, Apr 26, 2019 at 22:53:09 +0300, Eli Zaretskii wrote:
> > Date: Fri, 26 Apr 2019 19:30:56 +0000
> > From: Alan Mackenzie <acm@muc.de>

> > (i) A CC Mode buffer will be partitioned into @dfn{syntactic cells}.
> > These will be things like a section of code, a comment, a string, a raw
> > string, a CPP construct ....  Possibly even comment delimiters would
> > have their own cells.

> > (ii) Syntactic cells will be implemented by a text property, c-syntax,
> > whose value will indicate the type of the cell, and possibly an
> > identifier for it.  Neighbouring cells will always have distinct
> > c-syntax values.

> Can a syntactic cell have other syntactic cells embedded in it?

No.  Mainly because ....

> Because if it can, you cannot use text properties for that, since text
> properties cannot overlap.

Yes.

> > Thoughts?

> Why do you think this proposal will make CC Mode faster?  Wouldn't
> computing and updating the cells in itself be expensive?

The main speed up will come from only running CC Mode's change functions
occasionally, rather than at every buffer change.

For most changes, there will be no need explicitly to update the cells;
the text property stickiness, and so on, will do that implicitly.  When
there is a need, the cell boundaries will be calculated by existing
algorithms, but these will get run much less frequently.

For example c-fl-decl-start laboriously finds the start of the current
declaration, needed as a context for accurate font-locking.  The
syntactic cells will cache this value, rather than it having to be
continually calculated.  This function is one of the main brakes to CC
Mode's performance.

Also, there are currently a lot of calls to c-literal-limits and
friends, which use an explicit cache together with parse-partial-sexp.
Being able to use text property search instead should be a speedup.

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: A possible way for CC Mode to resolve its sluggishness

[Stefan Monnier]

> The problem is that CC Mode's before/after-change-functions are very
> general, and scan the buffer looking for situations which only arise
> sporadically.  Things like an open string getting closed, or a > being
> inserted which needs to be checked for a template delimiter.  However,
> these expensive checks are performed for _every_ buffer change.  Even
> doing something like inserting a letter or a digit causes the full range
> of tests to be performed.  This is not good.

Part of the problem is that CC-mode is very eager in its management of
syntax information: the `syntax-table` text-properties are always kept
up-to-date over the whole buffer right after every single change.

Modes using syntax-propertize work more lazily: before-change-functions
only marks that some change occurred at position POS and the syntax-table
properties after that position are only updated afterward on-demand.

CC-mode tries to make up for it by being more clever about which parts of
the buffer after position POS actually need to be updated, but when
there are several consecutive changes, the extra work performed between
each one of those changes add up quickly.

[ Of course, there are cases where the approach used in
  syntax-propertize loses big time.  E.g. if you have a loop that first
  modifies a char near point-min, then asks for the syntax-table
  properties near point-max, and then repeats... performance will suck.
  But luckily I haven't yet seen a real-world use case where
  this occurs.  ]

Maybe another part of the problem is that CC-mode tries to do more than
most other major modes: e.g. the highlighting of unclosed strings.
For plain single-line strings this can be fairly cheap, but for
multiline strings, keeping this information constantly up-to-date over
the whole buffer can be costly.

Most other major modes just let the font-lock-string-face bleeds further
than the user intended, which requires much less work and works well
enough for all other syntactic elements (CC-mode doesn't highlight
unclosed parens, or mismatched parens, or `do` with missing `while`,
...).  When needed these many different kinds of errors are detected and
shown to the user via things like flymake or LSP instead, which work
much more lazily w.r.t buffer changes, so they don't need to same kind
of engineering efforts to make them fast enough.

> Thoughts?

Not sure whether you intend this to be just a change to CC-mode (it does
sound like it can all be implemented in Elisp) or you intend for some
change at the C level.  My gut feeling is that the checks you suggest in
(iii) could be implemented in Elisp without losing too much performance
(they should spend most of their time within a few C primitives), tho it
depends on the specifics of the cases you'll want to catch.  Also if you
want to implement it in C those same specifics will need to be spelled
out to figure out how a major mode will communicate them to the C code
(for this to be useful beyond CC-mode, it would need to be very general,
so it could be tricky to design).

But to tell you the truth, other than CC-mode, I'm having a hard time
imagining which other major mode will want to use such a thing.
Performance of syntax-propertize is not stellar but doesn't seem
problematic, and it is not too hard to use (its functioning is not
exactly the same as what a real lexer would do, but you can make use of
the language spec more or less straightforwardly), whereas I get the
impression that your suggestion relies on properties of the language
which are not often used, so are less familiar to the average
mode implementor (and a language spec is unlikely to help you figure out
what to do).

Maybe if we want to speed things up, we should consider a new parsing
engine (instead of parse-partial-sexp and syntax-tables) based maybe on
a DFA for the tokenizer and GLR parser on top.  That might arguably be
more generally useful and easier to use (in the sense that one can more
or less follow the language spec when implementing the major mode).


        Stefan

Re: A possible way for CC Mode to resolve its sluggishness

[Óscar Fuentes]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Maybe if we want to speed things up, we should consider a new parsing
> engine (instead of parse-partial-sexp and syntax-tables) based maybe on
> a DFA for the tokenizer and GLR parser on top.  That might arguably be
> more generally useful and easier to use (in the sense that one can more
> or less follow the language spec when implementing the major mode).

No parser will provide the information that cc-mode needs to properly
indent and colorize C++ code. Only a C++ front-end, which performs
semantic analysis, knows that information.

Re: A possible way for CC Mode to resolve its sluggishness

[Alan Mackenzie]

Hello, Stefan.

On Fri, Apr 26, 2019 at 22:10:23 -0400, Stefan Monnier wrote:
> > The problem is that CC Mode's before/after-change-functions are very
> > general, and scan the buffer looking for situations which only arise
> > sporadically.  Things like an open string getting closed, or a >
> > being inserted which needs to be checked for a template delimiter.
> > However, these expensive checks are performed for _every_ buffer
> > change.  Even doing something like inserting a letter or a digit
> > causes the full range of tests to be performed.  This is not good.

> Part of the problem is that CC-mode is very eager in its management of
> syntax information: the `syntax-table` text-properties are always kept
> up-to-date over the whole buffer right after every single change.

That is not part of the problem.  That is part of the challenge.

> Modes using syntax-propertize work more lazily:
> before-change-functions only marks that some change occurred at
> position POS and the syntax-table properties after that position are
> only updated afterward on-demand.

Yes, but it is somewhat unclear whether, how, and when modes using
syntax-propertize can update syntax-table properties on positions
_before_ a change.  This is a prime reason for CC Mode not using this
strategy.

> CC-mode tries to make up for it by being more clever about which parts
> of the buffer after position POS actually need to be updated, but when
> there are several consecutive changes, the extra work performed
> between each one of those changes add up quickly.

My proposal is to reduce this amount of work when it's not needed.

> [ Of course, there are cases where the approach used in
>   syntax-propertize loses big time.  E.g. if you have a loop that first
>   modifies a char near point-min, then asks for the syntax-table
>   properties near point-max, and then repeats... performance will suck.
>   But luckily I haven't yet seen a real-world use case where
>   this occurs.  ]

> Maybe another part of the problem is that CC-mode tries to do more than
> most other major modes: e.g. the highlighting of unclosed strings.
> For plain single-line strings this can be fairly cheap, but for
> multiline strings, keeping this information constantly up-to-date over
> the whole buffer can be costly.

CC Mode is successful in this regard.  The highlighting with
warning-face of unclosed string openers is a useful feature which other
modes could emulate.

I think I suggested a little while ago that this could be done in
syntactic analysis and font-lock.  We have a syntax flag saying "this
character (LF) terminates a style b comment", we could equally well have
a flag saying it terminates a string.  Then font-lock could examine the
string terminator, and use string-face or warning-face on the opener
depending on the terminating character.

But that's a digression from the topic of this thread.

> Most other major modes just let the font-lock-string-face bleeds further
> than the user intended, which requires much less work and works well
> enough for all other syntactic elements (CC-mode doesn't highlight
> unclosed parens, or mismatched parens, or `do` with missing `while`,
> ...).  When needed these many different kinds of errors are detected and
> shown to the user via things like flymake or LSP instead, which work
> much more lazily w.r.t buffer changes, so they don't need to same kind
> of engineering efforts to make them fast enough.

> > Thoughts?

> Not sure whether you intend this to be just a change to CC-mode (it does
> sound like it can all be implemented in Elisp) or you intend for some
> change at the C level.

At the Lisp level.  I hadn't even considered any C enhancements.

> My gut feeling is that the checks you suggest in (iii) could be
> implemented in Elisp without losing too much performance (they should
> spend most of their time within a few C primitives), tho it depends on
> the specifics of the cases you'll want to catch.  Also if you want to
> implement it in C those same specifics will need to be spelled out to
> figure out how a major mode will communicate them to the C code (for
> this to be useful beyond CC-mode, it would need to be very general, so
> it could be tricky to design).

> But to tell you the truth, other than CC-mode, I'm having a hard time
> imagining which other major mode will want to use such a thing.
> Performance of syntax-propertize is not stellar but doesn't seem
> problematic, and it is not too hard to use (its functioning is not
> exactly the same as what a real lexer would do, but you can make use of
> the language spec more or less straightforwardly), ....

Again, can syntax-propertize work on positions _before_ a buffer change?

> .... whereas I get the impression that your suggestion relies on
> properties of the language which are not often used, so are less
> familiar to the average mode implementor (and a language spec is
> unlikely to help you figure out what to do).

If other modes were to use the mechanism, they would need to define
their syntactic cell boundaries, as indeed I yet have to do for CC Mode.

> Maybe if we want to speed things up, we should consider a new parsing
> engine (instead of parse-partial-sexp and syntax-tables) based maybe on
> a DFA for the tokenizer and GLR parser on top.  That might arguably be
> more generally useful and easier to use (in the sense that one can more
> or less follow the language spec when implementing the major mode).

That would be a lot of design and a lot of work, and sounds like
something from the distant rather than medium future.  The indentation
and font-lock routines would have to be rewritten for each mode using
it.

>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: A possible way for CC Mode to resolve its sluggishness

[Stephen Leake]

Alan Mackenzie <acm@muc.de> writes:

>> Maybe if we want to speed things up, we should consider a new parsing
>> engine (instead of parse-partial-sexp and syntax-tables) based maybe on
>> a DFA for the tokenizer and GLR parser on top.  That might arguably be
>> more generally useful and easier to use (in the sense that one can more
>> or less follow the language spec when implementing the major mode).
>
> That would be a lot of design and a lot of work, and sounds like
> something from the distant rather than medium future.  

ada-mode uses just that approach; the WisiToken parser generator reads a
bison-like description of the grammar, and generates a lexer and
error-correcting parser. Those run in an Emacs background process,
which also runs other code to process the AST and produce font and
indent info, which is sent back to Emacs.

It works very well for Ada code, and I've got a very preliminary version
working with Java. See http://www.nongnu.org/ada-mode/ for the latest
release.

C++ is definitely more of a challenge; you need to run the preprocessor,
at least. In another post Oscar says you would need a full C++
front-end; I can believe that. Still, the approach is similar; run the
C++ front-end (maybe the clang one?) in a background process, together
with code that computes the info needed by Emacs.

One possible problem is that the parser needs to handle huge syntax
errors; it will be called to compute indent when the user has entered a
partial statement and hit return. I don't know how good clang is with
error correction; I spent a lot of time making the WisiToken parser
handle such errors well.

> The indentation and font-lock routines would have to be rewritten
> for each mode using it.

Yes; I had to translate the elisp into Ada. Currently, I'm maintaining
both (to support people who don't want to or can't compile the
background process code), but at some point I'll probably drop the
elisp.


It is a huge redesign and implementation effort. I started this for Ada
in 2013 when it became clear that the earlier ad-hoc approach could not
handle Ada 95 and 2012 syntax, and it took several years (with several
detours along the way; Java will take much less time). I'm almost at the
point where I can delete the old ad-hoc ada-mode code from Emacs core.

-- 
-- Stephe

Re: A possible way for CC Mode to resolve its sluggishness

[Stefan Monnier]

>> Part of the problem is that CC-mode is very eager in its management of
>> syntax information: the `syntax-table` text-properties are always kept
>> up-to-date over the whole buffer right after every single change.
> That is not part of the problem.  That is part of the challenge.

Keeping everything always up-to-date, whether we use them or not, is not
in itself of any benefit to the end-user.

So it's a self-imposed challenge.  I think here are enough challenges
without having to add this one to the lot.

>> Modes using syntax-propertize work more lazily:
>> before-change-functions only marks that some change occurred at
>> position POS and the syntax-table properties after that position are
>> only updated afterward on-demand.
>
> Yes, but it is somewhat unclear whether, how, and when modes using
> syntax-propertize can update syntax-table properties on positions
> _before_ a change.

When syntax-propertize-function is called on BEG..END it's not expected
to touch anything outside of the BEG..END region (I think it's perfectly
safe to touch things after END, but it's definitely risky to touch
things before BEG).

When a change at buffer position POS requires updating syntax-table (or
other) text-properties at some earlier position, this can be indicated
to syntax-propertize via syntax-propertize-extend-region-functions.

>> Maybe another part of the problem is that CC-mode tries to do more than
>> most other major modes: e.g. the highlighting of unclosed strings.
>> For plain single-line strings this can be fairly cheap, but for
>> multiline strings, keeping this information constantly up-to-date over
>> the whole buffer can be costly.
>
> CC Mode is successful in this regard.  The highlighting with
> warning-face of unclosed string openers is a useful feature which other
> modes could emulate.

I don't think "successful" is an appropriate description (e.g. I don't
know what a failure would be).  What I do know, is that this
highlighting imposes significant additional work (e.g. because it more
often requires updating text-properties before the place where
text was modified).
And that it's an incomplete feature: it only does that for strings.

Other major modes provide a more complete implementation of that feature
via flymake/lsp without imposing that extra work on
before/after-change-functions.

It also means that those modes don't try to give a definite answer to
questions of what to do in the face of invalid code
(e.g. non-terminated strings or comments, mismatched parens, ...)
a limit themselves to try and avoid doing something "obviously" wrong in
those case.

I know you think this is a bad design decision, but it's a design
decision that is largely unavoidable (e.g. C-mode has to do the same
when faced with some uses of CPP which render the "un-preprocessed"
code unparsable) and Emacs usually gets a lot of benefits from it in
terms of simplicity and performance.

> But that's a digression from the topic of this thread.

Indeed.

>> Not sure whether you intend this to be just a change to CC-mode (it does
>> sound like it can all be implemented in Elisp) or you intend for some
>> change at the C level.
> At the Lisp level.  I hadn't even considered any C enhancements.

Good.  Then I think it's worth a try.

>> But to tell you the truth, other than CC-mode, I'm having a hard time
>> imagining which other major mode will want to use such a thing.
>> Performance of syntax-propertize is not stellar but doesn't seem
>> problematic, and it is not too hard to use (its functioning is not
>> exactly the same as what a real lexer would do, but you can make use of
>> the language spec more or less straightforwardly), ....
> Again, can syntax-propertize work on positions _before_ a buffer change?

Yes.  There has not been much need for it, tho, so support for it is
fairly primitive.

E.g. most modes that have such needs don't use
syntax-propertize-extend-region-functions but rely on
jit-lock-multiline, which makes this kind of "update an earlier part of
the buffer" happen at a later time, and hence causes the text-properties
to be left invalid for a while.

Delaying updates this way is OK for font-lock highlighting, but is wrong
for syntax-propertize, so we should change those modes to use
syntax-propertize-extend-region-functions where relevant.

>> Maybe if we want to speed things up, we should consider a new parsing
>> engine (instead of parse-partial-sexp and syntax-tables) based maybe on
>> a DFA for the tokenizer and GLR parser on top.  That might arguably be
>> more generally useful and easier to use (in the sense that one can more
>> or less follow the language spec when implementing the major mode).
> That would be a lot of design and a lot of work, and sounds like
> something from the distant rather than medium future.

Agreed.

> The indentation and font-lock routines would have to be rewritten for
> each mode using it.

It would probably be a good idea to make use of parsing info for those,
but not indispensable.


        Stefan

Re: A possible way for CC Mode to resolve its sluggishness

[Alan Mackenzie]

Hello, Stefan.

On Sun, Apr 28, 2019 at 21:46:25 -0400, Stefan Monnier wrote:
> Keeping everything always up-to-date, whether we use them or not, is not
> in itself of any benefit to the end-user.

I may quote you on this at some time in the future.  :-)

[ .... ]

> >> Maybe another part of the problem is that CC-mode tries to do more than
> >> most other major modes: e.g. the highlighting of unclosed strings.
> >> For plain single-line strings this can be fairly cheap, but for
> >> multiline strings, keeping this information constantly up-to-date over
> >> the whole buffer can be costly.

> > CC Mode is successful in this regard.  The highlighting with
> > warning-face of unclosed string openers is a useful feature which other
> > modes could emulate.

> I don't think "successful" is an appropriate description (e.g. I don't
> know what a failure would be).

I was countering your disparaging use of the word "tries", which was
uncalled for.  It suggested that attempts have been made to do things in
CC Mode, but those attempts have failed.  That is not the case.

[ .... ]

>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: A possible way for CC Mode to resolve its sluggishness

[Stefan Monnier]

>> Keeping everything always up-to-date, whether we use them or not, is not
>> in itself of any benefit to the end-user.
> I may quote you on this at some time in the future.  :-)

Cc me when you do ;-)
>> I don't think "successful" is an appropriate description (e.g. I don't
>> know what a failure would be).
> I was countering your disparaging use of the word "tries", which was
> uncalled for.  It suggested that attempts have been made to do things in
> CC Mode, but those attempts have failed.  That is not the case.


I see, thanks for explaining.  I didn't mean it to be disparaging, but
I can see how it could be read that way.


        Stefan