From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#58342: 29.0.50; noverlay branch is O(N) for important calls Date: Thu, 06 Oct 2022 21:12:26 -0400 Message-ID: References: <87edvkcz5v.fsf@rfc20.org> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2051"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: gerd.moellmann@gmail.com, 58342@debbugs.gnu.org, mail@andreas-politz.de, eliz@gnu.org To: Matt Armstrong Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Oct 07 03:13:22 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1ogbvV-0000LY-Sn for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 03:13:22 +0200 Original-Received: from localhost ([::1]:45884 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogbvU-0006Y2-PM for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 06 Oct 2022 21:13:20 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:60988) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogbvC-0006Xl-Al for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 21:13:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:34825) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogbvB-0002bZ-QC for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 21:13:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ogbvB-0003UW-LR for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 21:13:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 07 Oct 2022 01:13:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58342 X-GNU-PR-Package: emacs X-Debbugs-Original-Cc: Gerd =?UTF-8?Q?M=C3=B6llmann?= , bug-gnu-emacs@gnu.org, Andreas Politz , Eli Zaretskii Original-Received: via spool by submit@debbugs.gnu.org id=B.166510516313381 (code B ref -1); Fri, 07 Oct 2022 01:13:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 01:12:43 +0000 Original-Received: from localhost ([127.0.0.1]:33903 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogbus-0003Tl-RI for submit@debbugs.gnu.org; Thu, 06 Oct 2022 21:12:43 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:57728) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogbup-0003Ta-JL for submit@debbugs.gnu.org; Thu, 06 Oct 2022 21:12:42 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:50180) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogbup-0006WD-EB for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 21:12:39 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:3471) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogbum-0002ak-CZ; Thu, 06 Oct 2022 21:12:38 -0400 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 8A69E443621; Thu, 6 Oct 2022 21:12:34 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id B088A443620; Thu, 6 Oct 2022 21:12:28 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1665105148; bh=Tx/76iCCMjycETgDqe49lNhg7DFAOEuWDSMqf2TVPDY=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=Yu4zGrYVxLbB1cEgiPFBZbhfePzRE8TXzvcccNQnUIDfUbEt19LXVTTBebehQsAQb FXCv9WMn5sVCHt8p4wQ064dejLBM0FLOzmMGjDPCRzDK3MAbOhzxTxhz6VtOx8JZ/L U43pcprlAxtmjIyhWiWo5PP5YlrZlDfEAuov1ZM/UqhX5//nmEYoOSk2051gfgmszr ix/wAcdo8nhRNk3Pv31O/F7eujwhji/2tZ3/hNIK6YFK4KWN7JGn/1TwIE0eSON8ka 4E02jq7ZRN0uQy5aZri0ETwLFp84N4sEgy5as9daK+VoDYOTEJxGl6HI/MYmpQ7fof 6XDEmC1WyNWjw== Original-Received: from milanesa (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 6BDA812068A; Thu, 6 Oct 2022 21:12:28 -0400 (EDT) In-Reply-To: <87edvkcz5v.fsf@rfc20.org> (Matt Armstrong's message of "Thu, 06 Oct 2022 16:25:48 -0700") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:244725 Archived-At: > Here we traverse overlays in ASCENDING order of BEG positions. The best > we can say is that this loop executes in O(K*log(N)) time, where K is > the MIN of number of overlays that overlap POS and the number of valid The core operation in itree.c is the equivalent of `overlays-in/at`. It's considered OK if this takes O(N) where N is the number of overlays that are returned, since that's the best we can do. In practice itree.c takes a bit more than O(N) for that, there's an additional log(M) factor where M is the total number of overlays, but it's still overall significantly better at this operation than the old code which was O(M). In practice the expectation is that N is relatively small. Of course, we don't have any such guarantee, there might be cases where packages create many overlays each of which covers almost all the buffer. IIUC this situation is poorly handled both by the old and the new code, tho. Realistic benchmarks would be most welcome. [ Site note: `previous-overlay-change` is probably not very important in practice, but `next-overlay-change` OTOH is indeed important because it's used during redisplay. So if someone comes up with a trick to speed up only one direction, it should be good enough. ] Maybe one way to improve the behavior is to accept the worst-case bound but to try and avoid paying it over-and-over each time the redisplay needs the "next change". IOW instead of a `next_overlay_change` function which takes a POS and returns the next change after that, the xdisp.c might benefit from having a `next_overlay_changes` *generator* which takes a starting POS and returns an iterator which will return (each time it's called) the successive positions where there's an overlay change. Hopefully this way we'd pay the O(N) cost once per redisplayed window rather than once per "small step in the rendering engine" (i.e. per next_overlay_change). Another way to do basically the same is to let next_overlay_change fill up a cache of change-positions which would be flushed whenever some overlay is modified/added/removed (or the current_buffer is different from last time). That might be easier to use with the current code since xdisp.c wouldn't need to pass around this iterator (which could require significant reworks). Stefan