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 integration on feature/tree-sitter Date: Mon, 9 May 2022 13:51:46 -0700 Message-ID: <5F186EBD-CD21-422B-8B4F-0D5424173334@gmail.com> References: <87y1zabmbt.fsf@gmail.com> Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.80.82.1.1\)) 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="16937"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Yoav Marco Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon May 09 22:52:40 2022 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 1noAMx-0004Gk-9o for ged-emacs-devel@m.gmane-mx.org; Mon, 09 May 2022 22:52:39 +0200 Original-Received: from localhost ([::1]:52928 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1noAMw-0007mR-6L for ged-emacs-devel@m.gmane-mx.org; Mon, 09 May 2022 16:52:38 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:51056) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1noAMA-0006w8-Tk for emacs-devel@gnu.org; Mon, 09 May 2022 16:51:50 -0400 Original-Received: from mail-oa1-x2d.google.com ([2001:4860:4864:20::2d]:40021) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1noAM9-00045X-7z for emacs-devel@gnu.org; Mon, 09 May 2022 16:51:50 -0400 Original-Received: by mail-oa1-x2d.google.com with SMTP id 586e51a60fabf-d6e29fb3d7so16091688fac.7 for ; Mon, 09 May 2022 13:51:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=trESVT9JIeirlY2/uVAebV7+WMzEv9NPV0QlnyRHQtA=; b=bdjrIDQQOqplIWZqlNO2My7Z3q7sYV5qYjPLT3ra9vr497pVBF5+mtVWk05kzOt6Zr /frGV7u1BbMgn48Tnw/rqfZi0QxNTsGnOkC5+LBRW7k8a67o7yWIkaa2R71YIkb9WI30 6GsnQCkmIPSepT39PGvHmB5dQjHB8p920b98Zv048YF0nhur+PbYoWcWA2m2ABICKJ9A 6tzeCkLYkZFioBNRIVAJNykWYrPeHix0feMeEtj3LG+h5FuoXU5jdeuZupe+ZpNJKXAy yufcJ07df0rjyQKM3ahH1SJaBHn8q1HwDFWKlnwyVsKOcEWDbuTP+Rdj3Bn00WC4Vup0 Vq0A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=trESVT9JIeirlY2/uVAebV7+WMzEv9NPV0QlnyRHQtA=; b=RVZ/jpBy3BL8GwMZtV66jWUNQ2yfA+VwFGGygmp3TBS7bQPGoPy2bJSYc89EYY2EuQ wAdudxhbHoVQAm3zVAuJAPpLO20m6NgHZkXlDu3AbS0NqA02h8Ny4wkL9yrZWTbPTkIO UPd0CmNF5bWjXht/jv1wUV1ZNOiXFE+qqGmNUm3eW4/Yxc6lZdDcDmU4Ve4F2cF+Uqvf n4ZHDjT2iBY8mhmFDNDE1ptr3yarJLR5i1lFO2NwQ+fv1iDoUHnieNvPysrXjcmEJu47 i/D+qQIHdGHwlV8JeZdTfZ947gFIrNYawlhM30L+zYrEV6SoI4TEVy953jeBF5uO9/Yq 7G6A== X-Gm-Message-State: AOAM533FtNU4sqGnuYv/cdFqCcJSCstKFFNkZ/1cOncRnoHuiHfo2qKu Kwp2w8OXpumD6dPLfl6M+FqjVuikCjY= X-Google-Smtp-Source: ABdhPJzgtGNJOiSsylnYp2ItcYDiGDcK6lHOBSc+jfLz30kgy5ZfJPoTK6zh0lwGbstzygYf/k9Sbw== X-Received: by 2002:a05:6870:79a:b0:e9:109a:1391 with SMTP id en26-20020a056870079a00b000e9109a1391mr7962982oab.105.1652129507829; Mon, 09 May 2022 13:51:47 -0700 (PDT) Original-Received: from smtpclient.apple ([2600:1700:2ec7:8c90:45d2:2f3d:5494:d9ad]) by smtp.gmail.com with ESMTPSA id s43-20020a4a96ae000000b0035eb4e5a6cbsm5451031ooi.33.2022.05.09.13.51.46 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 09 May 2022 13:51:47 -0700 (PDT) In-Reply-To: <87y1zabmbt.fsf@gmail.com> X-Mailer: Apple Mail (2.3696.80.82.1.1) Received-SPF: pass client-ip=2001:4860:4864:20::2d; envelope-from=casouri@gmail.com; helo=mail-oa1-x2d.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, T_SCC_BODY_TEXT_LINE=-0.01 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" Xref: news.gmane.io gmane.emacs.devel:289549 Archived-At: > On May 9, 2022, at 10:50 AM, Yoav Marco wrote: >=20 > Looking at the code, isn't the while loop in treesit-query-capture > O(n=C2=B2)? It essentially amounts to >=20 > result =3D nil > while (next capture group is avaliable) { > captures =3D nil > for (capture in capture group) { > captures =3D cons(capture, captures) > } > captures =3D nreverse(captures) > if (captures pass all predicates in their query) > result =3D nconc(result, captures) // <----- THE OFFENDER > } >=20 > A better way to do this would be to call nconc(captures, result) and > nreverse it all at the end instead of at the end of the for loop. >=20 > An even faster way would be to add unconditionally to result and roll = it > back in case predicates fail. This doesn't use nconc at all: >=20 > result =3D nil > while (next capture group is avaliable) { > prev_result =3D result; > for (capture in capture group) { > result =3D cons(capture, result) > } > if (captures *fail* at a predicate) > result =3D prev_result > } > result =3D nreverse(result) >=20 >=20 > Context: I'm still working on profiling query compilation, and from = what > I understand of gprof's output (not much) nconc indeed is very slow > here. Seeing nconc in the report is what made me look for nconc usage = in > treesit-query-capture. >=20 > index % time self children called name > [1] 98.4 1.76 0.13 169+9031282 [1] > 1.59 0.00 41385 Fnconc [2] > 0.06 0.05 2432616+3714 process_mark_stack = [24] > 0.08 0.00 147643 re_match_2_internal = [25] > 0.02 0.00 1707+56214 mark_char_table [32] > 0.00 0.02 18 garbage_collect [33] > ... >=20 > The thing profiled is calling treesit-font-lock-fontify-region with c > queries accidentally on a go file with 8k lines. Still shouldn't take > the 2.2 seconds that it did, though. Thanks for looking at this! I pushed your proposed fix, could you try = your profile again and see if it works? >=20 >> BTW, I would appreciate for someone to look at the manual and maybe >> touch up a bit, as I=E2=80=99m not a native speaker and might write = something >> not very idiomatic/fluent. >=20 > One thing I've noticed - the manual node starts by introducing > treesit-available-p, a function that doesn't seem to exist anymore? It=E2=80=99s defined in treesit.el, have you required it before checking = for that function? Yuan