unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Tree-sitter navigation time grows as sqrt(line-number)
@ 2023-08-17  4:01 JD Smith
  2023-08-17 10:56 ` Dmitry Gutov
  2023-08-18  3:00 ` Yuan Fu
  0 siblings, 2 replies; 40+ messages in thread
From: JD Smith @ 2023-08-17  4:01 UTC (permalink / raw)
  To: emacs-devel

[-- Attachment #1: Type: text/plain, Size: 1240 bytes --]

I recently posted about the high variability of Emacs 29’s tree-sitter navigation performance within a file.  I decided to conduct a simple test on a large python file of about 8400 lines to see if I could learn more.  The test is as follows: at the start of each line, locate the current syntax node, and starting from it, navigate up to the root node via `treesit-node-parent’.  

I was surprised to find that the time this takes grows as sqrt(N), for line number N.  This leads to performance variability of >100x for code that needs to walk the local syntax tree in large files.  Such variability can make performance projections and optimizations for latency-sensitive uses of tree-sitter (e.g. via font-lock) tricky.  

I’m unclear whether this is fundamental to the tree-sitter parse/tree algorithm, or if the scaling comes from Emacs’ TS implementation.  It does vaguely remind me of similar scaling with an old line-numbering algorithm, where lines were always being counted from the beginning of the buffer, so very fast at the front, and very slow near the end. 

Code and details here:

  https://gist.github.com/jdtsmith/7fa6263a13559d587abb51827e6ae472
tree-sitter navigation speed test
gist.github.com
	

[-- Attachment #2.1: Type: text/html, Size: 4250 bytes --]

[-- Attachment #2.2: gist-og-image.png --]
[-- Type: image/png, Size: 36122 bytes --]

^ permalink raw reply	[flat|nested] 40+ messages in thread
[parent not found: <87v8ddsqwe.fsf@web.de>]

end of thread, other threads:[~2023-09-01  5:33 UTC | newest]

Thread overview: 40+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-08-17  4:01 Tree-sitter navigation time grows as sqrt(line-number) JD Smith
2023-08-17 10:56 ` Dmitry Gutov
2023-08-17 11:41   ` Eli Zaretskii
2023-08-17 11:51     ` tomas
2023-08-17 12:21   ` JD Smith
2023-08-17 12:34     ` Dmitry Gutov
2023-08-17 13:19       ` Dmitry Gutov
2023-08-19 14:24         ` JD Smith
2023-08-19 22:16           ` Yuan Fu
2023-08-20  0:18             ` JD Smith
2023-08-20  0:39               ` Dmitry Gutov
2023-08-20  2:01                 ` Yuan Fu
2023-08-20 12:40                   ` JD Smith
2023-08-20 20:26                     ` Dmitry Gutov
2023-08-22  1:41                       ` Yuan Fu
2023-08-22 21:07                         ` JD Smith
2023-08-31  4:26                           ` Yuan Fu
2023-08-31  6:03                             ` Eli Zaretskii
2023-08-31 11:04                               ` Dmitry Gutov
2023-08-31 11:42                                 ` Po Lu
2023-08-31 17:32                                   ` Dmitry Gutov
2023-08-31 12:51                                 ` Eli Zaretskii
2023-08-31 13:58                                   ` JD Smith
2023-08-31 17:49                                   ` Dmitry Gutov
2023-08-31 19:03                               ` Yuan Fu
2023-08-31 19:06                                 ` Eli Zaretskii
2023-08-31 20:24                                   ` Stefan Kangas
2023-09-01  5:33                                     ` Eli Zaretskii
2023-08-20  6:18             ` Eli Zaretskii
2023-08-18  3:00 ` Yuan Fu
2023-08-18  4:19   ` JD Smith
2023-08-18  5:20     ` Yuan Fu
2023-08-18 13:21       ` Dmitry Gutov
2023-08-18 13:39       ` JD Smith
     [not found] <87v8ddsqwe.fsf@web.de>
2023-08-17 14:25 ` Dmitry Gutov
2023-08-17 14:36   ` Dmitry Gutov
2023-08-17 15:01     ` Dmitry Gutov
2023-08-17 15:15       ` Felix
2023-08-18  2:49         ` Yuan Fu
2023-08-18 13:29           ` Dmitry Gutov

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).