From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Gerd =?UTF-8?Q?M=C3=B6llmann?= Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Sat, 01 Oct 2022 07:06:50 +0200 Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.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="27193"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Oct 01 07:09:54 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 1oeUl5-0006hJ-Ek for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 01 Oct 2022 07:09:51 +0200 Original-Received: from localhost ([::1]:48918 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oeUl4-0006Yg-98 for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 01 Oct 2022 01:09:50 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:43458) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeUjK-0004JX-Uo for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 01:08:05 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:44333) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oeUjK-0003L4-Mx for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 01:08:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oeUjK-000076-Gr for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 01:08:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 01 Oct 2022 05:08:02 +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.166460082232470 (code B ref 58158); Sat, 01 Oct 2022 05:08:02 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 05:07:02 +0000 Original-Received: from localhost ([127.0.0.1]:43411 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeUiM-0008RQ-6C for submit@debbugs.gnu.org; Sat, 01 Oct 2022 01:07:02 -0400 Original-Received: from mail-ed1-f41.google.com ([209.85.208.41]:37797) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oeUiI-0008QH-UB for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 01:07:01 -0400 Original-Received: by mail-ed1-f41.google.com with SMTP id a41so8332517edf.4 for <58158@debbugs.gnu.org>; Fri, 30 Sep 2022 22:06:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date; bh=+YCkiWRhBoBJStJZSY7qKRgSYZSiqG4Juy72jxJD84g=; b=HyaAm4EgH0FtZmSIvUM+kcOPsBQW/RllOB/eaxNboBjLaP/nKAFFxrCDbheluBbxun C5nRhoiR7umly5hf5wYbrIYCxZyHWI2YuIIbxbV0mnz5f3bWtRcuJ33GDQdc2pRwcPss f5vCvQ3pG2CezDq89NDXmeUv+bvP/0PjuLf4Jv3hRWuOILmOqTMJUd+wG6bzIbp/6uip R45C9ZnxpxI1xZOCMuz7wJ0QNtiIkDmn3vSlGrTJw/7d1bJ1rFYxq3evoRP2msWg+pIc 7Z735r9vIM1bk5u3bX0q31WMr0G6UGwTk1ZlIbECYnqwl0h/H+p0BuO3iGGkoHkOaJfR W+Cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date; bh=+YCkiWRhBoBJStJZSY7qKRgSYZSiqG4Juy72jxJD84g=; b=KQvYuJ9Txli88z1zIwPzFCR2pEjBuQecpNcJJuvcDDQccoWOAaxoXKjPnThMNP+Y5g aBhhcN1g6UPapj6UJrdVshXAsco8gAXbGnoLUgGJfkWyvKY9Fje3rQyUmM9ljEepDDZw S9uuARoeChluHVt+ZFqBMrSr8OGWzzECANRlYZjfCsXInB6w7QdMxBg5RMMCGH7UoHRB nPUSOgpsi0Gd1OCGzEl2GQRRloGoaVIqK6KEnm6QwUF4P/hXb2VMXfuHJY6bHiC1Z9zc 4cezGm435odXAP8JVrSvym3Ts7lfPcPRGZRV12JOCLNLgN8sSy6OULU2zrDFHO2Gw09r lOFA== X-Gm-Message-State: ACrzQf1MvgO1fez94TfG5QevUxJMvdfQuLSVrQMCceiwSOHCtr17I7Fn NOo15FqRz252P/bgYfVzTdY= X-Google-Smtp-Source: AMsMyM7zVw00VFOqaIf8gXIMXLOUzkHX0upRIF4RnKj2Acys0TkW2FFMAQfwynLYbO3G4xLzBQrC4g== X-Received: by 2002:a05:6402:d05:b0:425:b5c8:faeb with SMTP id eb5-20020a0564020d0500b00425b5c8faebmr9975780edb.273.1664600813020; Fri, 30 Sep 2022 22:06:53 -0700 (PDT) Original-Received: from Mini.fritz.box (p4fe3ace2.dip0.t-ipconnect.de. [79.227.172.226]) by smtp.gmail.com with ESMTPSA id v18-20020a50d092000000b00457e5a760e3sm2876778edd.54.2022.09.30.22.06.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Sep 2022 22:06:52 -0700 (PDT) In-Reply-To: (Stefan Monnier's message of "Fri, 30 Sep 2022 11:25:30 -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:244070 Archived-At: Stefan Monnier writes: >> That is, if N is a node, all nodes in the subtree N->left are strictly < >> N, and nodes in N->right are >=. > > The following code in `interval_tree_insert`: > > while (child != ITREE_NULL) > { > parent = child; > offset += child->offset; > child->limit = max (child->limit, node->end - offset); > /* This suggests that nodes in the right subtree are strictly > greater. But this is not true due to later rotations. */ > child = node->begin <= child->begin ? child->left : child->right; > } > > suggests that N->left are <= and N->right are > but my reading of the > comment is that the only thing we can rely on is that N- N->right is >= Phew. I'm not sure but I get the feeling that makes implementing a successor function, let's say, challenging. I wonder how std::multimap deals with that. Hm. Anyways, with your removal of the visited flag (N thumbs up, for large values of N :-)), most of the problems I preceived are gone anyway. So, I guess we can live with the iteration stack, which seems to work fine, and the alternative is only nice to have, now. (And impacts are getting closer in the real world here, so I'm a bit distracted anyway.) > > [ I do understand this comment now :-) ] :-) > >> 2. Does the tree order duplicates in a particular way? >> Maybe by overlay priority, or by interval end? > > AFAICT, no it does not. Ok. >> And, perhaps, if it doesn't order duplicates, would it be an idea to >> order them, maybe at some later point? I'm asking this because >> a successor(N) function would return nodes in the order in the tree, >> always, and I don't know what the order is now. > > 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. Thanks. > >> 3. If my mental picture is right, we could of course end up with a tree >> that has degenerated to a list. Or a subtree, maybe. Do you know if >> that can happen? > > In terms of tree depth, no: the code preserves the RB invariants, which > ensure balance regardless of ordering (or lack thereof). Ok, thanks for your insights!