From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Yuan Fu Newsgroups: gmane.emacs.devel Subject: Re: Tree-sitter navigation time grows as sqrt(line-number) Date: Mon, 21 Aug 2023 18:41:16 -0700 Message-ID: <48CD64C5-CC2A-42C5-8496-33B188497B99@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> Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3731.600.7\)) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="20391"; mail-complaints-to="usenet@ciao.gmane.io" Cc: JD Smith , emacs-devel@gnu.org To: Dmitry Gutov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Aug 22 03:42:16 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 1qYGPQ-00057q-D2 for ged-emacs-devel@m.gmane-mx.org; Tue, 22 Aug 2023 03:42:16 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qYGOj-0001lD-KD; Mon, 21 Aug 2023 21:41:33 -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 1qYGOi-0001kg-Fv for emacs-devel@gnu.org; Mon, 21 Aug 2023 21:41:32 -0400 Original-Received: from mail-oi1-x235.google.com ([2607:f8b0:4864:20::235]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qYGOg-00079J-5e for emacs-devel@gnu.org; Mon, 21 Aug 2023 21:41:32 -0400 Original-Received: by mail-oi1-x235.google.com with SMTP id 5614622812f47-3a85cc7304fso961462b6e.1 for ; Mon, 21 Aug 2023 18:41:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1692668488; x=1693273288; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=XOKl8X0IEQN6alY7p1Nr7zYNCpj2LUFvqO0a2kABLHY=; b=DwOGQ5PKloHHIhajz5GxRh83bZL4qAFcGHab3AFSzWjZDvGiVVWgpJR1HqyCTrho4w n9JYChUiy+r1ZIk186431zLPZfO/RXHd/6u+AYH5/RXB47Nalk0IHDh6Z0961FGJfM77 4MrL7Txb0pFPya1wUBtyGRuqXZNS3zZPWwVft9S6JRpQZgONTHDeeVZnX9eT5ynq9c8H DSVTUvubqztuKE/yOvGstRytWuWXXK6OMLlWBih6IFQFbi8OEkf1UJiXIWLgtnfcE5Xn SS5I71o3Wz9tu6Zz/FgeNXOaXa4YSRgHeanjLvPUQ3HRy8vdbKfNWCN1P5WoMJEq8hjg WJ0Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692668488; x=1693273288; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=XOKl8X0IEQN6alY7p1Nr7zYNCpj2LUFvqO0a2kABLHY=; b=f5QbWyoJ3yBitAw+eP/a1oEIryaTYQg326sDzbldVpGULEQdFVUHRSxORLQcffufQn a+e/nUzXaYPdo06/83LX2qsPGp/bI1FkuJ5FnX60jz8wsreC5Jvi1AmIdB/lAEhfLUT5 qKbb0c5hKfkl2O6MA0DhhitAO8GNVaavdf6mb0CBhjpdUjWhfOnHz/0w02Z7oTq0R1EU vTnPfIuZJTiMeZxkCBMX/hnVygrkDJdfVLaraaY3mbvOqcENke4AMBbwONe38lnnW43v cQt/oPOd4tZJlS2Qg6HpS36F/ibWHVu8SfmrDKN07yYSQzc9oAmgkrC2PcxC1FymRR1Z v1tA== X-Gm-Message-State: AOJu0YwJrijM99dIu+FI/iRLndM37yL0OLwqB/6zS9G1XDroYSHR++1S XhnM6U/mO38M2jBZY8xz+F4= X-Google-Smtp-Source: AGHT+IHpjXspq+dPFyohq3vcuKf1r/u/h+tBXv/2ggfzZdr5pL7Lvi9vjCjuOQxD5fu8GF1aDPa+SQ== X-Received: by 2002:a05:6358:9910:b0:139:e766:5cbd with SMTP id w16-20020a056358991000b00139e7665cbdmr5643759rwa.32.1692668488409; Mon, 21 Aug 2023 18:41:28 -0700 (PDT) Original-Received: from smtpclient.apple (cpe-172-117-161-177.socal.res.rr.com. [172.117.161.177]) by smtp.gmail.com with ESMTPSA id h27-20020a63385b000000b0056c466b09a4sm1172896pgn.59.2023.08.21.18.41.27 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 21 Aug 2023 18:41:27 -0700 (PDT) In-Reply-To: X-Mailer: Apple Mail (2.3731.600.7) Received-SPF: pass client-ip=2607:f8b0:4864:20::235; envelope-from=casouri@gmail.com; helo=mail-oi1-x235.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, 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:309100 Archived-At: > On Aug 20, 2023, at 1:26 PM, Dmitry Gutov wrote: >=20 > On 20/08/2023 15:40, JD Smith wrote: >> Looks like a winner (see below, or the gist)! Thanks all. >=20 > Same here, thanks all indeed. Let=E2=80=99s run with this patch for sometime. If all goes well, I=E2=80=99= ll push to emacs-29.=20 >=20 >> I do think we should consider a treesit-node-ancestors function that = collects all the parent (of parent) nodes in one go into an (emacs) = list, since you basically have to descend the whole tree from root to = find the 1st parent anyway. Then people who want to know, e.g., =E2=80=9C= am I in an if block?=E2=80=9D can just test node type down the full = ancestor list. Of course, also, node-parent-until/while could be = re-written to use node-ancestors, for some additional efficiency. >=20 > Should be useful, but the speedup from traversing only once might be = negated by the work of allocating the full list of Lisp objects. So it = might improve only certain applications. >=20 > OTOH, node-parent-until/while could be rewritten in a way that only = allocates Lisp on-demand. Yeah, node-parent is already fast, and a tree=E2=80=99s height mostly = doesn=E2=80=99t grow higher than, say, 30 levels, so I won=E2=80=99t = worry about it until some real scenario pops up. Yuan=