From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Richard Stallman Newsgroups: gmane.emacs.devel Subject: Re: Overlay mechanic improvements Date: Sun, 21 Sep 2014 17:48:15 -0400 Message-ID: References: <871tr6qup8.fsf@fencepost.gnu.org> Reply-To: rms@gnu.org NNTP-Posting-Host: plane.gmane.org Content-Type: text/plain; charset=ISO-8859-15 X-Trace: ger.gmane.org 1411336124 7776 80.91.229.3 (21 Sep 2014 21:48:44 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 21 Sep 2014 21:48:44 +0000 (UTC) Cc: dak@gnu.org, emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Sep 21 23:48:40 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 1XVozn-0001wk-Sz for ged-emacs-devel@m.gmane.org; Sun, 21 Sep 2014 23:48:40 +0200 Original-Received: from localhost ([::1]:41070 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVozn-0000C0-I8 for ged-emacs-devel@m.gmane.org; Sun, 21 Sep 2014 17:48:39 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56224) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVozW-00008K-BY for emacs-devel@gnu.org; Sun, 21 Sep 2014 17:48:23 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XVozV-0007Jc-Eu for emacs-devel@gnu.org; Sun, 21 Sep 2014 17:48:22 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:42447) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVozV-0007Hc-Ch for emacs-devel@gnu.org; Sun, 21 Sep 2014 17:48:21 -0400 Original-Received: from rms by fencepost.gnu.org with local (Exim 4.71) (envelope-from ) id 1XVozP-0003WP-UF; Sun, 21 Sep 2014 17:48:15 -0400 In-reply-to: (message from Stefan Monnier on Sun, 21 Sep 2014 12:07:48 -0400) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::e 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:174627 Archived-At: [[[ To any NSA and FBI agents reading my email: please consider ]]] [[[ whether defending the US Constitution against all enemies, ]]] [[[ foreign or domestic, requires you to follow Snowden's example. ]]] Reasons for overlays being slow are: - if you have N overlays, you have 2N markers, so every insertion/deletion of text will involve a traversal of those 2N elements. - when we need to move from bytepos to charpos (or vice versa), we go through the 2N markers again. - when the Elisp code didn't know to overlay-recenter, or when overlays are added/removed from the "wrong" place (w.r.t to the overlay "center"), every overlay creation/removal takes O(N) time. Yes, that's true. Moving overlays into a balanced binary tree will remove those algorithmic performance problems. I'm not sue why you'd be opposed, since it will provide the exact same functionality anyway. It's just an internal detail of implementation. Why not do it for all markers, then? A large number of markers will cause the same slowdown even if they are not made for overlays. Note that I suggest to use the balanced binary tree used by text-properties, but there is no need for the two trees to be linked. I don't think the data structure of intervals lends itself directly to markers. A marker, whether it's on its own or an end of an overlay, has an identity that is permanent, whereas intervals are split and recombined whenever useful. -- Dr Richard Stallman President, Free Software Foundation 51 Franklin St Boston MA 02110 USA www.fsf.org www.gnu.org Skype: No way! That's nonfree (freedom-denying) software. Use Ekiga or an ordinary phone call.