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

[JD Smith]

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?  May be worth looking at how others are doing it, e.g. the python 
API.  

Alternatively, have we ruled the seemingly simplest node_parent out 
prematurely?  If the issue is a node being its own parent in some odd trees, 
wouldn’t a simple check suffice to guard against this rare possibility?

> On Aug 19, 2023, at 6:16 PM, Yuan Fu <casouri@gmail.com> wrote:
> 
> 
> 
>> 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>