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

[JD Smith]

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.

> 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>
>