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, 27 Sep 2022 10:31:04 -0700 Message-ID: <877d1oenc7.fsf@rfc20.org> References: <87bkr1e6yb.fsf@rfc20.org> <83ill9joji.fsf@gnu.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="19546"; mail-complaints-to="usenet@ciao.gmane.io" Cc: monnier@iro.umontreal.ca, emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Sep 27 19:37:03 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 1odEVz-0004tv-4l for ged-emacs-devel@m.gmane-mx.org; Tue, 27 Sep 2022 19:37:03 +0200 Original-Received: from localhost ([::1]:58838 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1odEVy-0001dq-1p for ged-emacs-devel@m.gmane-mx.org; Tue, 27 Sep 2022 13:37:02 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52288) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odEQO-0005Gl-RW for emacs-devel@gnu.org; Tue, 27 Sep 2022 13:31:17 -0400 Original-Received: from relay2-d.mail.gandi.net ([2001:4b98:dc4:8::222]:37371) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odEQL-0001Wd-IJ; Tue, 27 Sep 2022 13:31:16 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 7622040005; Tue, 27 Sep 2022 17:31:06 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1664299868; 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=QuGSNE+s4lvS46YTkOVD0y60dw0lyDKLf2cJ/JvixNI=; b=lHOOJG6ciH+rImWImK5knpR8pyGSJdQam9A4YJpleuTm13JdGtTS+Ek03pxB693Y7RR4Wh ebHnfQ8klFfkqiPctfioB6kVMlDGRZP+NQ4AkynEnm3C8cBoGZaew5llX9sGRUosa8LPG9 89K+ACohC3raxjKBwkW1lCcqXh5F3tHAYlZb6j+SihublOsG+cic8Cae58FozpyD2eVsYJ RE0YmLv32WHjk7Ui5NCMXm+nmY6a6LiYCmyjQsw7Uy49QuotiZaowDE8o/IEKJEU1B9fWV UKYSTVpfvzWQtZjKIufabh3Q3PP+snpUSWYKj770/30J8MeR4BWlRWjnsvWGFw== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1odEQC-0002iB-1I; Tue, 27 Sep 2022 10:31:04 -0700 In-Reply-To: <83ill9joji.fsf@gnu.org> 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:296360 Archived-At: Eli Zaretskii writes: [...] >> I was planning to takle these problems before proposing a merge: >> >> 1) Improve the worst case run time of `previous-overlay-change' from >> O(n) to O(log N). The noverlay branch uses an O(N) algorithm, >> though it is difficult to spot. Since the point of using a tree is >> O(log N) algorithms, and O(n) algorithms can easily become >> exponential algorithms when composed in higher level loops (the >> problem overlays sees today), this strikes me as important. [...] >> 3) Improve quality of comments in the new code. Personally, I find the >> algorithms quite subtle and quite a bit more complex than what you >> find on, say, https://en.wikipedia.org/wiki/Interval_tree or the >> Cormen et al. Introduction to Algorithms Book. I think I pieced >> most of it together but it took a lot of effort. At top of mind is >> looking at the interval_node.visited flag and figure out how that >> flag is used, then describe the algorithm in detail. It isn't clear >> to me how that flag gets set/cleared. Best case: doing so proves me >> wrong on point (1). [...] > We want to have this feature in Emacs 29, so, barring some grave bugs > that will be uncovered soon enough, this branch will land on master > soon. You can work on the items you've mentioned either now or after > the branch is merged. Item 3 can be done immediately, and will be > greatly appreciated, as comments that explain how the code works are > always welcome. I agree that this is a good plan. A nice thing about the noverlay branch is that it touches every place in Emacs that deals with overlay lists and, better, puts that behind an API. That is a good reason to merge noverlay now and, maybe, change things later. > Of the rest, item 1 sounds like the most important one, but do you > have ideas for how to achieve that? I think (3) -- improving the comments -- is a good starting point, because I want to verify my claim that the *-overlay-change algorithms are worst-case inefficient. My idea is: store each overlay in two trees, one ordered by ascending BEG and one ordered by descending END. These are the similar to the current "overlays before" and "overlays after" linked lists, except that the "overlay center" is gone and replaced by O(log N) lookups. (In fact we could retain the idea of an "overlay center" by maintaining a "finger" node in each tree...but I digress...) >From there an algorithm that is O(log N) in an obvious way falls out trivially in the same way it does for the current overlay lists approach.