From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Andreas Politz Newsgroups: gmane.emacs.bugs Subject: bug#58361: 29.0.50; noverlay branch is O(N) for important calls Date: Fri, 7 Oct 2022 18:51:14 +0200 Message-ID: References: <878rlrfyje.fsf@rfc20.org> Mime-Version: 1.0 (1.0) 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="24521"; mail-complaints-to="usenet@ciao.gmane.io" Cc: gerd.moellmann@gmail.com, 58361@debbugs.gnu.org, eliz@gnu.org, monnier@iro.umontreal.ca To: Matt Armstrong Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Oct 07 20:15:35 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 1ogrsk-0006DS-VO for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 20:15:35 +0200 Original-Received: from localhost ([::1]:33710 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogrsj-0003VJ-Bp for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 14:15:33 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:34282) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogrsF-0003V4-FJ for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 14:15:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38253) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogrsF-00072m-61 for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 14:15:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ogrsE-0001gI-Lp for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 14:15:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Andreas Politz Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 07 Oct 2022 18:15:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 58361 X-GNU-PR-Package: emacs X-Debbugs-Original-Cc: Gerd =?UTF-8?Q?M=C3=B6llmann?= , bug-gnu-emacs@gnu.org, Eli Zaretskii , Stefan Monnier Original-Received: via spool by submit@debbugs.gnu.org id=B.16651664816409 (code B ref -1); Fri, 07 Oct 2022 18:15:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 18:14:41 +0000 Original-Received: from localhost ([127.0.0.1]:37329 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogrrs-0001fH-PQ for submit@debbugs.gnu.org; Fri, 07 Oct 2022 14:14:41 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:49324) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogqZO-00085B-8m for submit@debbugs.gnu.org; Fri, 07 Oct 2022 12:51:30 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57950) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogqZN-0001pK-Nw for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 12:51:29 -0400 Original-Received: from mout.kundenserver.de ([212.227.126.130]:55023) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogqZK-00041N-PN; Fri, 07 Oct 2022 12:51:29 -0400 Original-Received: from smtpclient.apple ([77.181.178.184]) by mrelayeu.kundenserver.de (mreue012 [213.165.67.97]) with ESMTPSA (Nemesis) id 1MJnnV-1oRe291dqT-00K9io; Fri, 07 Oct 2022 18:51:16 +0200 In-Reply-To: <878rlrfyje.fsf@rfc20.org> X-Mailer: iPad Mail (19G82) X-Provags-ID: V03:K1:fzXBlZNteNLENboVA/hlyJcvuu1kDBiI4uNkLz7grifTm+Iw4Vk WRvP022ngLL0DJ/V6F9/+Tj4DQXJxs4CP5ZVc4Zuoek3Z1Q+y8jzc3Aul+inIBgfLhTYgEl vgK5HY4tHZTUvOUQOO5G+8tV57a8M0lzi6m9QyErXkaM8Wo5KfzZzRB06Vt5pJNRVljO72Q RK/bBLfThOLfRs82kh/sg== X-UI-Out-Filterresults: notjunk:1;V03:K0:oxOSyS6HEzY=:5woV7akfpcILVaBLPZiHMm Ad2OLhUwJZrMow4S3dK8kXSie0sItgCH6pDGALHtCIb5rR/aFzzU2Ku6FR3mtayl7FsMMV1bo QNQ/LHLAPtdctmwxK0/Y/jT41SJJSBQS4o1kWI111M1pXc63T6t4MvoZeAKoLRQ0EfpT3t4sY c27uAYHzAzQdv8xEfMSCk/gVnQy87Qcn4HerX1ZAZ0BjvRvEXnj9b42tM4BwrTZH+95SsQHDV gEbcodPhhyiGYPSJcMr1j9vUQsmlC/Sj5Vwqy35FEGywyXmTLAsVHdzN2+YBnDYGjEVxFz6Jv Cv1nFbnA+S3YGLMqYQ9kruqhSC8wnk1sqbKNtRg80J29WB6QepM0rNhVSOh948JqzepOPzM7I CMcGhzhUGosOtuM9io2DEju4HQfFxc7U2YknoPWffh0e6/UTb838jsV9CotaUgZITS2WmHe5t kNqaOxvp5t+H6Na5P3nLRwHSdcpFn6XFz8UMPjEL6r1YsjGcYQu6rmnQR4qX2NjvT9PNKQ0x7 S8bOk4p03WUhef6WAte/mYgWyZG2MAP0FHCzg6tpQqVJO0hoYkn7fi+/VN76jqt1Y+U3Mz2nd W98RajWddSWOVb5EuLFDzg4azHlY6gApVmKQvDNpbrmIZCS4DVwkqXJNEUZZKjN+kSNrgm5YM al1X90V/nIdIiUPvUU2iZQi+c1pNlUA5+OFuC2i9dDFTuXpWzajOpGmCfvjytrtu6aPBNxdSB 1r4+39bCood2pDXGzsbXYBTUeIC6g1XXLURLPAlP7EBSL0s6na+UeXpUbpm2eo5hN3HrL3IW Received-SPF: none client-ip=212.227.126.130; envelope-from=mail@andreas-politz.de; helo=mout.kundenserver.de X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Fri, 07 Oct 2022 14:14:39 -0400 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:244836 Archived-At: I think, a straightforward way to use 2 trees, one for begin and one for e= nd, could be to create another abstraction above those trees, while for the m= ost part duplicating the existing interface. This abstraction would then e= ither delegate to one or both trees, depending on the operation. The trick w= ould be to kinda multiplying the end-tree by -1, i.e. reverse begin and end= and multiply with -1 all inputs and outputs of this tree. Would that work ? > Am 07.10.2022 um 17:23 schrieb Matt Armstrong : >=20 > =EF=BB=BFTo start, I don't think this issue should delay a merge to master= . I > don't think it is clear we need to fix anything here. >=20 > I would like a note or FIXME in code noting the potentially slow > algorithm (patch sent), because it is currently well hidden behind a > generator loop. >=20 >=20 > Stefan Monnier writes: >=20 >>> 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 >>=20 >> The core operation in itree.c is the equivalent of `overlays-in/at`. >=20 > [...] >=20 > Yes, and for this O(K*log(N)) performance is a good result. The key > insight is that previous and next overlay changes require examining a > large K (in worst case, extending all the way to the beginning or end of > the buffer) because there is no ordering by END positions. >=20 >> Realistic benchmarks would be most welcome. >=20 > I am working on polishing off > https://git.sr.ht/~matta/emacs-overlay-perftests. Good news is that > redisplay is faster on the noverlay branch for the "realistic" case of > overlaping not overlapping eachother in pathalogical ways. >=20 >=20 >> [ 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. ] >>=20 >> 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. >>=20 >> 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). >=20 > At the moment I can't think of a reasonable way to implement such a > generator efficiently without, effectively, computing a temporary > ordered collection over overlay END positions. >=20 > This is why I keep coming back to the idea of storing both BEG and END > positions in ordered collections at all times. >=20 >=20 >> 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). >=20 > ...possibly, but the problem with caching is the time spent filling the > cache back up. I like the idea of storing both BEG and END positions in > an ordered collection because in that case the (potentially slow) > recomputation need not occur with every key press. If we're not worried > about that kind per-key-press of delay, then I argue there is no need > for a cache either.