From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Thu, 29 Sep 2022 16:40:10 +0300 Message-ID: <83leq2fged.fsf@gnu.org> 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; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="30837"; mail-complaints-to="usenet@ciao.gmane.io" Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Sep 29 17:01:16 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 1odv2K-0007se-0b for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 29 Sep 2022 17:01:16 +0200 Original-Received: from localhost ([::1]:52494 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1odv2J-0000ju-1Z for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 29 Sep 2022 11:01:15 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:56784) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtmg-00051J-A5 for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 09:41:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:37609) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1odtmg-0005Pj-1R for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 09:41:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1odtmf-0005B1-U8 for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 09:41:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 29 Sep 2022 13:41: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.166445882519823 (code B ref 58158); Thu, 29 Sep 2022 13:41:01 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 13:40:25 +0000 Original-Received: from localhost ([127.0.0.1]:36685 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtm4-00059e-MT for submit@debbugs.gnu.org; Thu, 29 Sep 2022 09:40:25 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:57872) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odtm3-00059N-1w for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 09:40:23 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]:35746) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtlx-0005CP-3w; Thu, 29 Sep 2022 09:40:17 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=9JGmNIcp4trp60/HHPctb7rUn/M53Ri2DdAZB8eTzVk=; b=BuXDQeu+lw0+KzH+po+W n+4idUSaBpfBGcF0C+bvZxcVz2E5hGRwucB/kr+1Qtlr6xbqL/nvbUCdm5u/T49D6fSyThkjFL/A1 Zxkwz489mJBxkmcI94wnFwMNQ7iYAzYSfdRCN/pr/gt2KcJgvDyBeTOR9+RsVJUzULgQ/jIqIc1Zl lADkJNDhKfQYdBY5gviIZFglSv+CISAqnanZHd62wtas4NGUAFAB7H+7sMhauBr/Dc9NOE/SYkUqr oTk75zabGLIJwmwMC7mVoy9RZOKo3dCpWBoXN3JEuF1Jc4z81hpME18tCCGkxBiCEeEmCd6qTcpae M/wWD/crXL9nmg==; Original-Received: from [87.69.77.57] (port=1666 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odtlw-000792-Ig; Thu, 29 Sep 2022 09:40:16 -0400 In-Reply-To: (message from Stefan Monnier on Thu, 29 Sep 2022 09:10:19 -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:243900 Archived-At: > From: Stefan Monnier > Cc: Gerd Möllmann , > 58158@debbugs.gnu.org > Date: Thu, 29 Sep 2022 09:10:19 -0400 > > Another is the need to update the begin/end fields (these need updating > because of insertions/deletions but they're updated lazily while > traversing the tree to avoid an O(N) complexity during the > insertions/deletions). Hiding that behind 'some kind of "next node" > function keeps the code more readable. Btw, couldn't we handle this by having a flag in the node that tells us whether the begin/end fields can be trusted? Then the first caller who need them would run the update and reset the flags, and we still have lazy update, albeit somewhat less lazy, but without the need for guarding the iteration with start/finish calls. Would that work?