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

[Yuan Fu <casouri@gmail.com>]

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



> On Aug 19, 2023, at 7:24 AM, JD Smith <jdtsmith@gmail.com> wrote:
> 
> Thanks for your patch, Dmitry.  I had a chance to test it this morning (the new, non-crashing version).  I made a new NS build, with and without the patch.  The results are really striking (scroll to bottom):
> 
>  https://gist.github.com/jdtsmith/7fa6263a13559d587abb51827e6ae472
> 
> Summary:
> 
> - Applying the same test above on _axes.py reproduces the earlier emacs-mac/29 results: the time to navigate from the node at line beginning to root starts at under 10µs, but rises as sqrt(N) by ~100x, reaching over 3000µs.
> 
> - With Dimitry’s patch, it performs much, much better, starting off with similar timing at early positions in the file, but rising no higher than 50µs, scaling much shallower than sqrt(N).
> 
> I should emphasize this is a new fast machine; I fully expect my old laptop would be much slower (10x ?) than 3ms in files this large, which makes using parent navigation for things like font-lock problematic.
> 
> The patched version results also make a lot more sense in terms of their similar logarithmic growth as node-at-point, since the method of search for a node at point and for its parent is, as Yuan points at, quite similar.

I inspected the descending algorithm, and there’s indeed an oversight made by me. Here’s a patch that should fix it. I tested it briefly and it does speeds things up greatly. Thanks for investigating this, JD!

I think the patch is relatively safe, so maybe we can push it to emacs-29 instead of master.

Yuan


[-- Attachment #2: node-parent.patch --]
[-- Type: application/octet-stream, Size: 1088 bytes --]

From dd20c4449493765c22dd2067ae410490e9f1d1dc Mon Sep 17 00:00:00 2001
From: Yuan Fu <casouri@gmail.com>
Date: Sat, 19 Aug 2023 15:04:20 -0700
Subject: [PATCH] Fix treesit_cursor_helper_1

* src/treesit.c (treesit_cursor_helper_1): Skip child nodes that can't
contain TARGET when traversing the tree: only traverse down the child
node if that node's end is grater or equal to TARGET's end.
---
 src/treesit.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/treesit.c b/src/treesit.c
index 1f694e47201..f9e98244a4f 100644
--- a/src/treesit.c
+++ b/src/treesit.c
@@ -3048,7 +3048,8 @@ treesit_cursor_helper_1 (TSTreeCursor *cursor, TSNode *target,
      siblings that could contain TARGET.  */
   while (ts_node_start_byte (cursor_node) <= end_pos)
     {
-      if (treesit_cursor_helper_1 (cursor, target, end_pos, limit - 1))
+      if (ts_node_end_byte (cursor_node) >= end_pos
+	  && treesit_cursor_helper_1 (cursor, target, end_pos, limit - 1))
 	return true;
 
       if (!ts_tree_cursor_goto_next_sibling (cursor))
-- 
2.41.0