From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Matt Armstrong Newsgroups: gmane.emacs.bugs Subject: bug#58342: 29.0.50; noverlay branch is O(N) for important calls Date: Fri, 07 Oct 2022 08:23:17 -0700 Message-ID: <878rlrfyje.fsf@rfc20.org> References: <87edvkcz5v.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="10157"; mail-complaints-to="usenet@ciao.gmane.io" Cc: gerd.moellmann@gmail.com, 58342@debbugs.gnu.org, mail@andreas-politz.de, eliz@gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Oct 07 18:05:28 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 1ogpqq-0002Q6-DU for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 18:05:28 +0200 Original-Received: from localhost ([::1]:48056 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogpqo-00017y-QL for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 12:05:26 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:38444) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogpCl-0004Qi-4D for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 11:24:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38123) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogpCk-0005w2-H3 for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 11:24:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ogpCk-0005qx-BO for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 11:24:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Matt Armstrong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 07 Oct 2022 15:24:02 +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.166515621222457 (code B ref -1); Fri, 07 Oct 2022 15:24:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 15:23:32 +0000 Original-Received: from localhost ([127.0.0.1]:37201 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogpCG-0005q9-8D for submit@debbugs.gnu.org; Fri, 07 Oct 2022 11:23:32 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:33190) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogpCE-0005q0-T8 for submit@debbugs.gnu.org; Fri, 07 Oct 2022 11:23:31 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48538) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogpCE-00038p-LO for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 11:23:30 -0400 Original-Received: from relay1-d.mail.gandi.net ([2001:4b98:dc4:8::221]:41385) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogpCB-0005ro-CB; Fri, 07 Oct 2022 11:23:30 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 5C83924000A; Fri, 7 Oct 2022 15:23:20 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665156202; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=38Kty76zu4mzjoxviGedY+bjAwkq9QkUktSpekdqDX4=; b=Gy+xZRFee3m0YhNEybbL6XYAZcijzrPnY5CiWffDP2KD6vm3EYBrWTq0zXo6m7UqM2qcKj vP+RcbuHuUzPRbGQZF16id8sS4F5eKSG95lZElr4GPrUOrlQNcL1tDbxJQlQmeef26TFdV uwP5tF08OxtnT/0pgiIu6WNkZY2U5uHjLHmF1WJvYY5MblLuJym3Wec3zIya0hTLkBam7p WczqyDLy/6D+kuIiWxdE6Vz976nl5R+YdwmVl08l1/cBfzSe7WHC+S7wRnG//j4fqojKYx yiWtLcx99p5KbLjAdDcT3IiCX+p2qX7X6LSdbMf3bsmw/3VgHyGLe+aYbec4Qw== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogpC2-004JKS-1r; Fri, 07 Oct 2022 08:23:18 -0700 In-Reply-To: Received-SPF: pass client-ip=2001:4b98:dc4:8::221; envelope-from=matt@rfc20.org; helo=relay1-d.mail.gandi.net 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_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:244822 Archived-At: To 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. 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. Stefan Monnier writes: >> 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`. [...] 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. > Realistic benchmarks would be most welcome. 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. > [ 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. This is why I keep coming back to the idea of storing both BEG and END positions in ordered collections at all times. > 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.