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

[Yuan Fu]

> 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
Description: Binary data