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

[Yuan Fu]

> On Aug 19, 2023, at 7:24 AM, JD Smith <jdtsmith@gmail.com> wrote:
> 
> 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.

I inspected the descending algorithm, and there’s indeed an oversight made by 
me. Here’s a patch that should fix it. I tested it briefly and it does speeds 
things up greatly. Thanks for investigating this, JD!

I think the patch is relatively safe, so maybe we can push it to emacs-29 
instead of master.

Yuan

node-parent.patch
Description: Binary data