[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: JD Smith
Subject: Re: Tree-sitter navigation time grows as sqrt(line-number)
Date: Sat, 19 Aug 2023 10:24:12 -0400

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):



- 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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]