unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
From: JD Smith <jdtsmith@gmail.com>
To: emacs-devel@gnu.org
Subject: Tree-sitter navigation time grows as sqrt(line-number)
Date: Thu, 17 Aug 2023 00:01:34 -0400	[thread overview]
Message-ID: <3E82D409-6903-4679-9031-939CA35791FF@gmail.com> (raw)

[-- 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 --]

             reply	other threads:[~2023-08-17  4:01 UTC|newest]

Thread overview: 40+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-08-17  4:01 JD Smith [this message]
2023-08-17 10:56 ` Tree-sitter navigation time grows as sqrt(line-number) 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

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/emacs/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=3E82D409-6903-4679-9031-939CA35791FF@gmail.com \
    --to=jdtsmith@gmail.com \
    --cc=emacs-devel@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).