> 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