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