From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.devel Subject: Re: Tree-sitter navigation time grows as sqrt(line-number) Date: Thu, 31 Aug 2023 20:32:30 +0300 Message-ID: <2a8bbb32-4f64-9b0a-dd7f-c4d4d0628bba@gutov.dev> 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> <875y4vsait.fsf@yahoo.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="35069"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 Cc: Eli Zaretskii , Yuan Fu , jdtsmith@gmail.com, emacs-devel@gnu.org To: Po Lu Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Aug 31 19:33:40 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 1qblY3-0008t7-1r for ged-emacs-devel@m.gmane-mx.org; Thu, 31 Aug 2023 19:33:39 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qblX6-0004Xu-4s; Thu, 31 Aug 2023 13:32:40 -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 1qblX2-0004XZ-A9 for emacs-devel@gnu.org; Thu, 31 Aug 2023 13:32:36 -0400 Original-Received: from out3-smtp.messagingengine.com ([66.111.4.27]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qblX0-0003rI-2L; Thu, 31 Aug 2023 13:32:35 -0400 Original-Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.nyi.internal (Postfix) with ESMTP id CFA815C008F; Thu, 31 Aug 2023 13:32:32 -0400 (EDT) Original-Received: from mailfrontend1 ([10.202.2.162]) by compute5.internal (MEProxy); Thu, 31 Aug 2023 13:32:32 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gutov.dev; h=cc :cc:content-transfer-encoding:content-type:content-type:date :date:from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to; s=fm3; t= 1693503152; x=1693589552; bh=4XI36v8yDlpyxtbdUhkaru+ySuAw0sim4T+ SZ0kMmWI=; b=O6jGwdAfu6ObGpFBDPzdTmRaPW/66+nfyxElMPKYBJxepbafnyl 0eNMEg0l1FVqhESupQ12C7j7U99TfKY8Kz9M3xKLVS7rLrFMsFms55lDjr13s/Tt d+1TyPw8Gj7q2HFdjz2Fxw7Gf2c95NAYb+UYtEDPyKl/FhhPz7uN1qQH1kTPRMHA Ze6Tz42yPmHXiHKQmcLQQLS1tqoS5O0A5O0hS/73NscLtwWgNGd/NvXKhfPDWzd3 WvbSV/IvW/RQwKort1l3gkuts9leoOakNaggciNOl7MPYRANmh1avRhf2G6cfKuj JWOmQOawE5mx6bKlX9/Fj2tzgnW66oCv4Vg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:content-type:date:date:feedback-id:feedback-id :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t= 1693503152; x=1693589552; bh=4XI36v8yDlpyxtbdUhkaru+ySuAw0sim4T+ SZ0kMmWI=; b=jkw5XjNLpiGn5eYiyQ0Kl8OX+rPTYsCgeUzPirElb26Uyulb+h+ hrTIb+sy8BSdSA+H2oAz9PsHJIV1OQMqhri/r+mNafJ4aCb+ZxQLAV2BS0wXyBAb UqpxtNASt4HRsXAZiOteQpFkljgJaolXOX5wONdGxpc9M8j0odtEWLgShfswhNg+ EfUzsZfk44ALLaU9T6+jNDwtmjiCzBlpzn/QT+GYhr6SKzl9c9umK0/1LJLFQMaK s9pqTXdObpSPVrm7PsnDAm7PfE+OJzgyoJKZtod1RUH9hpbqh+fUVKXVN1G9NEQl zGAy+20SLXujaop1bWZ3L4Sg0J7cPVJ0TZg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedviedrudegtddguddugecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpefkffggfgfuvfevfhfhjggtgfesthejredttdefjeenucfhrhhomhepffhm ihhtrhihucfiuhhtohhvuceoughmihhtrhihsehguhhtohhvrdguvghvqeenucggtffrrg htthgvrhhnpeeigfetveehveevffehledtueekieeikeeufeegudfgfeeghfdulefgfeev ledvveenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpe gumhhithhrhiesghhuthhovhdruggvvh X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 31 Aug 2023 13:32:31 -0400 (EDT) Content-Language: en-US In-Reply-To: <875y4vsait.fsf@yahoo.com> Received-SPF: pass client-ip=66.111.4.27; envelope-from=dmitry@gutov.dev; helo=out3-smtp.messagingengine.com X-Spam_score_int: -62 X-Spam_score: -6.3 X-Spam_bar: ------ X-Spam_report: (-6.3 / 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, NICE_REPLY_A=-3.478, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_PASS=-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:309686 Archived-At: On 31/08/2023 14:42, Po Lu wrote: > Dmitry Gutov writes: > >> Depending on the POV, O(N^2) performance for certain buffer >> interactions can be considered a bug. > But is fixing it is worth the risk? Is the change innocuous enough for > the release branch? It seems so, yes. The change doesn't increase code complexity, and rather fixes an omission where many nodes weren't outright filtered out during the search. Also, as JD said, packages using tree-sitter are going to be constrained by the lower common denominator of the primitives' performance characteristics. At least some of those will be able to recommend 29.2 (or put it as a dependency).