From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Tue, 11 Oct 2022 00:09:32 -0400 Message-ID: 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="1703"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Matt Armstrong Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Oct 11 06:10:43 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 1oi6bK-0000IU-HW for ged-emacs-devel@m.gmane-mx.org; Tue, 11 Oct 2022 06:10:42 +0200 Original-Received: from localhost ([::1]:38612 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oi6bI-0000lS-U5 for ged-emacs-devel@m.gmane-mx.org; Tue, 11 Oct 2022 00:10:40 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:43914) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oi6aS-0008Ap-VQ for emacs-devel@gnu.org; Tue, 11 Oct 2022 00:09:48 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:53518) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oi6aQ-00037Q-3d for emacs-devel@gnu.org; Tue, 11 Oct 2022 00:09:47 -0400 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id EF3E8440157; Tue, 11 Oct 2022 00:09:43 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id C9D094401B0; Tue, 11 Oct 2022 00:09:37 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1665461377; bh=QMSr4wTbm+e8DYIGPM2Mu3HQ6w59QyaKZjId9ZRLekI=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=EEqcjGYTu8/BN/1cLRYFXjD9GgsE6wW2o+ZNAJBEuSkA9cKc8EegVNXpCMnDl7YVN Ppc9LnUwEM76C6G2UFEfjSpyosHurZQ1nHk++r0lDmaY7NMcB5iArVSIqrZYEiYgCN f47/ArG7/M8MMCXuol5zSTVg6IwhzQrmFyZoq9uwaqLmpqWUQwUP1dAkmkLgGghyVZ aaCakYcUYlzIdih3cYtvNUG/5dpqjhob/KDt3YeOz6hh6b/jKSGh9rZfuvj/nhgXAu m2xbVqiRMjaLUISi6JLyvUE098oC+QrroHqsb7ypHqRMpNB4JGXIdMBsob+84kox/U 6tOCS/cfrHS2g== Original-Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id A1B0712036E; Tue, 11 Oct 2022 00:09:37 -0400 (EDT) In-Reply-To: <87sfjvvx7g.fsf@rfc20.org> (Matt Armstrong's message of "Mon, 10 Oct 2022 20:46:43 -0700") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, 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:297412 Archived-At: Matt Armstrong [2022-10-10 20:46:43] wrote: > Stefan, I read only Eli's reply this morning. Got to yours just now. > > > Stefan Monnier writes: > >>> I had a different idea of tightening the otree invariant to this: >>> 1) A node's otick must be greater than or equal to its children's. >> That's already checked in the current code, right? > 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`. >>> 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. >> 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. >> This max_depth also sounds to me like over-engineering. > I'd like to keep max_depth. Sorry, not gonna happen. > My reason for adding it is informed by experience on similar projects. > It is easier to understand an assertion that the tree is too deep than > it is to debug, say, stack overflow when there is a cycle in the link > structure of the tree. The purpose of ENABLE_CHECKING assertions is: - avoid errors remaining undetected. - document the code. If it crashes with a stack overflow, it still detects the problem, so `max_depth` is not necessary for that. Your checking code is nice and detailed, but it's becoming so large that it increases the maintenance burden. I want to make it shorter&simpler. > It is easier to limit the height of checking if, indeed, on some night > I am diagnosing an unrelated bug but the perf cost here is too much. Many people run their Emacs always with ENABLE_CHECKING, so the performance impact should be minimized. It's OK to check a node's local invariants in those places where you visit the node anyway. It's OK to check the overall state of the tree in those places where the code will visit all the nodes anyway, but it's not OK to visit significantly more nodes just for the check than what the normal code would do, especially if an error there could be detected sooner or later by cheaper checks elsewhere. > With max_depth in place I can easily manually hack up > a functon to verify checks only in a small subset of the tree > (e.g. around a rotation operation, etc.). I've done and benefited from > this sort of thing in the past. 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. > There is a small concrete benefit to it right now. MAX_DEPTH is now > initialized from interval_tree_max_height(), which currently could wildy > under estimate the height and we wouldn't notice (because generator > stacks auto-grow). Since we call that fucntion to make "big enough to > not need growing" stacks, it is nice to have test coverage for it. [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on auto-growing more heavily. ] >>> + result.complete = left_result.complete && right_result.complete; >>> + if (result.complete) >> I think all calls to `check_tree` should be complete traversals. >> Most of the invariants checked in it are already checked incrementally >> via sprinkled assertions elsewhere, so it's only really useful when >> debugging a concrete known issue where the "local" checks aren't good >> enough. > All `check_tree` calls are complete traversals. Great, so we can remove the `result.complete` field. >> We could also include a few "cheap" calls to `check_tree` via `eassert` >> (i.e. calls which we know shouldn't be algorithmically too expensive >> because we're already traversing the whole tree for some other reason, >> e.g. when killing a buffer (e.g. to verify that, at the end of the day, >> we still preversed the RB invariants :-) or maybe during GC). > ...I'm not understanding something here. All `check_tree` calls are in > `eassert` already. But some of them are currently at places where they're unacceptable because they cost a lot more than the surrounding code. Stefan