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#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Fri, 30 Sep 2022 13:11:06 -0400 Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> <83v8p4df2i.fsf@gnu.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="17346"; 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, mail@andreas-politz.de, 58158@debbugs.gnu.org To: Eli Zaretskii Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Sep 30 19:19:07 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 1oeJfH-0004Ko-2V for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 30 Sep 2022 19:19:07 +0200 Original-Received: from localhost ([::1]:38046 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oeJfG-0006YF-2q for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 30 Sep 2022 13:19:06 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:37478) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeJYR-0004h0-HI for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 13:12:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:43760) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oeJYR-00018I-A2 for bug-gnu-emacs@gnu.org; Fri, 30 Sep 2022 13:12:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oeJYP-0005ER-LL for bug-gnu-emacs@gnu.org; Fri, 30 Sep 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, 30 Sep 2022 17:12:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58158 X-GNU-PR-Package: emacs Original-Received: via spool by 58158-submit@debbugs.gnu.org id=B58158.166455787920060 (code B ref 58158); Fri, 30 Sep 2022 17:12:01 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 30 Sep 2022 17:11:19 +0000 Original-Received: from localhost ([127.0.0.1]:42838 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeJXi-0005DT-Gi for submit@debbugs.gnu.org; Fri, 30 Sep 2022 13:11:19 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:52512) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeJXf-0005Cv-Sr for 58158@debbugs.gnu.org; Fri, 30 Sep 2022 13:11:16 -0400 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 19D5044272A; Fri, 30 Sep 2022 13:11:10 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 95D87442727; Fri, 30 Sep 2022 13:11:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664557867; bh=VOuD7Jdhirx9qrz7e92ifV6GxUDcPSidokw1/hI4Wmk=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=L8qOOpoy3dKt0Tepjvwbl8JsiDyEVLUVv8qxQ4IzsPnigDXFodEihuoE/a7xrypSW LjxZp+7IrBT02M/m1Hs/9Ntp2c+h6svY5SmKmy3sxicdUYeDUFtE0I5G6BicZHQUdl kE2yX3WQGCgkdzujR2Ki65lsOP1YR7/cYv5D4WhXvqI2XJ09kze8N1K80Ti4TWoc1G GYdCq2y1kcTXtHqjpiaQAyoFWwhVg90kVwuDf4J3KowgEhOkSFuVJ6sGC7cb8le0fi AvvuwfB7OIXLNdvgYg8E7XDHWJuCNcKxnJ6fb3VI4wpAF9PVKizzGUqfduFCVNP7lF 3HfAlRmLgplzA== Original-Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 571D612031C; Fri, 30 Sep 2022 13:11:07 -0400 (EDT) In-Reply-To: <83v8p4df2i.fsf@gnu.org> (Eli Zaretskii's message of "Fri, 30 Sep 2022 19:04:05 +0300") 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:244037 Archived-At: >> Ordering based on interval end could arguably make sense. I'm not >> completely sure how/where it would benefit us, tho. Most times we look >> at the itree, we just look at *all* the nodes within a specific >> interval, so the order in which they're returned doesn't matter very >> much (the ordering within the tree does matter in terms of how we manage >> to prune the tree, but that has more to do with which elements are near >> the root, which is a different kind of "ordering" than the "binary tree >> ordering" itself). Maybe the `next/previous-overlay-change` code >> benefit from sub-ordering based on `end`, but I suspect the effect would >> be lost in the noise: if we want to speed up that part of the code, >> I expect that a better avenue is to rewrite the >> `next/previous-single-overlay-change` so as not to work by (while .. >> (next/previous-overlay-change ..) .. (get-char-property ..) ..) where >> both functions do the O(log N) itree-iteration dance, but instead doing >> the itree iteration itself. > > The display engine sorts the overlays, so order could be important. Indeed, for things like `overlays_at` it would be handy if the iterator could return the right overlays already in the right order, so we don't have to `sort_overlays`. But in `sort_overlays` the `priority` property takes precedence, so if we order the RB tree based on that ordering, we will lose the main purpose of the change, i.e. finding the overlays at POS in O(log N) time, because the `compare_overlays` ordering does not let us know that all of the left or right subtree is outside of a given interval. IOW the itree has to use a different ordering than that of `compare_overlays` anyway, so we're still forced to (re-)sort afterwards with `sort_overlays` :-( Stefan