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.devel Subject: Re: noverlay branch Date: Tue, 11 Oct 2022 11:02:22 -0700 Message-ID: <87fsfuw85t.fsf@rfc20.org> References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.fsf@rfc20.org> <87pmf04c7s.fsf@rfc20.org> <87sfjvvx7g.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="5270"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Oct 11 20:07:04 2022 Return-path: Envelope-to: ged-emacs-devel@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 1oiJei-0001BW-A4 for ged-emacs-devel@m.gmane-mx.org; Tue, 11 Oct 2022 20:07:04 +0200 Original-Received: from localhost ([::1]:58680 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oiJeg-0003m5-S3 for ged-emacs-devel@m.gmane-mx.org; Tue, 11 Oct 2022 14:07:02 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49410) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiJaN-0002hp-5z for emacs-devel@gnu.org; Tue, 11 Oct 2022 14:02:37 -0400 Original-Received: from relay8-d.mail.gandi.net ([2001:4b98:dc4:8::228]:34553) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiJaJ-00019N-Jo for emacs-devel@gnu.org; Tue, 11 Oct 2022 14:02:34 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 087141BF20C; Tue, 11 Oct 2022 18:02:25 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665511346; 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=KkChuCwXkw9ouVnps3Y0X/ACL3j7GTOD84y1U/BbpQM=; b=B/c9KOapevSFdy7ywMuJX7onVxL32zwVlemUwrOwDvk4tGV4K1eOeEr1WXSL277rABVctC LvFzETL7b7tQ4AZdZHdmtbApFgZENFSSn/xJo0zzX/a9kIo46DE1iYdWrepOn11CZwU5QN F3gI69LYmHI0eV+MBukcLt8qaNqj3dP9qBypYknMy5O03VcypwuvcPWR2rCv27qsmj7NH4 Ous/xU0PPuqKZzimCGuZFw5OB0M9C/AvsaXYKWcrzDQY4FodfJJOviqNRnD/XFhoYzTRPL Kf4T+ruRtb1lFIsFqAGcUVLc2WpiOh61dcWN47yblW04eafLws1zbgVuxhyZqw== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1oiJaB-009YzL-01; Tue, 11 Oct 2022 11:02:23 -0700 In-Reply-To: Received-SPF: pass client-ip=2001:4b98:dc4:8::228; envelope-from=matt@rfc20.org; helo=relay8-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: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:297517 Archived-At: Stefan Monnier writes: > Matt Armstrong [2022-10-10 20:46:43] wrote: > >> Not yet...until...just now. > > ?? > In the code I have from feature/noverlay I see: > > eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick); > > in `interval_tree_inherit_offset`. Oh, yeah. I was talking only about the `check_tree` function. >>>> 3) All downward tree traversal propagates offsets and otick. >>> I think we already do that, but if there are places we missed, then yes, >>> of course. >> Yes, I think we do. The wrinkle is that we don't always start >> inheriting at the root, but otick is not updated in that case. > > I don't think propagating `otick` is very important during > tree traversals. I agree. I can't think of a strong argument to do it. >>> Regarding `otick`, I can see 2 more options: >>> - Get rid of it completely: its sole purpose is to try and keep >>> `overlay-start/end` O(1) in the usual case instead of O(log N), but >>> I'm not convinced it's worth the cost of propagating `otick` everywhere >>> all the time. >>> - A halfway point is to keep `otick` but update it more lazily, >>> i.e. only update it when we do `overlay-start/end` (e.g. in >>> `interval_tree_validate`). >> These ideas are simpler but similar in direction to my idea to use a >> btree instead. > > Sorry, I fail to see the connection to btrees. Just a performance conjecture. A b-tree is shallower, so your first idea above is more attractive. >>> This max_depth also sounds to me like over-engineering. >> I'd like to keep max_depth. > > Sorry, not gonna happen. [...] > Yes, it's very helpful *while working on the code*. But it's easy to > sprinkle many more calls to `check_tree` as needed when you're debugging > an error caught by the cheap checks. And when you do that you can > temporarily pay the price of full tree traversals. [...] > But some of them are currently at places where they're unacceptable > because they cost a lot more than the surrounding code. Great, thanks for those explanations. I am now a little better calibrated as far as the expected performance of ENABLE_CHECKING code. > [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on > auto-growing more heavily. ] I rather like the size field. It is one of the first things I look at when assessing a crash, since it is nice to know whether a tree is small or enormous. But, yeah, little else really needs it. I have a different idea about the stacks, though. Idea: use fixed size stacks, no auto-growing. 120 elements is all that is needed (the max possible depth of a 3-pointer red-black tree on 64 bit architectures). That is 1K memory overhead per traversal, which I think isn't an issue? At least, this is a reasonable choice in other systems I've worked in. Is it reasonable for Emacs?