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: Fri, 07 Oct 2022 13:11:38 -0400 Message-ID: References: <87edvkcz5v.fsf@rfc20.org> <878rlrfyje.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="22230"; 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 19:19:27 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 1ogr0R-0005Zz-Hu for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 19:19:27 +0200 Original-Received: from localhost ([::1]:41102 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogr0Q-00038w-CR for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 13:19:26 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:47370) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogqtG-0005A4-Nb for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 13:12:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38226) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogqtG-0007CI-9j for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 13:12:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ogqtF-00009c-T6 for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 13:12: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 17:12: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.1665162719582 (code B ref -1); Fri, 07 Oct 2022 17:12:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 17:11:59 +0000 Original-Received: from localhost ([127.0.0.1]:37304 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogqtC-00009G-RW for submit@debbugs.gnu.org; Fri, 07 Oct 2022 13:11:59 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:38602) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogqtA-000098-9x for submit@debbugs.gnu.org; Fri, 07 Oct 2022 13:11:58 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:38154) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogqt5-0004xk-Nh for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 13:11:56 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:4863) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogqsz-0007AT-4Q; Fri, 07 Oct 2022 13:11:50 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id CBE3E100142; Fri, 7 Oct 2022 13:11:41 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id B86FB1000E7; Fri, 7 Oct 2022 13:11:39 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1665162699; bh=UJH5/jsIPSWn6HQghOzveGd3ScGiWzIXQja53alX8X4=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=bUFnQKQttxThSbD/qeyvh7lKmg3h93OzvplKLlFvT5RfPEu2xjWMR26Bs+NhQwNpb L0Qp3A4eCdXJRllZK2hLMdJe2SriBLrFe8ks9nlGYZySZi+O1r/JcaK3IEhJgvcCPU UfSu0qTqy+P+k9r5CDxQvIMhilWXIXlzeHLKFZxtoE1qt7b1IBCm4I2+6W8xllIM+1 mRDE6nvdgBG8tdVtyJDniZetoQF4+x/3gRJ0prkUJWVr5J8G5XQbbQI0yf/pVnYYZO fcbwgIasO9b/kEMQy0jOVgHn8sxSGcpZIcAqLHMyS9Asja2B305HNIvvpCSSO2xpWk /myHSz3t/d5/A== Original-Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 83FEA120636; Fri, 7 Oct 2022 13:11:39 -0400 (EDT) In-Reply-To: <878rlrfyje.fsf@rfc20.org> (Matt Armstrong's message of "Fri, 07 Oct 2022 08:23:17 -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, T_SPF_TEMPERROR=0.01 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:244835 Archived-At: > 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. I'll merge it soon, yes, thanks. > 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. Excellent, thanks. >> [ 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). > 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. Indeed, the generator needs to build such a side table (I was thinking of something like a heap datastructure). I don't see it as a problem. > This is why I keep coming back to the idea of storing both BEG and END > positions in ordered collections at all times. But that comes at a non-negligible constant-factor cost :-( [ Maybe a "cheapish" (memory-wise) way to make it work is to add two fields `prev` and `next` used to link the nodes into a doubly-linked list ordered by `end` positions. We should be able to find a given position in this list efficiently (i.e. not linear time) by relying on the `limit` field, thus making it unnecessary to maintain a second *tree*. ] >> 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). > > ...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. I'm definitely not worried about performing one such recomputation per key press. The problem of the O(N) issue you point out might come up when we have to repeat that O(N) for every buffer position where there's an "overlay change", but if it's done once per redisplay (or once per window being redisplayed), it should be lost in the noise. Stefan