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

[JD Smith <jdtsmith@gmail.com>]

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

Looks like a winner (see below, or the gist)!  Thanks all.  

I do think we should consider a treesit-node-ancestors function that collects all the parent (of parent) nodes in one go into an (emacs) list, since you basically have to descend the whole tree from root to find the 1st parent anyway.   Then people who want to know, e.g., “am I in an if block?” can just test node type down the full ancestor list.  Of course, also, node-parent-until/while could be re-written to use node-ancestors, for some additional efficiency.


[-- Attachment #2: PastedGraphic-1.png --]
[-- Type: image/png, Size: 107148 bytes --]

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



> On Aug 19, 2023, at 10:01 PM, Yuan Fu <casouri@gmail.com> wrote:
> 
> 
> 
>> 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
> 
> <node-parent.patch>
>