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 13:37:31 -0700 Message-ID: <87a6674bg4.fsf@rfc20.org> References: <87edvkcz5v.fsf@rfc20.org> <878rlrfyje.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="34922"; 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 22:38:13 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 1ogu6l-0008n0-Jp for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 22:38:12 +0200 Original-Received: from localhost ([::1]:44492 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogu6k-000563-AV for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 16:38:10 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48254) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogu6c-00055U-HX for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 16:38:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:38427) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogu6c-0000ye-9J for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 16:38:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ogu6b-0003VE-Nb for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 16:38:01 -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 20:38: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.166517506713443 (code B ref -1); Fri, 07 Oct 2022 20:38:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 20:37:47 +0000 Original-Received: from localhost ([127.0.0.1]:37505 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogu6M-0003Uk-Q0 for submit@debbugs.gnu.org; Fri, 07 Oct 2022 16:37:47 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:35384) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogu6L-0003Ud-3e for submit@debbugs.gnu.org; Fri, 07 Oct 2022 16:37:45 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:60588) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogu6K-00052x-HL for bug-gnu-emacs@gnu.org; Fri, 07 Oct 2022 16:37:44 -0400 Original-Received: from relay3-d.mail.gandi.net ([217.70.183.195]:47097) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogu6I-0000x9-5X; Fri, 07 Oct 2022 16:37:44 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id B06E160002; Fri, 7 Oct 2022 20:37:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665175058; 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=M3DFf9sMi1pjXNfSN2QBShtD3D4KWfAg6V9lhbHeygY=; b=EDk3s0nx7sMpgi925J5q8aw+486ycJsynDzj0tmnCmughOy5gwrF6ADyAQl9YPmaX1bBOD esdZiTdomxSm8N3nKjTtxBgVSKWWoa6ibus3YCzWTS/GCU6ZcH4dMmu1ikB2SC1CiCbZhY 4DHLpwLnjzOMAWEejHUaDLIrZ2gcLszQS0R4ZrQ29avLfxARa5aPe1M9MgIiQz0kxCs2JQ cpkfrvlILAj7bm0+wON0AeY3GMOWhethJkLyBHD595aCw7bNRvS2pzWpL3E3kVS5/l6yYK I8Cg29qdoAUAHqqBXBuYL1EcpFhF77jmXVeBuMjepckAitNYbmxAdrklYOk20Q== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogu67-004Vep-31; Fri, 07 Oct 2022 13:37:31 -0700 In-Reply-To: Received-SPF: pass client-ip=217.70.183.195; envelope-from=matt@rfc20.org; helo=relay3-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, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, 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:244849 Archived-At: Stefan Monnier writes: >> 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*. ] First, we need benchmark that demonstrates a problem. You've asked for this. I've simply pointed out that there is no algorithmic protection from bad performance, but I haven't yet come up with a practical example. I understand your concerns about the costs of maintaining a separate tree, but I think this design brainstorm is getting ahead of things. I would advocate for such a "dual tree" design only if it made sense on some demonstrated engineering basis. Goals are always balancing simple code, simple design, and efficiency. Opinions can differ, but they're difficult to settle out without something concrete to talk about. Does anybody know of an Emacs package that uses a large number of overlays that span large amounts of the buffer in complex ways? If none exist, maybe we can just close this bug!