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

[Yuan Fu <casouri@gmail.com>]

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



> On Aug 19, 2023, at 5:39 PM, Dmitry Gutov <dmitry@gutov.dev> wrote:
> 
> On 20/08/2023 03:18, JD Smith wrote:
>> Great, thanks.  I tried this patch out, and there is indeed about 10x of improvement.  Check the bottom of the gist.  That said, node_parent remains 10x faster yet (at worst, in a long file), so maybe there’s room for further improvement?
> 
> Similarly, I also see an improvement from Yuan's patch in my testing (about 2x), while the patch with ts_node_parent remains the fastest anyway. Where my test looks like this:
> 
>  (benchmark 1000 '(treesit-node-parent n))
> 
> I looked around for the reasons for the difference. Built the latest tree-sitter (didn't help) and found these two threads on GH:
> 
> https://github.com/tree-sitter/tree-sitter/issues/567#issuecomment-595564171 - Max Brunsfield says "There is some caching done in that method to make sure it performs well in the common case of walking repeatedly up the tree", but I haven't found where said caching resides so far.
> 
> https://github.com/tree-sitter/tree-sitter/discussions/878 - mentions that mixing cursor and direct node apis leads to suboptimal results, and just using the former gives an improvement. No "good" code example in there.
> 
> >  May be worth looking at how others are doing it, e.g. the python API.
> 
> Apparently they have both a wrapper for a cursor API, and node_get_parent which is implemented using ts_node_parent: https://github.com/tree-sitter/py-tree-sitter/issues/34
> 
> Leaving it to the callers to choose which one to use.

Ok, I fiddled around a bit more, and this patch (applies to master) should make the speed comparable to ts_node_parent.

Yuan


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

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

* src/treesit.c: (treesit_cursor_helper_1): Use
ts_tree_cursor_goto_first_child_for_byte to speed up traversing among
siblings.  The "while (ts_node_end_byte (cursor_node) < end_pos)" can
be removed with the check added in the loop below.
---
 src/treesit.c | 22 +++++++++-------------
 1 file changed, 9 insertions(+), 13 deletions(-)

diff --git a/src/treesit.c b/src/treesit.c
index 1f694e47201..1017c64f899 100644
--- a/src/treesit.c
+++ b/src/treesit.c
@@ -3023,7 +3023,8 @@ treesit_assume_true (bool val)
    limit.  */
 static bool
 treesit_cursor_helper_1 (TSTreeCursor *cursor, TSNode *target,
-			 uint32_t end_pos, ptrdiff_t limit)
+			 uint32_t start_pos, uint32_t end_pos,
+			 ptrdiff_t limit)
 {
   if (limit <= 0)
     return false;
@@ -3032,23 +3033,17 @@ treesit_cursor_helper_1 (TSTreeCursor *cursor, TSNode *target,
   if (ts_node_eq (cursor_node, *target))
     return true;
 
-  if (!ts_tree_cursor_goto_first_child (cursor))
+  if (ts_tree_cursor_goto_first_child_for_byte (cursor, start_pos) == -1)
     return false;
 
-  /* Skip nodes that definitely don't contain TARGET.  */
-  while (ts_node_end_byte (cursor_node) < end_pos)
-    {
-      if (!ts_tree_cursor_goto_next_sibling (cursor))
-	break;
-      cursor_node = ts_tree_cursor_current_node (cursor);
-    }
-
   /* Go through each sibling that could contain TARGET.  Because of
      missing nodes (their width is 0), there could be multiple
      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, start_pos, end_pos,
+				      limit - 1))
 	return true;
 
       if (!ts_tree_cursor_goto_next_sibling (cursor))
@@ -3080,11 +3075,12 @@ treesit_cursor_helper_1 (TSTreeCursor *cursor, TSNode *target,
 static bool
 treesit_cursor_helper (TSTreeCursor *cursor, TSNode node, Lisp_Object parser)
 {
+  uint32_t start_pos = ts_node_start_byte (node);
   uint32_t end_pos = ts_node_end_byte (node);
   TSNode root = ts_tree_root_node (XTS_PARSER (parser)->tree);
   *cursor = ts_tree_cursor_new (root);
-  bool success = treesit_cursor_helper_1 (cursor, &node, end_pos,
-					  TREESIT_RECURSION_LIMIT);
+  bool success = treesit_cursor_helper_1 (cursor, &node, start_pos,
+					  end_pos, TREESIT_RECURSION_LIMIT);
   if (!success)
     ts_tree_cursor_delete (cursor);
   return success;
-- 
2.41.0


[-- Attachment #3: Type: text/plain, Size: 2 bytes --]