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 22:18:49 -0700 Message-ID: <87czaxwreu.fsf@rfc20.org> References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.fsf@rfc20.org> <87pmf04c7s.fsf@rfc20.org> <87sfjvvx7g.fsf@rfc20.org> <87fsfuw85t.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="13002"; 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 Wed Oct 12 07:23:33 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 1oiUDM-0003C4-Or for ged-emacs-devel@m.gmane-mx.org; Wed, 12 Oct 2022 07:23:32 +0200 Original-Received: from localhost ([::1]:59052 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oiUDL-00084X-CG for ged-emacs-devel@m.gmane-mx.org; Wed, 12 Oct 2022 01:23:31 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:39202) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiU8z-0005dw-9u for emacs-devel@gnu.org; Wed, 12 Oct 2022 01:19:01 -0400 Original-Received: from relay1-d.mail.gandi.net ([2001:4b98:dc4:8::221]:43465) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiU8w-0000xi-Dk for emacs-devel@gnu.org; Wed, 12 Oct 2022 01:19:01 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 84344240003; Wed, 12 Oct 2022 05:18:52 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665551933; 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=AXsaA7cN38aLowKX3GdIS0i3Tzn2uO8eD+/s71XR8MQ=; b=iGc7Ak3GsCHddtSgqX1SYonSgjzKgqbgDq3fVOAlOFhIkQT6QQYWLl8QrDH541tER5yGDk TanfYGDL+fX5ndH72ZoXIOcuUO0TpQ/rppAxgluAidgrXGhLqxBMODVgxkfKVzkyH6SglL mJFRHY8oxRoBSoHxkY5/gLkSXp3BQIY8DiPZlA0JtRET7stGkEXsEuL6CIYbBhscP3R5RS nCPhoDqdFubRak/Gel4fTxPs9R2ijUzXTvwH0hxPUVPHQJ84fEcGnCat3BhgIjtGVWNZmf H0/pH+tkP78dYY+VyGjeoV+dJAXUSs6HFwlIu0lVdvkHRqj9dK8jbeyb38kvOQ== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1oiU8n-00ENJW-2C; Tue, 11 Oct 2022 22:18:49 -0700 In-Reply-To: Received-SPF: pass client-ip=2001:4b98:dc4:8::221; envelope-from=matt@rfc20.org; helo=relay1-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:297569 Archived-At: --=-=-= Content-Type: text/plain Stefan Monnier writes: > Oh, I think you're talking specifically about the complete removal of > `otick` where a shallower tree would make that less costly. > Sorry. I understand quickly, but only after a long explanation. That and the basic tree operations (find, insert, remove, etc.). You are right that there is enough essential updating going on in the tree that perhaps the btree isn't a win. I haven't thought about it deeply. >>> [ 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. > > I agree it has its benefit, which is why I haven't removed it yet: > I'm not sure. > >> 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? > > Maybe you're right. I think this decision is muddled by the (ab)use of > stacks as collections of nodes at a few places (where we use > `interval_stack_push`), where it's not limited to O(log N). Could most places use a fixed C array (maybe in a simple struct), with fancy places still using the fancy thing? Anyway, today 3 tiny patches. Two improvements, one bug fix. Also on https://git.sr.ht/~matta/emacs/log/feature/noverlay. And now patches... --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0001-.clang-format-Add-ITREE_FOREACH.patch >From 034d50415858b18b032b116804bfefc1be421bb3 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Tue, 11 Oct 2022 11:41:47 -0700 Subject: [PATCH 1/3] ; * .clang-format: Add ITREE_FOREACH. --- .clang-format | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/.clang-format b/.clang-format index 44200a3995..ac9f95c88a 100644 --- a/.clang-format +++ b/.clang-format @@ -6,7 +6,7 @@ BreakBeforeBinaryOperators: All BreakBeforeBraces: GNU ColumnLimit: 70 ContinuationIndentWidth: 2 -ForEachMacros: [FOR_EACH_TAIL, FOR_EACH_TAIL_SAFE] +ForEachMacros: [FOR_EACH_TAIL, FOR_EACH_TAIL_SAFE, ITREE_FOREACH] IncludeCategories: - Regex: '^$' Priority: -1 -- 2.35.1 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0002-src-itree.c-check_tree-assert-that-the-tree-root-is-.patch >From fda8723be640593a662d7ff9d4900b7f9e56423e Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Tue, 11 Oct 2022 20:32:08 -0700 Subject: [PATCH 2/3] ; * src/itree.c (check_tree): assert that the tree root is black --- src/itree.c | 1 + 1 file changed, 1 insertion(+) diff --git a/src/itree.c b/src/itree.c index ef623d0850..deef0335cf 100644 --- a/src/itree.c +++ b/src/itree.c @@ -307,6 +307,7 @@ check_tree (struct interval_tree *tree, if (tree->root == ITREE_NULL) return true; eassert (tree->root->parent == ITREE_NULL); + eassert (!check_red_black_invariants || !tree->root->red); struct interval_node *node = tree->root; struct check_subtree_result result -- 2.35.1 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0003-src-itree.c-check_subtree-fix-logical-error-in-easse.patch >From a98497429fcb1369bfe2af9d57820eb94ae380dc Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Tue, 11 Oct 2022 20:19:16 -0700 Subject: [PATCH 3/3] ; * src/itree.c (check_subtree): fix logical error in eassert --- src/itree.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/itree.c b/src/itree.c index deef0335cf..cd6b0b35f8 100644 --- a/src/itree.c +++ b/src/itree.c @@ -277,7 +277,8 @@ check_subtree (struct interval_node *node, if (check_red_black_invariants) { eassert (left_result.black_height == right_result.black_height); - eassert (node->parent != ITREE_NULL || !node->red || !node->parent->red); + eassert (node->parent == ITREE_NULL || !node->red + || !node->parent->red); } result.size = 1 + left_result.size + right_result.size; -- 2.35.1 --=-=-=--