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

[JD Smith <jdtsmith@gmail.com>]

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>