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: Fri, 07 Oct 2022 08:59:55 -0700 Message-ID: <871qrjfwuc.fsf@rfc20.org> References: <1468ca31-1703-82a1-0c8c-be2c5b5674a7@gmail.com> <87r0zld0de.fsf@rfc20.org> <87edvki88a.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="13030"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier , Gerd =?utf-8?Q?M=C3=B6llman?= =?utf-8?Q?n?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Oct 07 19:09:17 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 1ogqqa-0003Dh-3q for ged-emacs-devel@m.gmane-mx.org; Fri, 07 Oct 2022 19:09:16 +0200 Original-Received: from localhost ([::1]:38120 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogqqY-0002bs-Un for ged-emacs-devel@m.gmane-mx.org; Fri, 07 Oct 2022 13:09:14 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:44372) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogplh-0004YV-Py for emacs-devel@gnu.org; Fri, 07 Oct 2022 12:00:09 -0400 Original-Received: from relay2-d.mail.gandi.net ([2001:4b98:dc4:8::222]:48265) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogplb-0003nX-Nn for emacs-devel@gnu.org; Fri, 07 Oct 2022 12:00:05 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id C07DE40008; Fri, 7 Oct 2022 15:59:57 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665158400; 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=VIL3Snr7XhD4JKl5GyDsoLk/YG3LJ1euVJzDSNAVZ7A=; b=ckybDzHPJEc6gP7izVgeCxTIw+eym5Fqugjj+UlxmthrejKbLulCHCrnX4LTEKLQdwHLkg YRHw4vBAEAw4mqrcVEl1eBaKxLieACDOjmPqxBHOM+Jf1pzLJoNuuQIWg4HuiZS5BP3l8p OkD4Q58XcycDiBrx/K5KlQs+hiR4c19CAAsE3UTdleFyhnbuPhv7Lamlk0tw9a1K0W9YEn RVpPuL9nEP658cNryBAnQXjVcEpUrxp/7NVKNq5jZjz9TZfPwDmm34mVKHHqurjQfrRRPz tFj6dKK44V2JBDH6rLK7F9qWphZajjg2YJ1FjzAxY/GRsbWkST1wkEykcOVQCA== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogplT-004Jcw-1j; Fri, 07 Oct 2022 08:59:55 -0700 In-Reply-To: Received-SPF: pass client-ip=2001:4b98:dc4:8::222; envelope-from=matt@rfc20.org; helo=relay2-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:297164 Archived-At: Stefan Monnier writes: >> to allow C++. With std::multimap/std::multiset, we would have a >> ready-made complete solution for the tree, tested by a gazillion of >> users. Just dreaming :-)) > > I'm not familiar with C++ libs: does this `multiset` lib offer something > similar to the lazy update of buffer positions that Andreas's code uses > (via the `offset` field together with the `interval_tree_inherit_offset` > function)? The ordered collections in the C++ standard library do not support augmentation. User code isn't allowed to see the left, right, parent pointers, for example, nor are there "hooks" that allow running user code as the tree is traversed or modified. The "treeness" of the collection is abstracted away entirely. The kind of augmentation used by noverly is quite bespoke, and I think it justifies a bespoke implementation. It is "augmented" both bottom up (the LIMIT field) and top down (the OFFSET field), and requires specific handling of each. There are enticing features in C++, but I don't think an off-the-shelf solution to the overlay problem, suitable for use in Emacs (e.g. licensing), is one of them. I like C++ quite a lot, and have decades of using it professionally, but I'd still be very cautious using it in Emacs. For one, Emacs aims to support all sorts of relatively obscure compilers on little used platforms. C++ tends to reduce what a program is portable to, though admitedly it is much more portable in practice than most "modern" programming languages. >>> I think in the context of this overlay work the performance difference >>> is not very significant, since the code is doing a lot of other stuff >>> while traversing the tree. >> I agree. I think NULL could be better in multi-threaded cases, as >> Stefan alluded to. > > The current code should be multi-thread safe (except for the global > iterator, of course), despite its use of a global sentinel node: there's > no need to synchronize anything when reading a read-only field or when > writing a write-only field. Pedantically, read-only fields do need synchronization with respect to previous writers. As for writing, you do need synchronization of writes to avoid undefined behavior. The memory model doesn't allow for unsynchronized writes. Anyway, neither is happening here. If this global sentinel node is never modified then it isn't ever used, so there can't be a synchronization problem! It is just there to generate a unique constant address that the tree code uses as a "null" value without actually using NULL. I think it is unusual and unecessary, but it is thread safe.