Re: Tree-sitter navigation time grows as sqrt(line-number)

[JD Smith <jdtsmith@gmail.com>]

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

The scale of the improvement is up to 100x.  For me it has been on the edge between “acceptable” and “very bad”.  I have the impression that most modes are using treesit-query-capture with compiled queries for performance-sensitive stuff (font lock), which is fast, and hasn’t changed.  So those shouldn’t be affected. 

But any tree-sitter modes developed over the next few years to respect more “containing context” (structural editing, navigation, smarter context highlighting and folding, etc.) will I bet first reach for treesit-node-parent and its friends treesit-parent-while/until, as I did.  For example, I believe combobulate[1] is using these frequently (Mickey copied here).  These functions are up to 100x slower than necessary on long but still reasonable (10k line) files.

Is there a test harness somewhere that exercises treesit commands in large buffers of various different languages?  Perhaps a test could be added to “navigate up several generations” from random locations in the buffer and confirm the same nodes are reached.

[1] https://github.com/mickeynp/combobulate

> On Aug 31, 2023, at 8:51 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> 
>> Date: Thu, 31 Aug 2023 14:04:39 +0300
>> Cc: jdtsmith@gmail.com, emacs-devel@gnu.org
>> From: Dmitry Gutov <dmitry@gutov.dev>
>> 
>> On 31/08/2023 09:03, Eli Zaretskii wrote:
>>> Thanks, but why emacs-29?  Is this a bugfix?
>> 
>> Depending on the POV, O(N^2) performance for certain buffer interactions 
>> can be considered a bug.
> 
> Performance improvement is an enhancement.  Unless the performance is
> very bad, I don't think its place is on the release branch, especially
> after the major release.
> 
> Stefan, WDYT?


[-- Attachment #2: Type: text/html, Size: 2496 bytes --]