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

[Dmitry Gutov]

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.