bug#59738: c-ts-mode is slow with large buffers.

bug#59738: c-ts-mode is slow with large buffers.

[Alan Mackenzie]

Hello, Emacs.

In an up to date (2022-11-30) master started as $ emacs --no-desktop:

The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
in the Linux source tree is 6.8 MB big, consisting of a large number of
#defines and comments, but nothing else.

To scroll through it in c-ts-mode takes a little over 26 minutes on my
system.  By comparison, in C Mode it takes 31 seconds.  There would
appear to be a need for some optimisation in c-ts-mode, here.


The file
https://gitlab.com/wireshark/wireshark/-/raw/master/epan/dissectors/packet-rrc.c
(see bug #45248) (10 MB) takes 578 seconds to scroll in c-ts-mode.  It
scrolls through the first 83% of the buffer rapidly, then chokes on a big
brace block initialisation.  Also, the font-locking fails part way
through this brace block (without any apparent speed up).

For comparison, the scrolling takes 30 seconds in C Mode.  There seems to
be a need for optimisation of c-ts-mode in this case, too.


For completeness, I used M-: (time-scroll) in the following for the
timings:

(defmacro time-it (&rest forms)
  "Time the running of a sequence of forms using `float-time'.
Call like this: \"M-: (time-it (foo ...) (bar ...) ...)\"."
  `(let ((start (float-time)))
    ,@forms
    (- (float-time) start)))

(defun time-scroll (&optional arg)
  (interactive "P")
  (message "%s"
           (time-it
            (condition-case nil
                (while t
                  (if arg (scroll-down) (scroll-up))
                  (sit-for 0))
              (error nil)))))


-- 
Alan Mackenzie (Nuremberg, Germany).

bug#59738: c-ts-mode is slow with large buffers.

[Yuan Fu via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Alan Mackenzie <acm@muc.de> writes:

> Hello, Emacs.
>
> In an up to date (2022-11-30) master started as $ emacs --no-desktop:
>
> The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
> in the Linux source tree is 6.8 MB big, consisting of a large number of
> #defines and comments, but nothing else.
>
> To scroll through it in c-ts-mode takes a little over 26 minutes on my
> system.  By comparison, in C Mode it takes 31 seconds.  There would
> appear to be a need for some optimisation in c-ts-mode, here.
>
>
> The file
> https://gitlab.com/wireshark/wireshark/-/raw/master/epan/dissectors/packet-rrc.c
> (see bug #45248) (10 MB) takes 578 seconds to scroll in c-ts-mode.  It
> scrolls through the first 83% of the buffer rapidly, then chokes on a big
> brace block initialisation.  Also, the font-locking fails part way
> through this brace block (without any apparent speed up).
>
> For comparison, the scrolling takes 30 seconds in C Mode.  There seems to
> be a need for optimisation of c-ts-mode in this case, too.
>
>
> For completeness, I used M-: (time-scroll) in the following for the
> timings:
>
> (defmacro time-it (&rest forms)
>   "Time the running of a sequence of forms using `float-time'.
> Call like this: \"M-: (time-it (foo ...) (bar ...) ...)\"."
>   `(let ((start (float-time)))
>     ,@forms
>     (- (float-time) start)))
>
> (defun time-scroll (&optional arg)
>   (interactive "P")
>   (message "%s"
>            (time-it
>             (condition-case nil
>                 (while t
>                   (if arg (scroll-down) (scroll-up))
>                   (sit-for 0))
>               (error nil)))))

Thanks for the report! I’m a bit overwelmed by all the open bug reports
right now, but I’ll be sure to investigate it as soon as I’m able.

Yuan

bug#59738: c-ts-mode is slow with large buffers.

[Yuan Fu]

Alan Mackenzie <acm@muc.de> writes:

> Hello, Emacs.
>
> In an up to date (2022-11-30) master started as $ emacs --no-desktop:
>
> The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
> in the Linux source tree is 6.8 MB big, consisting of a large number of
> #defines and comments, but nothing else.
>
> To scroll through it in c-ts-mode takes a little over 26 minutes on my
> system.  By comparison, in C Mode it takes 31 seconds.  There would
> appear to be a need for some optimisation in c-ts-mode, here.
>
>
> The file
> https://gitlab.com/wireshark/wireshark/-/raw/master/epan/dissectors/packet-rrc.c
> (see bug #45248) (10 MB) takes 578 seconds to scroll in c-ts-mode.  It
> scrolls through the first 83% of the buffer rapidly, then chokes on a big
> brace block initialisation.  Also, the font-locking fails part way
> through this brace block (without any apparent speed up).
>
> For comparison, the scrolling takes 30 seconds in C Mode.  There seems to
> be a need for optimisation of c-ts-mode in this case, too.
>
>
> For completeness, I used M-: (time-scroll) in the following for the
> timings:
>
> (defmacro time-it (&rest forms)
>   "Time the running of a sequence of forms using `float-time'.
> Call like this: \"M-: (time-it (foo ...) (bar ...) ...)\"."
>   `(let ((start (float-time)))
>     ,@forms
>     (- (float-time) start)))
>
> (defun time-scroll (&optional arg)
>   (interactive "P")
>   (message "%s"
>            (time-it
>             (condition-case nil
>                 (while t
>                   (if arg (scroll-down) (scroll-up))
>                   (sit-for 0))
>               (error nil)))))

Ah, the lovely packet-rrc.c file. We had some discussion of it in
bug#59415, basically it contains some syntax that screws tree-sitter up.
The block initialization you see makes tree-sitter into erroneously
generating a very tall tree: it recognizes all the opening bracket and
ignores (almost) all the closing brackets. That causes operations on the
tree to be much much slower than it normally is.

I added some fix so the rest of the file can be largely unaffected, and
reported this problem to tree-sitter-c’s developer (no reply as of now).
There is not much we can do to fix this, and since it’s rare, I think a
user could probably just use c-mode for this kind of files.

Yuan

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> Date: Thu, 1 Dec 2022 11:50:05 +0000
> From: Alan Mackenzie <acm@muc.de>
> 
> Hello, Emacs.
> 
> In an up to date (2022-11-30) master started as $ emacs --no-desktop:
> 
> The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
> in the Linux source tree is 6.8 MB big, consisting of a large number of
> #defines and comments, but nothing else.

Please post the file (compressed), or tell how to access it on your
machine.

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> Cc: 59738@debbugs.gnu.org
> Date: Wed, 07 Dec 2022 16:34:13 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> 
> > Date: Thu, 1 Dec 2022 11:50:05 +0000
> > From: Alan Mackenzie <acm@muc.de>
> > 
> > Hello, Emacs.
> > 
> > In an up to date (2022-11-30) master started as $ emacs --no-desktop:
> > 
> > The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
> > in the Linux source tree is 6.8 MB big, consisting of a large number of
> > #defines and comments, but nothing else.
> 
> Please post the file (compressed), or tell how to access it on your
> machine.

And, btw, please do the benchmarks on the release branch, since it
will be released much sooner than master, and because the main work on
the tree-sitter supported modes is on the release branch.

bug#59738: c-ts-mode is slow with large buffers.

[Alan Mackenzie]

[-- Attachment #1: Type: text/plain, Size: 646 bytes --]

On Wed, Dec 07, 2022 at 16:34:13 +0200, Eli Zaretskii wrote:
> > Date: Thu, 1 Dec 2022 11:50:05 +0000
> > From: Alan Mackenzie <acm@muc.de>

> > Hello, Emacs.

> > In an up to date (2022-11-30) master started as $ emacs --no-desktop:

> > The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
> > in the Linux source tree is 6.8 MB big, consisting of a large number of
> > #defines and comments, but nothing else.

> Please post the file (compressed), or tell how to access it on your
> machine.

This post (with Eli Z.'s Cc: removed) contains a compressed version of
the above file.

-- 
Alan Mackenzie (Nuremberg, Germany).


[-- Attachment #2: dce_12_0_sh_mask.h.xz --]
[-- Type: application/x-xz, Size: 155700 bytes --]

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> Cc: 59738@debbugs.gnu.org
> From: Yuan Fu <casouri@gmail.com>
> Date: Tue, 6 Dec 2022 20:56:13 -0800
> 
> 
> Alan Mackenzie <acm@muc.de> writes:
> 
> > Hello, Emacs.
> >
> > In an up to date (2022-11-30) master started as $ emacs --no-desktop:
> >
> > The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
> > in the Linux source tree is 6.8 MB big, consisting of a large number of
> > #defines and comments, but nothing else.
> >
> > To scroll through it in c-ts-mode takes a little over 26 minutes on my
> > system.  By comparison, in C Mode it takes 31 seconds.  There would
> > appear to be a need for some optimisation in c-ts-mode, here.
> >[...]
> Ah, the lovely packet-rrc.c file.

No, this is a different file, dce_12_0_sh_mask.h.  It is a header file
which only has preprocessor #define lines.  I'm puzzled why this
presents such a great difficulty for tree-sitter.  Could you take a
look what happens with that file?

> We had some discussion of it in
> bug#59415, basically it contains some syntax that screws tree-sitter up.
> The block initialization you see makes tree-sitter into erroneously
> generating a very tall tree: it recognizes all the opening bracket and
> ignores (almost) all the closing brackets. That causes operations on the
> tree to be much much slower than it normally is.

Right, but with a long series of #define lines there should be no
parse tree at all...

bug#59738: c-ts-mode is slow with large buffers.

[Yuan Fu]

> On Dec 7, 2022, at 9:23 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> 
>> Cc: 59738@debbugs.gnu.org
>> From: Yuan Fu <casouri@gmail.com>
>> Date: Tue, 6 Dec 2022 20:56:13 -0800
>> 
>> 
>> Alan Mackenzie <acm@muc.de> writes:
>> 
>>> Hello, Emacs.
>>> 
>>> In an up to date (2022-11-30) master started as $ emacs --no-desktop:
>>> 
>>> The file .../drivers/gpu/drm/amd/include/asic_reg/dce/dce_12_0_sh_mask.h
>>> in the Linux source tree is 6.8 MB big, consisting of a large number of
>>> #defines and comments, but nothing else.
>>> 
>>> To scroll through it in c-ts-mode takes a little over 26 minutes on my
>>> system.  By comparison, in C Mode it takes 31 seconds.  There would
>>> appear to be a need for some optimisation in c-ts-mode, here.
>>> [...]
>> Ah, the lovely packet-rrc.c file.
> 
> No, this is a different file, dce_12_0_sh_mask.h.  It is a header file
> which only has preprocessor #define lines.  I'm puzzled why this
> presents such a great difficulty for tree-sitter.  Could you take a
> look what happens with that file?
> 
>> We had some discussion of it in
>> bug#59415, basically it contains some syntax that screws tree-sitter up.
>> The block initialization you see makes tree-sitter into erroneously
>> generating a very tall tree: it recognizes all the opening bracket and
>> ignores (almost) all the closing brackets. That causes operations on the
>> tree to be much much slower than it normally is.
> 
> Right, but with a long series of #define lines there should be no
> parse tree at all…

Ok, I think I know why. At the beginning of the file there is this line

#ifndef _dce_12_0_SH_MASK_HEADER

So it’s parsed into a preproc_ifdef node, which contains every #define directive in the file as its immediate child. Now you have this node with a tons of immediate children. And querying this node in font-lock is very slow, even with a limited range. I think for the query result to be accurate, tree-sitter has to query the whole node without considering the range, then throw away matches that are not in the range. 

Anyway, I activated my backup backup plan, which goes down the parse tree to find a sufficiently small node to query. Now scrolling the header file is fast as other files.

Yuan

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> From: Yuan Fu <casouri@gmail.com>
> Date: Wed, 7 Dec 2022 16:40:15 -0800
> Cc: Alan Mackenzie <acm@muc.de>,
>  59738@debbugs.gnu.org
> 
> > Right, but with a long series of #define lines there should be no
> > parse tree at all…
> 
> Ok, I think I know why. At the beginning of the file there is this line
> 
> #ifndef _dce_12_0_SH_MASK_HEADER
> 
> So it’s parsed into a preproc_ifdef node, which contains every #define directive in the file as its immediate child. Now you have this node with a tons of immediate children. And querying this node in font-lock is very slow, even with a limited range. I think for the query result to be accurate, tree-sitter has to query the whole node without considering the range, then throw away matches that are not in the range. 
> 
> Anyway, I activated my backup backup plan, which goes down the parse tree to find a sufficiently small node to query. Now scrolling the header file is fast as other files.

Thanks, now c-ts-mode is twice as fast as c-mode with that file.

Great job!

bug#59738: c-ts-mode is slow with large buffers.

[Alan Mackenzie]

Hello, Eli.

On Thu, Dec 08, 2022 at 22:37:05 +0200, Eli Zaretskii wrote:
> > From: Yuan Fu <casouri@gmail.com>
> > Date: Wed, 7 Dec 2022 16:40:15 -0800
> > Cc: Alan Mackenzie <acm@muc.de>,
> >  59738@debbugs.gnu.org

> > > Right, but with a long series of #define lines there should be no
> > > parse tree at all…

> > Ok, I think I know why. At the beginning of the file there is this
> > line

> > #ifndef _dce_12_0_SH_MASK_HEADER

> > So it’s parsed into a preproc_ifdef node, which contains every
> > #define directive in the file as its immediate child. Now you have
> > this node with a tons of immediate children. And querying this node
> > in font-lock is very slow, even with a limited range. I think for the
> > query result to be accurate, tree-sitter has to query the whole node
> > without considering the range, then throw away matches that are not
> > in the range. 

> > Anyway, I activated my backup backup plan, which goes down the parse
> > tree to find a sufficiently small node to query. Now scrolling the
> > header file is fast as other files.

> Thanks, now c-ts-mode is twice as fast as c-mode with that file.

> Great job!

The bug which was causing it to be very slow is fixed, so I agree,
excellent job!

But I've measured it as being 62% faster (not twice as fast) as CC Mode.
A "normal" C file (xdisp.c) is around 160% faster, i.e. a little over 2½
times as fast.  These timings are indeed significantly faster.

But given how slow CC Mode was held to be, is a factor 2.6 speed-up
really all that we were expecting from c-ts-mode?  This is the sort of
speed-up one would get by replacing a 5 year old machine with a new one,
or using an optimised build in place of a debug build.

Was I perhaps a little unrealistic in expecting an order of magnitude
speed-up?  Is there still scope for optimisation in c-ts-mode?

-- 
Alan Mackenzie (Nuremberg, Germany).

bug#59738: c-ts-mode is slow with large buffers.

[Yuan Fu]

> On Dec 10, 2022, at 1:34 PM, Alan Mackenzie <acm@muc.de> wrote:
> 
> Hello, Eli.
> 
> On Thu, Dec 08, 2022 at 22:37:05 +0200, Eli Zaretskii wrote:
>>> From: Yuan Fu <casouri@gmail.com>
>>> Date: Wed, 7 Dec 2022 16:40:15 -0800
>>> Cc: Alan Mackenzie <acm@muc.de>,
>>> 59738@debbugs.gnu.org
> 
>>>> Right, but with a long series of #define lines there should be no
>>>> parse tree at all…
> 
>>> Ok, I think I know why. At the beginning of the file there is this
>>> line
> 
>>> #ifndef _dce_12_0_SH_MASK_HEADER
> 
>>> So it’s parsed into a preproc_ifdef node, which contains every
>>> #define directive in the file as its immediate child. Now you have
>>> this node with a tons of immediate children. And querying this node
>>> in font-lock is very slow, even with a limited range. I think for the
>>> query result to be accurate, tree-sitter has to query the whole node
>>> without considering the range, then throw away matches that are not
>>> in the range. 
> 
>>> Anyway, I activated my backup backup plan, which goes down the parse
>>> tree to find a sufficiently small node to query. Now scrolling the
>>> header file is fast as other files.
> 
>> Thanks, now c-ts-mode is twice as fast as c-mode with that file.
> 
>> Great job!
> 
> The bug which was causing it to be very slow is fixed, so I agree,
> excellent job!
> 
> But I've measured it as being 62% faster (not twice as fast) as CC Mode.
> A "normal" C file (xdisp.c) is around 160% faster, i.e. a little over 2½
> times as fast.  These timings are indeed significantly faster.
> 
> But given how slow CC Mode was held to be, is a factor 2.6 speed-up
> really all that we were expecting from c-ts-mode?  This is the sort of
> speed-up one would get by replacing a 5 year old machine with a new one,
> or using an optimised build in place of a debug build.
> 
> Was I perhaps a little unrealistic in expecting an order of magnitude
> speed-up?  Is there still scope for optimisation in c-ts-mode?

AFAIK not too much room for optimization. Querying the patterns takes like 99% of the time during fontification.
Querying time (thus fontification time) increases as the buffer size increases, even if we limit the range of the query to a fixed region (which is what we do in tree-sitter font-lock). This is unlike c-mode, where fontifying a region takes the same amount of time regardless of the buffer size. Some benchmarks I did:

In xdisp.c

Time        Task
0.0008      A single query for comments
0.008       All queries in c-ts-mode
0.00815     treesit-font-lock-fontify-region (1500 char)
0.0214      font-lock-fontify-region in c-mode (1500 char)
12.048      time-scroll in c-ts-mode
21.206      time-scroll in c-mode
5.539       time-scroll in fundamental-mode

In treesit.c

Time        Task
0.00336     All queries in c-ts-mode
0.00391     treesit-font-lock-fontify-region (1500 char)
0.0281      font-lock-fontify-region in c-mode (1500 char)
1.958       time-scroll in c-ts-mode
1.969       time-scroll in c-mode
0.535       time-scroll in fundamental-mode

Though I’ll note that tree-sitter would provide other benefits. I don’t know how much time does c-mode spend on analyzing the buffer content when user edits it, but I imagine tree-sitter to be faster in that regard, too. That should help the perceived performance. Also (unrelated to performance) tree-sitter makes it vastly easier to write (and maintain) a major mode.

Yuan

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> Date: Sat, 10 Dec 2022 21:34:20 +0000
> Cc: Yuan Fu <casouri@gmail.com>, 59738@debbugs.gnu.org
> From: Alan Mackenzie <acm@muc.de>
> 
> > Thanks, now c-ts-mode is twice as fast as c-mode with that file.
> 
> > Great job!
> 
> The bug which was causing it to be very slow is fixed, so I agree,
> excellent job!
> 
> But I've measured it as being 62% faster (not twice as fast) as CC Mode.
> A "normal" C file (xdisp.c) is around 160% faster, i.e. a little over 2½
> times as fast.

You do all your measurements in an optimized build of Emacs.  I did
mine in an unoptimized build, something that I need to use all the
time, even though my production sessions run optimized builds.  In an
unoptimized build CC Mode is extremely slow.  For example, just
visiting dce_12_0_sh_mask.h file takes a whopping 67 sec, and M->
immediately after the file is displayed takes another 25 sec.  With
c-ts-mode, these numbers are, respectively, 1.8 sec and 2 sec.

IOW, scrolling through the whole humongous file measures some aspect
of the redisplay (actually, JIT font-lock) performance, but that is
not all that matters when one has to edit a file; the above two
situations are also important use cases.

However, talking only about speed is looking at this from an incorrect
aspect, see below.

> But given how slow CC Mode was held to be, is a factor 2.6 speed-up
> really all that we were expecting from c-ts-mode?  This is the sort of
> speed-up one would get by replacing a 5 year old machine with a new one,
> or using an optimised build in place of a debug build.

Speed is not the main reason why we want to have font-lock and
indentation based on a parser library.  The main reason is
_correctness_ and _accuracy_.  A regexp-based fontification and
indentation engines will never be able to match parser-based engines,
because they doesn't really understand the source code.  Even when
aided by syntax-ppss, they only catch some part of the syntax, and
none of the semantics.  The hope is that using a parser will allow us
to provide much more accurate implementations.  Whether and how much
this hope will materialize is yet to be seen, but looking just at the
speedup is definitely not TRT for assessing the success of this
development in Emacs.

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> From: Yuan Fu <casouri@gmail.com>
> Date: Sat, 10 Dec 2022 15:14:27 -0800
> Cc: Eli Zaretskii <eliz@gnu.org>,
>  59738@debbugs.gnu.org
> 
> Querying time (thus fontification time) increases as the buffer size increases, even if we limit the range of the query to a fixed region (which is what we do in tree-sitter font-lock). This is unlike c-mode, where fontifying a region takes the same amount of time regardless of the buffer size.

The last sentence is inaccurate: sometimes CC Mode must look far
beyond the fixed region which jit-lock.el asks it to fontify.  AFAIR,
that is mainly to figure out the syntactical context of the portion of
the buffer that needs to be fontified.

bug#59738: c-ts-mode is slow with large buffers.

[Alan Mackenzie]

Hello, Yuan.

On Sat, Dec 10, 2022 at 15:14:27 -0800, Yuan Fu wrote:

> > On Dec 10, 2022, at 1:34 PM, Alan Mackenzie <acm@muc.de> wrote:

[ .... ]

> > The bug which was causing it to be very slow is fixed, so I agree,
> > excellent job!

> > But I've measured it as being 62% faster (not twice as fast) as CC
> > Mode.  A "normal" C file (xdisp.c) is around 160% faster, i.e. a
> > little over 2½ times as fast.  These timings are indeed significantly
> > faster.

> > But given how slow CC Mode was held to be, is a factor 2.6 speed-up
> > really all that we were expecting from c-ts-mode?  This is the sort
> > of speed-up one would get by replacing a 5 year old machine with a
> > new one, or using an optimised build in place of a debug build.

> > Was I perhaps a little unrealistic in expecting an order of magnitude
> > speed-up?  Is there still scope for optimisation in c-ts-mode?

> AFAIK not too much room for optimization. Querying the patterns takes
> like 99% of the time during fontification.  Querying time (thus
> fontification time) increases as the buffer size increases, even if we
> limit the range of the query to a fixed region (which is what we do in
> tree-sitter font-lock).

This seems similar to c-mode, where a syntactically coherent region is
determined each time fontification is done.

> This is unlike c-mode, where fontifying a region takes the same amount
> of time regardless of the buffer size.

OK, thanks for the explanation.

> Some benchmarks I did:

> In xdisp.c

> Time        Task
> 0.0008      A single query for comments
> 0.008       All queries in c-ts-mode
> 0.00815     treesit-font-lock-fontify-region (1500 char)
> 0.0214      font-lock-fontify-region in c-mode (1500 char)
> 12.048      time-scroll in c-ts-mode
> 21.206      time-scroll in c-mode
> 5.539       time-scroll in fundamental-mode

> In treesit.c

> Time        Task
> 0.00336     All queries in c-ts-mode
> 0.00391     treesit-font-lock-fontify-region (1500 char)
> 0.0281      font-lock-fontify-region in c-mode (1500 char)
> 1.958       time-scroll in c-ts-mode
> 1.969       time-scroll in c-mode
> 0.535       time-scroll in fundamental-mode

Those look the same as timings I've done.

> Though I’ll note that tree-sitter would provide other benefits. I don’t
> know how much time does c-mode spend on analyzing the buffer content
> when user edits it, ....

It's quite a lot.  Occasionally, it's enough to make the response appear
a little sluggish.  This analysis, time-wise, is less critical than the
time taken for font locking, though.

> .... but I imagine tree-sitter to be faster in that regard, too. That
> should help the perceived performance. Also (unrelated to performance)
> tree-sitter makes it vastly easier to write (and maintain) a major
> mode.

Yes indeed!  We have the advantage that a core part of the functionality
is taken care of by an external party.  But we also have the disadvantage
that a core part of the functionality is taken care of by an external
party.

> Yuan

-- 
Alan Mackenzie (Nuremberg, Germany).

bug#59738: c-ts-mode is slow with large buffers.

[Dmitry Gutov]

On 11/12/2022 15:22, Alan Mackenzie wrote:
>> Though I’ll note that tree-sitter would provide other benefits. I don’t
>> know how much time does c-mode spend on analyzing the buffer content
>> when user edits it, ....
> It's quite a lot.  Occasionally, it's enough to make the response appear
> a little sluggish.  This analysis, time-wise, is less critical than the
> time taken for font locking, though.

If we test a different scenario (font-locking just one screen-ful, 
perhaps repeatedly, while the user is typing), which of the steps can 
take more time in a large buffer?

bug#59738: c-ts-mode is slow with large buffers.

[Alan Mackenzie]

Hello, Eli.

On Sun, Dec 11, 2022 at 08:45:21 +0200, Eli Zaretskii wrote:
> > Date: Sat, 10 Dec 2022 21:34:20 +0000
> > Cc: Yuan Fu <casouri@gmail.com>, 59738@debbugs.gnu.org
> > From: Alan Mackenzie <acm@muc.de>

> > > Thanks, now c-ts-mode is twice as fast as c-mode with that file.

> > > Great job!

> > The bug which was causing it to be very slow is fixed, so I agree,
> > excellent job!

> > But I've measured it as being 62% faster (not twice as fast) as CC Mode.
> > A "normal" C file (xdisp.c) is around 160% faster, i.e. a little over 2½
> > times as fast.

> You do all your measurements in an optimized build of Emacs.  I did
> mine in an unoptimized build, something that I need to use all the
> time, even though my production sessions run optimized builds.  In an
> unoptimized build CC Mode is extremely slow.

I've built an emacs-29 with CFLAGS='-O0 -g3', --with-native-compilation,
and --with-enable-checking=all.  Just about anything is slow in such a
build.  For example, converting the org mode manual from .org to .texi
took ~15 minutes in the bootstrap.  I think this configuration is close
to your unoptimized build.

Do you really need to run in such a build all the time?  We're talking
about an order of magnitude slow-down from an optimized build.  Surely
only a tiny portion of bugs actually need this level of pessimisation.
Even a "normal" debugging build (without the --with-enable-checking) is
going to be a factor of ~3 faster, and surely would be suitable for
nearly all debugging.

> For example, just visiting dce_12_0_sh_mask.h file takes a whopping 67
> sec, and M-> immediately after the file is displayed takes another 25
> sec.  With c-ts-mode, these numbers are, respectively, 1.8 sec and 2
> sec.

Yes.  I saw pretty much the same in my pessimised build.  In a normal
build, these operation are ~10 times as fast.  Also we're all agreed
dce_12_0_sh_mask.h is an unusual file, both in its content and its size.

> IOW, scrolling through the whole humongous file measures some aspect
> of the redisplay (actually, JIT font-lock) performance, but that is
> not all that matters when one has to edit a file; the above two
> situations are also important use cases.

> However, talking only about speed is looking at this from an incorrect
> aspect, see below.

If I remember rightly, speed was one of the main reasons given for
introducing tree-sitter, though I may well be wrong here.

> > But given how slow CC Mode was held to be, is a factor 2.6 speed-up
> > really all that we were expecting from c-ts-mode?  This is the sort of
> > speed-up one would get by replacing a 5 year old machine with a new one,
> > or using an optimised build in place of a debug build.

> Speed is not the main reason why we want to have font-lock and
> indentation based on a parser library.  The main reason is
> _correctness_ and _accuracy_.  A regexp-based fontification and
> indentation engines will never be able to match parser-based engines,
> because they doesn't really understand the source code.

Given the current CC Mode, any increase in correctness is going to be
marginal, if apparent at all.

> Even when aided by syntax-ppss, they only catch some part of the
> syntax, and none of the semantics.

c-forward-decl-or-cast-1 and friends do analyze semantics; the level of
analysis is part of the reason why CC Mode's fontification isn't fast.

> The hope is that using a parser will allow us to provide much more
> accurate implementations.  Whether and how much this hope will
> materialize is yet to be seen, but looking just at the speedup is
> definitely not TRT for assessing the success of this development in
> Emacs.

I see the advantage of the new tree sitter modes more in a reduction of
maintenance burden (though few other people will see this with respect to
CC Mode ;-).

-- 
Alan Mackenzie (Nuremberg, Germany).

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> Date: Sun, 11 Dec 2022 17:13:49 +0000
> Cc: casouri@gmail.com, 59738@debbugs.gnu.org
> From: Alan Mackenzie <acm@muc.de>
> 
> > You do all your measurements in an optimized build of Emacs.  I did
> > mine in an unoptimized build, something that I need to use all the
> > time, even though my production sessions run optimized builds.  In an
> > unoptimized build CC Mode is extremely slow.
> 
> I've built an emacs-29 with CFLAGS='-O0 -g3', --with-native-compilation,
> and --with-enable-checking=all.  Just about anything is slow in such a
> build.  For example, converting the org mode manual from .org to .texi
> took ~15 minutes in the bootstrap.

The time it takes to build the Org manual doesn't bother me, since it
is rarely redone, and is not part of my maintenance job.  Also, in my
builds I get to producing the Org manual when the Lisp files are
already byte-compiled, so it takes much less than 15 min.  And
finally, I almost never bootstrap.

> Do you really need to run in such a build all the time?

It is impossible to debug Emacs efficiently on the C level using the
optimized build.  So yes, I'm using unoptimized builds quite a lot.

> > For example, just visiting dce_12_0_sh_mask.h file takes a whopping 67
> > sec, and M-> immediately after the file is displayed takes another 25
> > sec.  With c-ts-mode, these numbers are, respectively, 1.8 sec and 2
> > sec.
> 
> Yes.  I saw pretty much the same in my pessimised build.  In a normal
> build, these operation are ~10 times as fast.  Also we're all agreed
> dce_12_0_sh_mask.h is an unusual file, both in its content and its size.

If it is an unusual file, why did you report the slow scrolling
through it as a bug?  We need to be consistent: either that file is
legitimate and Emacs should work reasonably fast with it, or it isn't.

> If I remember rightly, speed was one of the main reasons given for
> introducing tree-sitter, though I may well be wrong here.

Not from my POV, no.  It's an important factor, but not the main
reason.

> > Speed is not the main reason why we want to have font-lock and
> > indentation based on a parser library.  The main reason is
> > _correctness_ and _accuracy_.  A regexp-based fontification and
> > indentation engines will never be able to match parser-based engines,
> > because they doesn't really understand the source code.
> 
> Given the current CC Mode, any increase in correctness is going to be
> marginal, if apparent at all.

I disagree.  Both C and C++ are still evolving, and their syntax and
semantics don't become simpler.  People post bug reports against CC
Mode which involve some tricky syntactical constructs all the time.
Our current font-lock is just a huge collection of ad-hocery, and
there's a limit to what we can do with ad-hoc code.  Personally, I
think this is an evolutionary dead end.  It was acceptable years ago,
when the incremental parsing technology was not developed enough
and/or not accessible easily enough.

> > Even when aided by syntax-ppss, they only catch some part of the
> > syntax, and none of the semantics.
> 
> c-forward-decl-or-cast-1 and friends do analyze semantics

A small part of it.

> > The hope is that using a parser will allow us to provide much more
> > accurate implementations.  Whether and how much this hope will
> > materialize is yet to be seen, but looking just at the speedup is
> > definitely not TRT for assessing the success of this development in
> > Emacs.
> 
> I see the advantage of the new tree sitter modes more in a reduction of
> maintenance burden (though few other people will see this with respect to
> CC Mode ;-).

That too.

bug#59738: c-ts-mode is slow with large buffers.

[Alan Mackenzie]

Hello, Eli.

On Sun, Dec 11, 2022 at 19:38:24 +0200, Eli Zaretskii wrote:
> > Date: Sun, 11 Dec 2022 17:13:49 +0000
> > Cc: casouri@gmail.com, 59738@debbugs.gnu.org
> > From: Alan Mackenzie <acm@muc.de>

> > > You do all your measurements in an optimized build of Emacs.  I did
> > > mine in an unoptimized build, something that I need to use all the
> > > time, even though my production sessions run optimized builds.  In an
> > > unoptimized build CC Mode is extremely slow.

> > I've built an emacs-29 with CFLAGS='-O0 -g3', --with-native-compilation,
> > and --with-enable-checking=all.  Just about anything is slow in such a
> > build.  For example, converting the org mode manual from .org to .texi
> > took ~15 minutes in the bootstrap.

> The time it takes to build the Org manual doesn't bother me, since it
> is rarely redone, and is not part of my maintenance job.  Also, in my
> builds I get to producing the Org manual when the Lisp files are
> already byte-compiled, so it takes much less than 15 min.  And
> finally, I almost never bootstrap.

I was advancing that figure merely as a measure of how slow such a build
is.

> > Do you really need to run in such a build all the time?

> It is impossible to debug Emacs efficiently on the C level using the
> optimized build.  So yes, I'm using unoptimized builds quite a lot.

I use an optimised build for running and debugging at the Lisp level.
Occasionally I need C debugging, and so run in an "ordinary" debugging
build (3 times as slow) on these occasions.  I think I've only once or
twice needed a super-slow build (with --with-enable-checking=all) for
debugging.

My question was to enquire as to whether you actually really need the 10x
as slow build most of the time, or whether the normal 3x as slow (normal
debugging) build or even an optimised build would suffice most of the
time.

> > > For example, just visiting dce_12_0_sh_mask.h file takes a whopping
> > > 67 sec, and M-> immediately after the file is displayed takes
> > > another 25 sec.  With c-ts-mode, these numbers are, respectively,
> > > 1.8 sec and 2 sec.

> > Yes.  I saw pretty much the same in my pessimised build.  In a normal
> > build, these operation are ~10 times as fast.  Also we're all agreed
> > dce_12_0_sh_mask.h is an unusual file, both in its content and its
> > size.

> If it is an unusual file, why did you report the slow scrolling through
> it as a bug?  We need to be consistent: either that file is legitimate
> and Emacs should work reasonably fast with it, or it isn't.

It is both an unusual file (so unusual behaviour might be expected in
Emacs with it) and fully legitimate (so Emacs should handle it with times
for scrolling operations measured in seconds, not minutes).  Up until
Yuan fixed c-ts-mode, its scrolling was indeed measured in minutes.  The
bug was legitimate, and the fix is good.

[ .... ]

> > > Speed is not the main reason why we want to have font-lock and
> > > indentation based on a parser library.  The main reason is
> > > _correctness_ and _accuracy_.  A regexp-based fontification and
> > > indentation engines will never be able to match parser-based
> > > engines, because they doesn't really understand the source code.

> > Given the current CC Mode, any increase in correctness is going to be
> > marginal, if apparent at all.

> I disagree.  Both C and C++ are still evolving, and their syntax and
> semantics don't become simpler.  People post bug reports against CC
> Mode which involve some tricky syntactical constructs all the time.

Yes.  It remains to be seen if the tree-sitter grammars handle these
unusual constructs effortlessly.  I somehow suspect it won't be as simple
as all that.  Yuan has already raised a bug in the C grammar where it
doesn't handle packet-rrc.c correctly.

> Our current font-lock is just a huge collection of ad-hocery, and
> there's a limit to what we can do with ad-hoc code.  Personally, I
> think this is an evolutionary dead end.  It was acceptable years ago,
> when the incremental parsing technology was not developed enough
> and/or not accessible easily enough.

We're in violent agreement, here.  ;-)

[ .... ]

-- 
Alan Mackenzie (Nuremberg, Germany).

bug#59738: c-ts-mode is slow with large buffers.

[Eli Zaretskii]

> Date: Sun, 11 Dec 2022 18:39:46 +0000
> Cc: casouri@gmail.com, 59738@debbugs.gnu.org, acm@muc.de
> From: Alan Mackenzie <acm@muc.de>
> 
> > It is impossible to debug Emacs efficiently on the C level using the
> > optimized build.  So yes, I'm using unoptimized builds quite a lot.
> 
> I use an optimised build for running and debugging at the Lisp level.
> Occasionally I need C debugging, and so run in an "ordinary" debugging
> build (3 times as slow) on these occasions.  I think I've only once or
> twice needed a super-slow build (with --with-enable-checking=all) for
> debugging.
> 
> My question was to enquire as to whether you actually really need the 10x
> as slow build most of the time, or whether the normal 3x as slow (normal
> debugging) build or even an optimised build would suffice most of the
> time.

I gave you my answer, based on many hours of debugging hard problem
and on a lot of gray hair.  Debugging optimized code is unreliable, at
least with GCC and GDB.  There are tricky bugs whose debugging
requires setting up complex traps and sophisticated breakpoint
conditions.  It takes time to find these tricks, and even a single
variable which is "optimized out" or a call to a function that cannot
be stepped into due to inlining and moving code around can ruin a long
and frustrating debugging session.  I cannot afford wasting my time
that way.

That the DWARF data generated by GCC is either not expressive enough
to tell the whole story, or GDB is not smart enough to interpret it,
is IMNSHO the greatest disaster that happened to the GNU Project.  Why
The Powers That Be don't consider it a grave problem, I cannot
imagine.  I'm old enough to remember that with GCC 2.7.2 I used to
debug optimized programs without any problems -- and it was a welcome
feature that made GCC stand out compared to the other compilers back
then, with which you simply couldn't debug optimized code.

> > I disagree.  Both C and C++ are still evolving, and their syntax and
> > semantics don't become simpler.  People post bug reports against CC
> > Mode which involve some tricky syntactical constructs all the time.
> 
> Yes.  It remains to be seen if the tree-sitter grammars handle these
> unusual constructs effortlessly.  I somehow suspect it won't be as simple
> as all that.  Yuan has already raised a bug in the C grammar where it
> doesn't handle packet-rrc.c correctly.

If this proves to be a serious problem, eventually someone on our team
will start making changes in the grammar files.  It isn't rocket
science, after all, given that the parsing itself is done elsewhere.

bug#59738: c-ts-mode is slow with large buffers.

[Stefan Kangas]

Alan Mackenzie <acm@muc.de> writes:

> The bug which was causing it to be very slow is fixed, so I agree,
> excellent job!

Could this bug therefore be closed, or is there more to do here?

bug#59738: c-ts-mode is slow with large buffers.

[Yuan Fu]

Stefan Kangas <stefankangas@gmail.com> writes:

> Alan Mackenzie <acm@muc.de> writes:
>
>> The bug which was causing it to be very slow is fixed, so I agree,
>> excellent job!
>
> Could this bug therefore be closed, or is there more to do here?

This probably can be closed, so I’m closing it.

Yuan