From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Overlay mechanic improvements Date: Fri, 19 Sep 2014 13:22:43 -0400 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1411147403 32271 80.91.229.3 (19 Sep 2014 17:23:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 19 Sep 2014 17:23:23 +0000 (UTC) Cc: emacs-devel@gnu.org To: Vladimir Kazanov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Sep 19 19:23:16 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XV1tr-0007Mi-P8 for ged-emacs-devel@m.gmane.org; Fri, 19 Sep 2014 19:23:15 +0200 Original-Received: from localhost ([::1]:59591 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XV1tr-0000ga-Cz for ged-emacs-devel@m.gmane.org; Fri, 19 Sep 2014 13:23:15 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49755) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XV1tY-0000gJ-K9 for emacs-devel@gnu.org; Fri, 19 Sep 2014 13:23:02 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XV1tS-0005hP-Fr for emacs-devel@gnu.org; Fri, 19 Sep 2014 13:22:56 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:17530) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XV1tS-0005hF-CL for emacs-devel@gnu.org; Fri, 19 Sep 2014 13:22:50 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArYGAIDvNVNFpZEG/2dsb2JhbABZgwY7gw/APYEXF3SCJQEBAQECAVYPFAULCw4mEhQYDSSIBAgN0gwTBI4WZAeEOASpGYFqg0whgSw X-IPAS-Result: ArYGAIDvNVNFpZEG/2dsb2JhbABZgwY7gw/APYEXF3SCJQEBAQECAVYPFAULCw4mEhQYDSSIBAgN0gwTBI4WZAeEOASpGYFqg0whgSw X-IronPort-AV: E=Sophos;i="4.97,753,1389762000"; d="scan'208";a="90303811" Original-Received: from 69-165-145-6.dsl.teksavvy.com (HELO pastel.home) ([69.165.145.6]) by ironport2-out.teksavvy.com with ESMTP/TLS/DHE-RSA-AES256-SHA; 19 Sep 2014 13:22:44 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id EDA21642C6; Fri, 19 Sep 2014 13:22:43 -0400 (EDT) In-Reply-To: (Vladimir Kazanov's message of "Fri, 19 Sep 2014 17:59:34 +0300") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 206.248.154.181 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 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.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:174563 Archived-At: > After answering my question Stefan (Monnier?) mentioned that overlay > behavior can be fixed from N^2 to N*logN, which would make them > asymptotically equivalent to text properties; adding that he has no time to > implement the fix. So, here's the idea: Currently overlays are implemented as (two) sorted singly linked lists (one for overlays_before some position and one for overlay_after that position, for some quirky definition of "before" and "after"). The function `overlay-recenter' changes the position used for the split (and is called internally in various situations). Each overlay is itself implemented with two markers (which keep track of the overlay-start and overlay-end). Markers are implemented as a non-sorted singly linked list of markers. So every text insertion/deletion requires O(N) time, where N is the number of markers since we have to go down that list to update those markers that are affected by the modification. You can start in src/buffer.[ch], maybe grepping for overlays_before for a starting point. Text-properties, OTOH, are implemented with a (mostly) balanced binary tree. This is implemented in src/intervals.[ch]. So we'd like to change overlays so that they don't use markers (and we don't keep them in two sorted singly-linked lists) any more. Instead, we'll store them inside the balanced binary tree used for text-properties. I think we can use the "augmented tree" approach described in https://en.wikipedia.org/wiki/Interval_tree. To ease up debugging during development, I'd guess the implementation would first add the new stuff, keeping the old stuff (i.e. add to Lisp_Overlay whichever fields are needed for the new code, while keeping the old ones, add needed overlay fields to the intervals tree, but keep the old fields, the overlays_before etc...). This way, you can add consistency checks that make sure the new code computes the same results as the old code. And once that works well, we can remove the old code and old fields. So I suggest you start looking at src/buffer.[ch] and src/intervals.[ch]. That should make you ask many more questions. Stefan