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: treesitter local parser: huge slowdown and memory usage in a long file Date: Mon, 13 May 2024 02:44:31 +0300 Message-ID: References: <2DB11528-C657-4AC1-A143-A13B1EAC897A@gmail.com> <0132CFC2-CFA0-4D58-9632-6E6E03FE57DB@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2000"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla Thunderbird Cc: "Ergus via Emacs development discussions." To: Yuan Fu Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon May 13 01:45:26 2024 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 1s6Ise-0000Ha-6A for ged-emacs-devel@m.gmane-mx.org; Mon, 13 May 2024 01:45:25 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1s6Irz-0006QZ-TG; Sun, 12 May 2024 19:44:43 -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 1s6Irx-0006QB-Tp for emacs-devel@gnu.org; Sun, 12 May 2024 19:44:41 -0400 Original-Received: from wfhigh8-smtp.messagingengine.com ([64.147.123.159]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1s6Iru-00048Z-Tk for emacs-devel@gnu.org; Sun, 12 May 2024 19:44:40 -0400 Original-Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailfhigh.west.internal (Postfix) with ESMTP id F2B071800084; Sun, 12 May 2024 19:44:34 -0400 (EDT) Original-Received: from mailfrontend2 ([10.202.2.163]) by compute7.internal (MEProxy); Sun, 12 May 2024 19:44:35 -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:subject:subject:to:to; s=fm2; t=1715557474; x=1715643874; bh=UOndqG27oAokaERXd8sTbKqXd6UBbAg3B7yw+swd25w=; b= KJQJpfnNc03jC9sf8Hu9bFsZlZYpXDjyQ+IGlv/V8ZsR56//Mr1U1aBDxyEtq13T TZ62c09YbqWQKaYDzwwLFvesT7PeCyJ05iXaCXYy1aofikCtjTYWIxl864mka9PR PCBmvnWItuikyg16oaTwRV+VnVhyzSXzr9PyGVjZhoXSn2i7FkmLzPojWQKaUA53 nZS20/Y1S1zh8rEoUTNJid7b4yDSWIRhfY1SaFQnVOJhhkazYa7b/tdKYdn5uaEj qouCPuI3Zw+Yf3XbjbKNv1tECsHvE4f59rmYhMVdj+Pt4GuCCFas0hiQt43ERCTg pQIpVmGe/j5U2dil+QFPAA== 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:subject:subject:to:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm3; t=1715557474; x= 1715643874; bh=UOndqG27oAokaERXd8sTbKqXd6UBbAg3B7yw+swd25w=; b=H S1c5vEz6eSIUgeXCcW+jenv/PbZl+PmX7CNrhQ3SEUfzjXWl7OOnm7slKPsn0n9Y PitYCpRZYnXxZXEa83keNZOXPGbbHgSBu4L/A9RogufbWi5Zs5i3wIK59p/UvLB1 50/azYcZhWxIep86NpHhHaGzUt1vyZZSkVot1uH+sbTtmgWKcaamTbf/ZAKcAMz0 a8zqkUYg84+k1BBvz8P8JUjO/g/mJJB+QCMiTunsyFa3ANgxtsDVt13BbloIAssh 0cyTq80B1mLttag6XOKQrJbPymWHEvjHS7d1xdNAL3TPlqnxL7hRgaYgVpo540DF CPjjsdDNKbTlHZIhF4b1w== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrvdegfedgvdeiucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepkfffgggfuffvvehfhfgjtgfgsehtkeertddtvdejnecuhfhrohhmpeffmhhi thhrhicuifhuthhovhcuoegumhhithhrhiesghhuthhovhdruggvvheqnecuggftrfgrth htvghrnhepgeelfeetkefghfdvhfdtgeevveevteetgeetveegtedthefhudekteehffeu keeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepug hmihhtrhihsehguhhtohhvrdguvghv X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Sun, 12 May 2024 19:44:33 -0400 (EDT) Content-Language: en-US In-Reply-To: <0132CFC2-CFA0-4D58-9632-6E6E03FE57DB@gmail.com> Received-SPF: pass client-ip=64.147.123.159; envelope-from=dmitry@gutov.dev; helo=wfhigh8-smtp.messagingengine.com X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 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, 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:319194 Archived-At: On 09/05/2024 03:16, Yuan Fu wrote: >> Is it possible that there would occur multiple changes and reparses between some firings of the above hooks? For example, some new feature might go over the buffer's text with an automated multi-step transformation, calling the parser (but not syntax-ppss) on each step. >> In such a scenario it seems treesit--pre-redisplay might miss intermediate range updates. Would that be okay? > > I think you’re right. The chance of it actually go wrong will be slim, but anything that’s possible to go wrong will eventually go wrong. Thanks for confirming the concern. > The remaining question is how. I’m thinking of keeping a history of updated ranges, each marked with the parser timestamp. The parser timestamp is already there, it’s incremented every time the parser reparses. And treesit-parser-changed-ranges will return the timestamp along with the updated ranges. Then in the next iteration, the consumer can pass the last timestamp to treesit-parser-changed-ranges, which tells it to return all the changed ranges since that timestamp. > > The only problem is to decide how long a history of updated ranges do we keep for each parser. The 100% correct approach is to maintain a separate history for each consumer, and never throw away old ranges until the consumer consumes them. But then you risk wasting memory if some consumer never consumes the ranges. To handle that we can add a hard limit. But then this hard limit might be too low for some edge case… We can make this hard limit configurable, and if we ever encountered a case where this hard limit is not enough and there’s no way around it (unlikely), we can instruct users or lisp program to increase it. That could work. Although it's hard for me to imagine how far back the history would have to be stored, and would that have any practical consequences for Emacs's memory use. Maybe not. The approach I was thinking of is in different direction: we take a step back, remove (or stop using at least) the new function, and go back to the idea of subscribing to parsers' after-change notifiers. The improvement in commit f62c1b4cd00 seems to stem from relying foremost on changes ranges in the primary parser. Okay - we re-add the listener for the primary parser only. This listener would be specific for a particular consumer. In our case, we'd have a listener which would populate - and then update - the variable used by treesit--pre-redisplay. That variable would store the "up to date" list of updated ranges. The listener, on every call, would "merge" its current value one with the new list of ranges (*). treesit--pre-redisplay would use the data in that data structure instead of calling treesit-parser-changed-ranges, and set the value to nil to "reset" it for the next update. (*) So real "merging" would only need to be performed when listener fires 2+ times between the two adjacent treesit--pre-redisplay calls. Otherwise the current value is nil, so the the new list is simply assigned to the variable. Anyway, the merging logic seems to be the trickiest part in this scheme (managing and interpreting offsets), but it should be very similar in both approaches.