From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: JD Smith Newsgroups: gmane.emacs.devel Subject: Re: Tree-sitter navigation time grows as sqrt(line-number) Date: Thu, 31 Aug 2023 09:58:12 -0400 Message-ID: <83A6A7B3-9944-4E1D-8714-BA2675409ABB@gmail.com> References: <3E82D409-6903-4679-9031-939CA35791FF@gmail.com> <32507689-3b2c-ccbf-dd14-e7bf0bed1ac7@gutov.dev> <6db52945-5459-197c-405d-153ff395a824@gutov.dev> <1F7C956D-6D22-4CC1-8656-6E2A4D07D5FB@gmail.com> <69D18963-D94F-4792-9FF1-159897A99E50@gmail.com> <48CD64C5-CC2A-42C5-8496-33B188497B99@gmail.com> <831qfjg34v.fsf@gnu.org> <209683e1-be9d-f112-40e2-34ea2ffd5ed9@gutov.dev> <834jkfe5oh.fsf@gnu.org> Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3731.700.6\)) Content-Type: multipart/alternative; boundary="Apple-Mail=_15992026-EE10-45A0-BBAF-AE7949D0E5F4" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="16914"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Dmitry Gutov , Yuan Fu , emacs-devel@gnu.org, mickey@masteringemacs.org To: Eli Zaretskii , Stefan Kangas Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Aug 31 15:58:53 2023 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qbiCD-0004DX-5c for ged-emacs-devel@m.gmane-mx.org; Thu, 31 Aug 2023 15:58:53 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qbiBu-0006GN-Jr; Thu, 31 Aug 2023 09:58:34 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qbiBs-00066x-Uv for emacs-devel@gnu.org; Thu, 31 Aug 2023 09:58:32 -0400 Original-Received: from mail-yw1-x1135.google.com ([2607:f8b0:4864:20::1135]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qbiBo-0007Ir-5i; Thu, 31 Aug 2023 09:58:31 -0400 Original-Received: by mail-yw1-x1135.google.com with SMTP id 00721157ae682-58dfe2d5b9aso10759747b3.1; Thu, 31 Aug 2023 06:58:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1693490305; x=1694095105; darn=gnu.org; h=references:to:cc:in-reply-to:date:subject:mime-version:message-id :from:from:to:cc:subject:date:message-id:reply-to; bh=xiQCBN1xb1jCdj05Of4Ccj0uarv9iqg/Ta3KC2LtxDg=; b=KphrT3KO4boLCYhPz/84MwtVuxXsr03LO3zVXwlTC07jK30/QJBjaYA2NaWA0yOsWH nSmd0LwYcuEcPwpvq7oDCKm9Hus+p6bqDJ78F90r8RA3pXLE5mYYC9zotzQUKnLglxGw 84S5co+cOJyYoRCztPCVJdBYcYL2/2KDhGfcRTHsZegDSARe60dOK0ArQip4p2HN/NBu pv3jtFV5IEE6mAeJHUcAS4hFWB/QbNluA6CtVnkOY6kP/BXP4yeJQVQu5ESt6a4HyegV vuIFeoLd29Ooa4ytZDq5hOoW60+gRxGQTgwtNbjuQk6jfv7zGcM6pehMxc4v9yWobTI0 R4Ag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693490305; x=1694095105; h=references:to:cc:in-reply-to:date:subject:mime-version:message-id :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=xiQCBN1xb1jCdj05Of4Ccj0uarv9iqg/Ta3KC2LtxDg=; b=A3XSyQTQ9mDuEvYMCiuU5SvOCvY2amcK1CLgIz8wMInWWNj0mR3fb/R+xJZVRoHvSX WKWcHvdU063DfVS3O8btjyEtNDSpDIRA71y2fsHVZ8/u2WrEvEcP8QTaySmqPjEE/fBG TTzdp80f4Ml22x/pG8qzGjAJzNdShSChxs2S/LD0NVquy+ovGjTLcETOhgS8ZbQeE5cs 9Z0c0FpH2GcHSDaqbkvfkqS+HvH0eZdcEMTZ0TI4Vl69MQx7gcKoh4V8ATivcTXEve2M EHHbPk4IAuHKIbAxDS8t17MptgLs7qEeuxHvNI9td15HXfWKLckflsErljt9QVBigCHX zlog== X-Gm-Message-State: AOJu0Yx2LKLKn8KpyHQ8DuH2HmhjwCwqDkChOqUdhfNFY/kgh8maPe+J vT+B67DieRsWIQHSHkgulBqGo2dAujMpCw== X-Google-Smtp-Source: AGHT+IG9NeJqGv+lNgE8fznbDqQ709TnsDPynEHtgOk6Sa+fgi8NjeCkqP+P9ycOVqG7t+vsyr+qeQ== X-Received: by 2002:a0d:dd54:0:b0:586:b0ad:18fa with SMTP id g81-20020a0ddd54000000b00586b0ad18famr2162079ywe.25.1693490305365; Thu, 31 Aug 2023 06:58:25 -0700 (PDT) Original-Received: from smtpclient.apple (cm-24-53-187-34.buckeyecom.net. [24.53.187.34]) by smtp.gmail.com with ESMTPSA id x184-20020a0deec1000000b00576c727498dsm426693ywe.92.2023.08.31.06.58.23 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 31 Aug 2023 06:58:24 -0700 (PDT) In-Reply-To: <834jkfe5oh.fsf@gnu.org> X-Mailer: Apple Mail (2.3731.700.6) Received-SPF: pass client-ip=2607:f8b0:4864:20::1135; envelope-from=jdtsmith@gmail.com; helo=mail-yw1-x1135.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:309668 Archived-At: --Apple-Mail=_15992026-EE10-45A0-BBAF-AE7949D0E5F4 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 The scale of the improvement is up to 100x. For me it has been on the = edge between =E2=80=9Cacceptable=E2=80=9D and =E2=80=9Cvery bad=E2=80=9D. = I have the impression that most modes are using treesit-query-capture = with compiled queries for performance-sensitive stuff (font lock), which = is fast, and hasn=E2=80=99t changed. So those shouldn=E2=80=99t be = affected.=20 But any tree-sitter modes developed over the next few years to respect = more =E2=80=9Ccontaining context=E2=80=9D (structural editing, = navigation, smarter context highlighting and folding, etc.) will I bet = first reach for treesit-node-parent and its friends = treesit-parent-while/until, as I did. For example, I believe = combobulate[1] is using these frequently (Mickey copied here). These = functions are up to 100x slower than necessary on long but still = reasonable (10k line) files. Is there a test harness somewhere that exercises treesit commands in = large buffers of various different languages? Perhaps a test could be = added to =E2=80=9Cnavigate up several generations=E2=80=9D from random = locations in the buffer and confirm the same nodes are reached. [1] https://github.com/mickeynp/combobulate > On Aug 31, 2023, at 8:51 AM, Eli Zaretskii wrote: >=20 >> Date: Thu, 31 Aug 2023 14:04:39 +0300 >> Cc: jdtsmith@gmail.com, emacs-devel@gnu.org >> From: Dmitry Gutov >>=20 >> On 31/08/2023 09:03, Eli Zaretskii wrote: >>> Thanks, but why emacs-29? Is this a bugfix? >>=20 >> Depending on the POV, O(N^2) performance for certain buffer = interactions=20 >> can be considered a bug. >=20 > Performance improvement is an enhancement. Unless the performance is > very bad, I don't think its place is on the release branch, especially > after the major release. >=20 > Stefan, WDYT? --Apple-Mail=_15992026-EE10-45A0-BBAF-AE7949D0E5F4 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 The scale of = the improvement is up to 100x.  For me it = has been on the edge between =E2=80=9Cacceptable=E2=80=9D and =E2=80=9Cver= y bad=E2=80=9D.  I have the impression that most modes are using = treesit-query-capture with compiled queries for performance-sensitive = stuff (font lock), which is fast, and hasn=E2=80=99t changed.  So = those shouldn=E2=80=99t be affected. 

But any tree-sitter modes developed over = the next few years to respect more =E2=80=9Ccontaining context=E2=80=9D = (structural editing, navigation, smarter context highlighting and = folding, etc.) will I bet first reach for treesit-node-parent and its = friends treesit-parent-while/until, as I did.  For example, I = believe combobulate[1] is using these frequently (Mickey copied here). =  These functions are up to 100x slower than necessary on long but = still reasonable (10k line) = files.

Is there a test harness = somewhere that exercises treesit commands in large buffers of various = different languages?  Perhaps a test could be added to =E2=80=9Cnavig= ate up several generations=E2=80=9D from random locations in the buffer = and confirm the same nodes are = reached.


On Aug = 31, 2023, at 8:51 AM, Eli Zaretskii <eliz@gnu.org> wrote:

Date: Thu, 31 Aug 2023 14:04:39 +0300
Cc: = jdtsmith@gmail.com, emacs-devel@gnu.org
From: Dmitry Gutov = <dmitry@gutov.dev>

On 31/08/2023 09:03, Eli Zaretskii = wrote:
Thanks, but why emacs-29?  Is = this a bugfix?

Depending on the POV, O(N^2) = performance for certain buffer interactions
can be considered a = bug.

Performance improvement is an enhancement. =  Unless the performance is
very bad, I don't think its place is = on the release branch, especially
after the major = release.

Stefan, = WDYT?

= --Apple-Mail=_15992026-EE10-45A0-BBAF-AE7949D0E5F4--