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

[JD Smith]

Thanks for your patch, Dmitry.  I had a chance to test it this morning (the 
new, non-crashing version).  I made a new NS build, with and without the patch. 
 The results are really striking (scroll to bottom):

  https://gist.github.com/jdtsmith/7fa6263a13559d587abb51827e6ae472

Summary:

- Applying the same test above on _axes.py reproduces the earlier emacs-mac/29 
results: the time to navigate from the node at line beginning to root starts at 
under 10µs, but rises as sqrt(N) by ~100x, reaching over 3000µs.

- With Dimitry’s patch, it performs much, much better, starting off with 
similar timing at early positions in the file, but rising no higher than 50µs, 
scaling much shallower than sqrt(N).

I should emphasize this is a new fast machine; I fully expect my old laptop 
would be much slower (10x ?) than 3ms in files this large, which makes using 
parent navigation for things like font-lock problematic.

The patched version results also make a lot more sense in terms of their 
similar logarithmic growth as node-at-point, since the method of search for a 
node at point and for its parent is, as Yuan points at, quite similar.